2.4. Декартово произведение множеств. Бинарные отношения

Отношения между двумя и более множествами рассматриваются в разделе 2.3.1. Данная операция позволяет их сравнивать и делать вывод о равенстве или включении одного множества в другое. Известно, если два множества состоят из одних и тех же элементов, то эти множества равны независимо от порядка их следования. Однако в математике рассматриваются множества, где учитывается порядок следования элементов множества. В том случае, когда важен порядок следования элементов, в математике вводят понятие упорядоченных наборов элементов. Двухэлементное множество {x, y}, в котором элемент х стоит на первом месте, а y – на втором называется упорядоченной парой (x; y). Упорядоченную пару, образованную из элементов: х , y принято записывать в круглые скобки (x; y). Элемент x называют первой координатой пары, а элемент y – второй. Две пары равны, если их координаты совпадают. Если сравнить два множества: {2,5}; {5,2}, то можно отметить, что они равны, так как они состоят из одинаковых элементов. Если сравнить две упорядоченные пары: (2; 5), (5; 2), то следует отметить, что они не равны, так как их координаты не совпадают. В этом основное отличие упорядоченной пары от двухэлементного множества.

Упорядоченные пары можно образовывать как из элементов одного множества, так и двух множеств. В примере 9 рассматривается образование упорядоченных пар из элементов двух множеств.

Пример 9.

Пусть заданы два множества: X={7,5}, Y={1,4,8}. Из этих множеств можно создать новое множество, перечислив все упорядоченные пары:{(7;1), (7;4), (7;8), (5;1), (5;4), (5;8)}. В полученном множестве каждый элемент является упорядоченной парой, в которой первая компонента принадлежит множеству X, вторая множеству Y.

При создании нового множества элементы первого множества должны стоять на первом месте, элементы второго множества должны стоять на втором месте. Множество, элементами которого являются упорядоченные пары чисел, называется декартовым произведением. На примере 9 можно отметить: создание нового множества, состоящего из упорядоченных пар, аналогично перемножению элементов двух скобок, т.е. заданных множеств X,Y , только операция умножения заменяется построением соответствующих пар.

Определение 12: Декартовым произведением множеств X и Y называется множество всех пар (x, y), первая компонента которых xX, вторая компонента yY. Декартово произведение множеств X и Y обозначают XY и его можно записать: XY = {(x; y) | xX ; yY }.

Аналогично можно конструировать новые множества, используя вместо пар (x,y) наборы из n –элементов {а, x, y,...}. Упорядоченные наборы, состоящие из n – элементов (n-ки) называют кортежами. Длина кортежа – это число элементов, из которых он состоит. Например, (с, т, у, д, е, н, т) – это кортеж длины 7. Тогда, декартово произведение n – множеств есть множество кортежей, построенных из n – элементов этих множеств.

В упорядоченных кортежах компоненты могут находиться в какой-то связи, т.е. отношении. Если рассматривают отношения между объектами, то это: «больше», «меньше», «равно». Например: x>y; z<r; а=с; x A.

Из этих примеров видно, что отношение используется для двух объектов, записанных в определенном порядке. Если две упорядоченные пары равны, то они находятся в отношении равенства. Чтобы определить отношение, достаточно перечислить все пары, которые находятся в данном отношении.

Отношение–из X в Y есть некоторое множество упорядоченных пар (x; y), где: xX, yY. Так как отношение связывает два объекта, его назывют бинарным. Если (x, y), гдеесть некоторое множество упорядоченных пар, то элемент х находится в отношениис элементом y.

Если рассматривают отношения между тремя элементами, то их называют тернарными, отношения между n элементами – n-арными. Примером тернарного отношения может служить отношение между точками прямой: точка х лежит между двумя точками прямой (z, y). Если рассматривать некоторую точку, удовлетворяющую или нет данному отношению (например, принадлежности прямой), то данное отношение будет унарным. В математике чаще всего встречаются бинарные отношения – множество пар, т.е. отношения, заданные на декартовом произведении двух множеств: А1А2.

Примеры бинарных отношений:

• Бинарное отношение старшинства между двумя людьми по возрасту или воинскому званию.

• Бинарное отношение между целыми числами – «иметь одинаковые остатки от деления на 7».

Можно отметить виды отношений между элементами множества.

1. Отношения эквивалентности. В этом случае выделяется какое-то свойство множества (например, положительные или отрицательные числа, чёрный или белый цвет). По этому свойству элементы, принадлежащие одному классу эквивалентности, являются эквивалентными. Например. Отношение параллельности на множестве прямых. Отношение подобия на множестве всех треугольников на плоскости.

2. Отношения частичного порядка. Примеры отношений частичного порядка: числа кратные двум, или трём, или семи и т. д., отношения «больше» или «меньше», x > y, z < r. Пример. Отношение на множестве задано неравенством: 5x-2y>0. Можно построить новое множество, которое соответствует данному отношению: {(1,0);(2,1);(3,2)}. Данное множество состоит из упорядоченных пар, каждая из которых удовлетворяет заданному отношению.

3. Отношения строгого порядка (зависимости). Примеры отношений зависимости: табличная, функциональная y=f(x). График функции есть множество упорядоченных пар: G = {(x, y) | x X; yf(x)}.

Рассмотрим различные виды бинарных отношений на примерах. Множество {(2;4), (7;3), (3;3), (2;1)} есть множество упорядоченных пар. Однако между парами отсутствует связь. Если установить отношение «меньше»: x < y , то множество можно записать для примера в виде: {(2;3), (4;7), (5;8), (8;17)}. В последнем примере элементы множества располагаются по возрастанию. Такое отношение называется отношением частичного порядка, а множество из таких элементов получится частично упорядоченным.

Иначе можно записать бинарные отношения, если между ними установить функциональную зависимость.

Пример 10.

y=x+2, множество из порядоченных пар можно записать в виде:

{(2;4), (4;6), (6;8), (8;10)}. В общем виде: {(x, y) | x X; y = x+2}.

Пример 11.

Пусть задано отношение на множестве в виде функциональной зависимости. Z = {(x, y) | x X; y = x²}. В этом примере можно строить любое множество из упорядоченных пар, задаваясь значением х и вычисляя y = x². Например. {(1,1);(2,4);(3,9)(4,16)}.

Пример 12.

D={(x;y)|xX;y=cosx}. Если построить график данной зависимости на координатной плоскости, то он будет наглядным представлением отношения. В данном случае каждая упорядоченная пара отношения (x, y)графически может быть представлена точкой на плоскости. Соединив все точки данной функциональной зависимости кривой линией, можно получить графическое представление бинарного отношения.

Обобщая выше рассмотренное, можно отметить:

1. Бинарное отношение из множества X в множество Y есть подмножество декартова произведения множеств: XY. Отношения состоят из однотипных кортежей.

2. Бинарное отношение на множестве Х есть всякое подмножество декартова произведения ХХ.

Пример 13.

Пусть на множестве Х={3, 5, 7} задано отношение «меньше» (т.е. первый элемент меньше второго, второй меньше третьего). Записать декартово произведение X Х.

Решение.

Декартово произведение X Х может быть записано в виде множества из упорядоченных пар: {(3,3);(3,5);(3,7);(5,3);(5,5);(5,7);(7,3);(7,5);(7,7)}. Из этого множества следует выбрать элементы, которые должны удовлетворять отношению «меньше». В результате получится новое множество из упорядоченных пар: {(3;5), (3;7), (5;7)}. В новом множестве все пары являются элементами декартова произведения ХХ. Отношение «меньше» на множестве Х является подмножеством декартова произведения ХХ.

3. Подмножество R декартова произведения множеств Х₁Х₂Х₃... X_nназывается отношением степени n (n-арным отношением).

В математике, как правило, отношения заданы на бесконечных множествах и имеют бесконечную мощность. Отношение – понятие очень широкое. Поскольку отношения являются множествами, то к ним применимы все теоретико-множественные операции: объединение, пересечение, дополнение и др.