Декартово произведение множеств. Соответствия. Бинарные отношения и их свойства. Отображения.
Рассмотрим следующую реальную ситуацию. Школьникам дали цветную бумагу и попросили вырезать украшения для новогодней елки. Обозначим через А множество видов украшений: А={звездочка, снежинка, фонарик, гирлянда}, через В – множество предлагаемых цветов: В={красная, синяя, голубая, зеленая, розовая, белая}. Посмотрим, какие украшения можно получить, учитывая возможные для них расцветки. Для этого составим список всех пар из элементов множества А и элементов множества В таким образом, что сначала будем записывать элемент множества А, затем элемент множества В. получим множество С упорядоченных пар элементов множеств А и В. Возможные изделия можно перечислить с помощью таблицы. Итак, мы имеем дело с особым множеством, составленным из элементов двух данных множеств. Такое произведение называется декартовым произведением двух множеств.
| В А | звездочка | снежинка | фонарик | гирлянда |
| красная | звездочка – красная | снежинка – красная | фонарик – красный | гирлянда – красная |
| синяя | звездочка – синяя | снежинка – синяя | фонарик – синий | гирлянда – синяя |
| голубая | звездочка – голубая | снежинка – голубая | фонарик – голубой | гирлянда – голубая |
| зеленая | звездочка – зеленая | снежинка – зеленая | фонарик – зеленый | гирлянда – зеленая |
| розовая | звездочка – розовая | снежинка – розовая | фонарик – розовый | гирлянда – розовая |
| белая | звездочка – белая | снежинка – белая | фонарик – белый | гирлянда – белая |
Опр. 2.6.1. Декартовым (или прямым) произведением множества А на множество В называется множество всех упорядоченных пар, в которых первая компонента – элемент множества А, а вторая – элемент множества В. Обозначают А×В.
Таким образом, А×В={(x, y) |хÎА и yÎВ}.
Может случиться , что множества А и В окажутся одинаковыми. Рассмотрим следующий пример. Школьники делают открытки: отдельно обложку и внутреннюю часть следующих цветов: синий, красный, зеленый, желтый.
Обозначим через А – множество цветов обложки, через В – множество цветов внутренней части. Тогда получим: А=В={синий, красный, зеленый, желтый}. Можно составить список возможных сочетаний цветов для открытки: цвет обложки и цвет внутренней части.
Объединяя всеми возможными способами цвет из А с цветом из В=А, получим элементы прямого произведения множества А «самого на себя», которое называется прямым или декартовым квадратом и обозначается: А×А=А2.
Из этого примера видно, что каждая пара прямого произведения должна быть упорядочена: открытка с красной обложкой и с синей внутренней частью отличается от открытки с синей обложкой и с красной внутренней частью.
Для описания прямого произведения множеств бывает удобно использовать «геометрический язык». При этом элементы множества А×В называются точками. Например, если z=(x,y), то хÎА называется абсциссой, а yÎВ – ординатой точки z. В связи с этим заметим, что множество точек плоскости по существу являются элементами прямого квадрата R×R=R2 множества Rдействительных чисел.
На рис.1 точками показаны элементы декартова произведения множеств А={1, 2, 3} и В={4, 5, 6, 7}. Отсюда легко видеть способ нахождения общего числа элементов в декартовом произведении двух множеств: если m(А)=n, m(B)=k, то m(А×В)=n*k (4).
| 0 1 2 3 |
Рис.1.
Пример.Применим формулу (4) для подсчета количества двухзначных чисел. Двухзначное число можно принять за упорядоченную пару, где на первом месте может стоять цифра из множества А={1, 2, 3, 4, 5, 6, 7, 8, 9}, а на втором – из множества В={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, т.е. за элемент прямого произведения этих множеств, тогда получаем: m(А)=9, m(B)=10, то m(А×В)=9·10=90. Итак, всего имеется 90 различных двухзначных чисел. ♦
Перейдем к знакомству с другим новым понятием. Рассмотрим два множества: первое (А), состоящее из 11 учащихся, второе (В), состоящее из 9 городов. Чтобы получить прямое произведение этих множеств, надо составить все пары: (ученик – город). Из множества всех таких пар мы выберем лишь такие, которые «связывают» каждого ученика с тем городом, где он бывал. Очевидно, что «список» таких пар (ученик – известный город) будет являться подмножеством Ω декартова произведения. Такой «список» удобно заменить таблицей, где можно указать все города, в которых побывал каждый ученик:
| Москва | Тула | Одесса | Тамбов | Воронеж | Липецк | Елец | Задонск | Лебедянь | |
| Петя | × | × | × | × | |||||
| Вася | × | × | × | ||||||
| Коля | × | × | × | ||||||
| Саша | × | × | × | ||||||
| Лена | × | × | × | ||||||
| Таня | × | × | × | ||||||
| Ирина | × | × | |||||||
| Вера | × | × | |||||||
| Андрей | × | × | × | ||||||
| Витя | × | × | × | × | |||||
| Катя | × | × |
Можно сказать, что данная таблица задает определенное соотношение между элементами множеств А и В.
Опр.2.6.2. Будем говорить, что между элементами двух множеств А и В установлено соответствие ρ, если в их произведении А×В выделено некоторое подмножество Ω. Если пара (a,b) Î ΩÍΑ×Β, это означает по определению, что элементы a и b множеств А и В находятся в отношении ρ (пишется aρb).
Еще один пример соответствия: Пусть даны множества А – студентов и В – множество групп. Утверждение “студент a учится в группе b” задает соответствие между множеством студентов и множеством групп. Здесь а пробегает множество значений А, b – множество значений В. Такое соотношение называется бинарным соответствием, т.е. соответствием между двумя множествами А и В.
Бинарные соответствия можно задавать таблицами (например, расписание занятий) или ориентированными графами.
| Пн. | Вт. | Ср. | |
| Педагогика | |||
| Математика | |||
| Физкультура |
Рис. 2. 
Если соответствие ρ задано между элементами одного и того же множества, то говорят, что между элементами этого множества задано отношение ρ. Итак, задать на множестве А 2-хместное (бинарное) отношение означает выделить в прямом квадрате А2 этого множества некоторое подмножество Ω.
Опр.2.6.3 Бинарным отношением, заданным на множестве А называется всякое подмножество декартова произведения А×А.
Местность отношения показывает, сколько объектов могут разом находиться в данном отношении. Чаще всего рассматриваются бинарные (двухместные) или тернарные (трехместные) отношения.
Таким образом, бинарные соответствия между X и X называются бинарными отношениями на множестве X, т.е. соответствиями между элементами одного и того же множества (или равных множеств). Например, отношения: “2>1”, “3=3”, “человек х старше человека y” и др.
Пример.Возьмем в качестве элементов множества А случайную группу людей (например, едущих в одном поезде). И выберем бинарное отношение ρ на этом множестве следующим образом: два человека из А будут находиться в данном отношении, если они родились в одном и том же месяце (под одним знаком зодиака; имеют одинаковые имена и пр.). И еще элемент а1 из А будет находиться в отношении δ с элементом а2 из того же множества, если, допустим, первый человек выше ростом, чем второй (старше, тяжелее и пр.).
Из этих примеров можно заметить, что если Таня родилась в том же месяце, что и Петя, то же самое можно сказать и о Пете: Петя родился в том же месяце, что и Таня. С учетом введенных обозначений можно записать: если ТаняρПетя, то ПетяρТаня. Иначе дело обстоит с другим отношением δ: если Таня ростом выше Пети, то неверно, что и Петя ростом выше Тани.
Таким образом, различные отношения могут иметь и различные свойства. Рассмотрим основные из них.
Опр.2.6.4 Бинарное отношение (БО) ρ, заданное на множестве А, называется рефлексивным, если любой элемент этого множества находится в данном отношении с самим собой, т.е. "аÎА: аρа.
Опр.2.6.5 БО ρ называется симметричным, если из того, что пара (a,b) находится в отношении ρ, следует, что и симметричная ей пара (b,a) тоже находится в этом отношении, т.е"a,bÎA: aρb 
bρa.
Опр.2.6.6 БО называется антисимметричным, если "a,bÎA: aρb 
bρa a=b.
Опр.2.6.7 БО называется транзитивным, если"a,b,cÎA: aρb bρc aρc.
Примерами рефлексивного и транзитивного отношения является отношение равенства, не симметричного – отношения «больше» или «меньше» на множестве действительных чисел.
БИНАРНЫЕ ОТНОШЕНИЯ (ОПРЕДЕЛЕНИЯ)
| БО ρ, заданное на множестве А, является: | Если выполняется следующее условие: |
| Рефлексивным Симметричным Антисимметричным Транзитивным | "аÎА aρa
"a,bÎA aρb bρa
"a,bÎA aρb bρa a=b
"a,b,cÎA aρb bρc aρc
|
Опр.2.6.8 Бинарное отношение, обладающее свойствами рефлексивности, симметричности и транзитивности, называется отношением эквивалентности (или просто эквивалентностью).
Бинарное отношение ρ можно задать перечислением всех пар из А×А, принадлежащих отношению, указанием характеристического свойства, которым обладают все элементы отношения, а также с помощью так называемого ориентированного графа. Для этого элементы множества А изображают в виде точек и вводят соглашение: если xρy, то от точки x проводят стрелку к точке y. Если xρх, то начало и конец стрелки совпадают, такую стрелку называют петлей. Выполнив указанные построения, получим фигуру – ориентированный граф. Точки, соединенные стрелками, называются вершинами графа, а сами стрелки – ребрами графа.
Пример.Пусть на множестве М={2,3,4,5,6} задано отношение ρ -кратности элементов, т.е. xρy, если x M y (x делится на y без остатка). Построить ориентированный граф данного бинарного отношения.
Решение: Заметим, что по графу наглядно можно судить о свойствах данного отношения: замкнутые на каждом элементе круглые стрелочки – признак рефлексивности отношения; единственная стрелка (а не с обеих сторон) у линии, соединяющей один элемент данного множества с другим, говорит о том, что отношение не является симметричным; отсутствие хотя бы у одной пары элементов соединяющих их стрелок указывает на то, что отношение не антисимметрично и т.д. ♦
Рассмотрим еще один частный случай общего понятия “соответствие” – отображение множеств.
Рассмотрим два множества X и Y.
Опр. 2.6.9 Если каждому элементу xÎX поставлен в соответствие единственный элемент yÎY, то такое соответствие называется отображением множества Х в множество Y. Т.е., каждому элементу х соответствует только один элемент y Обозначается отображение множеств так: f: X→Y , здесь f – символ самого отображения.
Пример.Пусть Х – множество студентов в аудитории, Y – множество столов в этой аудитории. Соответствие “студент х сидит за столом y” задает отображение множества Х в множество Y. Это очевидно, так как все студенты сидят за столом, иногда по двое, по трое и т.д., но есть и пустые столы. При таком отображении множества Х в множество Y, элемент yÎY называется образом элемента xÎX, а элемент xÎX называется прообразом элемента yÎY.
Опр.2.6.10 Если при отображении f каждому элементу xÎX поставлен в соответствие один элемент yÎY, при этом соответствии каждому элементу yÎY соответствует единственный элемент xÎX, то такое отображение называется взаимно-однозначным.
Примеры.1) Пусть Х – множество студентов, Y – множество зачетных книжек. Соответствие “студенту х принадлежит зачетная книжка y” задает взаимно-однозначное отображение между множествами Х и Y. Это очевидно, так как все студенты имеют зачетные книжки, причем каждый только одну и каждая зачетная книжка принадлежит своему студенту.
2) Перечислить все элементы декартова произведения множеств А={-2, 1, 3} и В={-1, 0, 2, 5}.
Решение: А×В={(-2,-1), (-2,0), (-2,2), (-2,5), (1,-1), (1,0), (1,2), (1,5), (3,-1), (3,0), (3,2), (3,5)}.
Заметим, что точки на координатной плоскости, изображающие элементы декартова произведения В×А, будут симметричны соответствующим точкам из А×В относительно биссектрисы первого и третьего координатных углов.
3) Выяснить, какими свойствами обладает бинарное отношение η - «отношение больше» на множестве N.
Решение: Для любых натуральных чисел хηу, если х>у.
а) х>х – неверно для всех х ÎΝ, т.е. данное отношение не является рефлексивным;
б) для всякой пары натуральных чисел из х>у не следует у>х, т.е. БО не является симметричным;
в) для любых х,у ÎΝ выполняется одно из неравенств: х>у или у>х, т.е. отношение антисимметрично;
г) если х>у, а у>z, то справедливо х>z, т.е. БО транзитивно.