§ 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.