§ 3. Декартово произведение множеств. Соответствия. Бинарные отношения и их свойства. Отображения.

Рассмотрим следующую реальную ситуацию. Фабрика верхнего трикотажа изготовляет мужские пуловеры, женские костюмы, кофты и платья следующих расцветок: бордо, синяя, голубая, зеленая, коричневая, серая. Обозначим через А множество видов изделий: А={мужской пуловер, женский костюм, кофта, платье}, через В – множество предлагаемых расцветок: В={бордо, синяя, голубая, зеленая, коричневая, серая}. Посмотрим, какие изделия можно получить, учитывая возможные для них расцветки. Для этого составим список всех пар из элементов множества А и элементов множества В таким образом, что сначала будем записывать элемент множества А, затем элемент множества В. получим множество С упорядоченных пар элементов множеств А и В. Возможные изделия можно перечислить с помощью таблицы. Итак, мы имеем дело с особым множеством, составленным из элементов двух данных множеств. Такое произведение называется декартовым произведением двух множеств.

А В	мужской пуловер	женский костюм	Кофта	Платье
Бордо	пуловер-бордо	костюм женский – бордо	кофта–бордо	Платье – бордо
Синяя	пуловер - синий
Голубая
Зеленая			кофта – зеленая
Коричневая				Платье – коричневое
Серая		костюм – серый

Опр. 3.1 Декартовым (или прямым) произведением множества А на множество В называется множество всех упорядоченных пар, в которых первая компонента – элемент множества А, а вторая – элемент множества В. Обозначают АВ.

Т аким образом, АВ={(x, y) xA, yB}.

Может случиться , что множества А и В окажутся одинаковыми. Рассмотрим следующий пример. Фабрика «Авторучка» изготовляет отдельно корпус и колпачок авторучек следующих цветов: белый, красный, зеленый, оранжевый.

Обозначим через А – множество цветов корпуса ручки, через В – множество цветов колпачка. Тогда получим: А=В={белый, красный, зеленый, оранжевый}. Можно составить список возможных колоритов для авторучки: цвет корпуса и цвет колпачка.

Объединяя всеми возможными способами цвет из А с цветом из В=А, получим элементы прямого произведения множества А «самого на себя», которое называется прямым или декартовым квадратом и обозначается: АА=А².

Из этого примера видно, что каждая пара прямого произведения должна быть упорядочена: красная ручка с белым колпачком отличается от белой ручки с красным колпачком.

Д ля описания прямого произведения множеств бывает удобно использовать «геометрический язык». При этом элементы множества АВ называются точками. Например, если z=(x,y), то хА называется абсциссой, а yВ – ординатой точки z. В связи с этим заметим, что множество точек плоскости по существу являются элементами прямого квадрата RR=R² множества R действительных чисел.

На рис.11 точками показаны элементы декартова произведения множеств А={1, 2, 3} и В={4, 5, 6, 7}. Отсюда легко видеть способ нахождения общего числа элементов в декартовом произведении двух множеств:

если m(А)=n, m(B)=k, то m(АВ)=nk (5).

Пример 3.1. Применим формулу (5) для подсчета количества двухзначных чисел. Двухзначное число можно принять за упорядоченную пару, где на первом месте может стоять цифра из множества А={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 городов. Чтобы получить прямое произведение этих множеств, надо составить все пары: (ученик – город).

Из множества всех таких пар мы выберем лишь такие, которые «связывают» каждого ученика с тем городом, где он бывал. Очевидно, что «список» таких пар (ученик – известный город) будет являться подмножеством  декартова произведения. Такой «список» удобно заменить таблицей, где можно указать все города, в которых побывал каждый ученик:

	Москва	Тула	Одесса	Тамбов	Воронеж	Липецк	Елец	Задонск	Лебедянь
Петя							
Вася							
Коля							
Саша								
Лена							
Таня							
Ирина							
Вера							
Андрей							
Витя								
Катя							

Можно сказать, что данная таблица задает определенное соотношение между элементами множеств А и В.

Опр.3.2 Будем говорить, что между элементами двух множеств А и В установлено соответствие , если в их произведении АВ выделено некоторое подмножество . Если пара (a,b), это означает по определению, что элементы a и b множеств А и В находятся в отношении  (пишется ab).

Еще один пример соответствия: Пусть даны множества А – студентов и В – множество групп. Утверждение “студент a учится в группе b” задает соответствие между множеством студентов и множеством групп. Здесь а пробегает множество значений А, b – множество значений В. Такое соотношение называется бинарным соответствием, т.е. соответствием между двумя множествами А и В.

Бинарные соответствия можно задавать таблицами (например, расписание занятий) или ориентированными графами.

	Пн.	Вт.	Ср.
Педагогика
Математика
Физкультура

Рис.12.

Если соответствие  задано между элементами одного и того же множества, то говорят, что между элементами этого множества задано отношение . Итак, задать на множестве А 2-хместное (бинарное) отношение означает выделить в прямом квадрате А² этого множества некоторое подмножество .

Опр.3.3 Бинарным отношением, заданным на множестве А называется всякое подмножество декартова произведения АА.

Местность отношения показывает сколько объектов могут разом находиться в данном отношении. Чаще всего рассматриваются бинарные (двухместные) или тернарные (трехместные) отношения.

Таким образом, бинарные соответствия между X и X называются бинарными отношениями на множестве X, т.е. соответствиями между элементами одного и того же множества (или равных множеств). Например, отношения: “2>1”, “3=3”, “человек х старше человека y” и др.

Пример 3.2. Возьмем в качестве элементов множества А случайную группу людей (например, едущих в одном поезде). И выберем бинарное отношение  на этом множестве следующим образом: два человека из А будут находиться в данном отношении, если они родились в одном и том же месяце (под одним знаком зодиака; имеют одинаковые имена и пр.). И еще элемент а₁ из А будет находиться в отношении  с элементом а₂ из того же множества, если, допустим, первый человек выше ростом, чем второй (старше, тяжелее и пр.).

Из этих примеров можно заметить, что если Таня родилась в том же месяце, что и Петя, то же самое можно сказать и о Пете: Петя родился в том же месяце, что и Таня. С учетом введенных обозначений можно записать: если ТаняПетя, то ПетяТаня. Иначе дело обстоит с другим отношением : если Таня ростом выше Пети, то неверно, что и Петя ростом выше Тани.

Таким образом, различные отношения могут иметь и различные свойства. Рассмотрим основные из них.

Опр.3.4 Бинарное отношение (БО) , заданное на множестве А, называется рефлексивным, если любой элемент этого множества находится в данном отношении с самим собой, т.е. аА: аа.

Опр.3.5 БО  называется симметричным, если из того, что пара (a,b) находится в отношении , следует, что и симметричная ей пара (b,a) тоже находится в этом отношении, т.е a,bA: ab ba.

Опр.3.6 БО называется антисимметричным ,если

a,bA: ab  ba  a=b.

Опр.3.7 БО называется транзитивным, если a,b,cA:

ab  bc  ac.

Примерами рефлексивного и транзитивного отношения является отношение равенства, не симметричного – отношения «больше» или «меньше» на множестве действительных чисел.

БИНАРНЫЕ ОТНОШЕНИЯ (ОПРЕДЕЛЕНИЯ)

БО , заданное на Множестве А, является:	Если выполняется Следующее условие:
Рефлексивным Симметричным Антисимметричным Транзитивным	aA 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

Опр.3.8 Бинарное отношение, обладающее свойствами рефлексивности, симметричности и транзитивности, называется отношением эквивалентности (или просто эквивалентностью).

Бинарное отношение  можно задать перечислением всех пар из АА, принадлежащих отношению, указанием характеристического свойства, которым обладают все элементы отношения, а также с помощью так называемого ориентированного графа. Для этого элементы множества А изображают в виде точек и вводят соглашение: если xy, то от точки x проводят стрелку к точке y. Если xх, то начало и конец стрелки совпадают, такую стрелку называют петлей. Выполнив указанные построения, получим фигуру – ориентированный граф. Точки, соединенные стрелками, называются вершинами графа, а сами стрелки – ребрами графа.

Пример 3.3. Пусть на множестве М={2,3,4,5,6} задано отношение  - кратности элементов, т.е. xy, если x  y (x делится на y без остатка). Построить ориентированный граф данного бинарного отношения.

Р ешение: Заметим, что по графу (рис. 13) наглядно можно судить о свойствах данного отношения: замкнутые на каждом элементе круглые стрелочки – признак рефлексивности отношения; единственная стрелка (а не с обеих сторон) у линии, соединяющей один элемент данного множества с другим, говорит о том, что отношение не является симметричным; отсутствие хотя бы у одной пары элементов соединяющих их стрелок указывает на то, что отношение не антисимметрично и т.д.

Рассмотрим еще один частный случай общего понятия “соответствие” – отображение множеств.

Рассмотрим два множества X и Y.

О пр 3.9 Если каждому элементу xX поставлен в соответствие единственный элемент yY, то такое соответствие называется отображением множества Х в множество Y. Т.е., каждому элементу х соответствует только один элемент y (рис.14).

Обозначается отображение множеств так: f: XY , здесь f – символ самого отображения.

Пример 3.4 Пусть Х – множество студентов в аудитории, Y – множество столов в этой аудитории. Соответствие “студент х сидит за столом y” задает отображение множества Х в множество Y. Это очевидно, так как все студенты сидят за столом, иногда по двое, по трое и т.д., но есть и пустые столы. При таком отображении множества Х в множество Y, элемент yY называется образом элемента xX, а элемент xX называется прообразом элемента yY.

О пр 3.10 Если при отображении f каждый элемент множества Y является образом хотя бы одного элемента из Х, то f называют отображением Х на Y или сюръективным (рис.15).

Пример 3.5 Пусть Х – множество студентов, Y – множество книг. Соответствие “студенту x принадлежит книга y” задает сюръективное отображение множества Х на множество Y. Это очевидно, так как каждая книга принадлежит одному или нескольким студентам, а некоторые студенты книг не имеют.

О пр 3.11 Если при отображении f все различные элементы множества Х переходят в различные элементы множества Y, то отображение f называется инъективным отображением (рис.16).

Пример 3.6 Пусть Х – множество студентов, Y – множество стульев. Соответствие “студент х сидит на стуле y” задает инъективное отображение между множествами Х и Y. Это очевидно, так как все студенты сидят на стульях, причем каждый на своем, но в аудитории есть и пустые стулья.

О пр 3.12 Если при отображении f каждому элементу xX поставлен в соответствие один элемент yY, при этом соответствии каждому элементу yY соответствует единственный элемент xX, то такое отображение называется взаимно-однозначным (рис.17).

Пример 3.7 Пусть Х – множество студентов, Y – множество зачетных книжек. Соответствие “студенту х принадлежит зачетная книжка y” задает взаимно-однозначное отображение между множествами Х и Y. Это очевидно, так как все студенты имеют зачетные книжки, причем каждый только одну и каждая зачетная книжка принадлежит своему студенту.

П ример 3.8 пусть Х – множество пальто в гардеробе, а Y – множество крючков в этом гардеробе. Поставим в соответствие каждому пальто крючок, на котором оно висит. Если каждое пальто висит на крючке (а не лежит на полу), то это соответствие является отображением X в Y. Это отображение инъективно, если ни на одном крючке не висит более 1-го пальто (крючки могут быть пустыми), и сюръективно, если все крючки заняты, но на некоторых крючках висит несколько пальто. Это отображение взаимно-однозначно, если на каждом крючке висит одно и только одно пальто.

Примеры

1. Перечислить и указать на координатной плоскости все элементы декартова произведения множеств А={-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)}.

З

Рис. 18

аметим, что точки на координатной плоскости, изображающие элементы декартова произведения ВА, будут симметричны соответствующим точкам из АВ относительно биссектрисы первого и третьего координатных углов. 

2. З аписать с помощью декартова произведения некоторых множеств фигуры, изображенные на рисунке (рис. 19):

Решение:

1. АВ, где А=(-3, -1], В=[2,6];

2) СD, где С=[3, 7), D=(-, +).

3. Выяснить, какими свойствами обладает бинарное отношение  - «отношение больше» на множестве N.

Решение: Для любых натуральных чисел х у, если ху.

1. хх – неверно для всех х, т.е. данное отношение не является рефлексивным;

2. для всякой пары натуральных чисел из ху не следует ух, т.е. БО не является симметричным;

3. для любых х,у выполняется одно из неравенств: ху или ух, т.е. отношение антисимметрично;

4. если ху, а уz, то справедливо хz, т.е. БО транзитивно.

Задачи для самостоятельной работы

1. Записать множества А и В, если известно, что АВ={(3;1), (-3;4), (0; 2), (1;3), (0;1), (5;7), (0;0), (5;5)}. Найти АВ, В\А. Изобразить на координатной прямой элементы множества ВА. Сколько элементов содержится в каждом из рассмотренных множеств?

2. На каком множестве задано БО  ={(2;3), (3;5), (5;7)}. Что можно сказать о его свойствах?

3 . Выберите некоторое множество, задайте на нем БО, постройте для этого отношения ориентированный граф, по графу определите свойства БО.

4. Определить свойства следующих бинарных отношений: 1)  - «родство по крови»; 2)  - «быть знакомым»; 3) отношение «=» - равенства на множестве R (а также , , ).

5. Записать с помощью декартова произведения множества точек координатной плоскости, указанные на рис. 20.

1. Постройте граф отношения, обладающего указанными ниже свойствами:

а) рефлексивность и транзитивность;

б) антисимметричность;

в) рефлексивность, симметричность и транзитивность.

2. Какие отношения эквивалентности можно задать на множестве N (R)? Какими еще свойствами они обладают?

8. Изобразить на координатной плоскости прямое произведение NR.