КОРТЕЖИ И ДЕКАРТОВО ПРОИЗВЕДЕНИЕ МНОЖЕСТВ. БИНАРНЫЕ ОТНОШЕНИЯ

КОРТЕЖИ И ДЕКАРТОВО ПРОИЗВЕДЕНИЕ МНОЖЕСТВ. БИНАРНЫЕ ОТНОШЕНИЯ

В математике для обозначения связи между предметами или понятиями используют термин «отношение».

Примеры отношений.

• х меньше у;

• х делится на у;

• прямая а параллельна b;

• х включено в у;

• х является сыном для у и т.п.

Понятие «отношение» будем рассматривать в рамках теории множеств.

Определение.

Пусть даны множества Х1, Х2, … Хn. Кортежем длины n, составленным из элементов этих множеств, называется конечная упорядоченная последовательность этих элементов. , где - называется k-ой координатой.

Кортежи длины два называют упорядоченными парами, длины три – упорядоченными тройками, длины четыре – упорядоченными четвертками, длины n – упорядоченными n-ками. Кортеж, не содержащий ни одной координаты, называется пустым.

Определение.

Два кортежа равны в том и только том случае, когда они имеют одинаковую длину и координаты, стоящие на местах с одинаковыми номерами, равны. .

Пример1.

, , .

Таблица 1. Основные отличия понятий кортежа и множества

№ п/п	Отличительные черты	Множества	Кортежи
1	Порядок	порядок не играет роли	порядок важен
2	Элементы	все элементы различны	элементы могут повторяться

Определение.

Прямым (или декартовым) произведением двух множеств A и B называется множество упорядоченных пар, таких, что первый элемент каждой пары принадлежит множеству A, а второй – множеству В. .

Пример2.

Пусть и , тогда

декартово произведение не обладает свойством коммутативности, т.е. .

Определение.

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

Французский математик и философ Рене Декарт впервые предложил координатное представление точек плоскости в своей работе «Рассуждение о методе, позволяющем направлять свой разум и отыскивать истину в науках» в 1637 году («Рассуждение о методе» известно как источник знаменитой фразы Je pense, donc je suis –«Я мыслю, следовательно я существую»). Это исторически первый пример прямого произведения.

Таким образом, бинарное отношение  есть множество упорядоченных пар, и если пара x, y принадлежит , то это записывается следующим образом: x, y   или, что то же самое, x y.

Рисунок 1. Способы задания бинарного отношения

Определение.

Областью определения бинарного отношения называется множество, состоящее из таких х, для которых x, y  . . Областью значения бинарного отношения называется множество, состоящее из таких у, для которых x, y  . . Областью задания бинарного отношения называется: .

Пример3.

Пусть  = {1, 3, 3, 3, 4, 2}.

Тогда D = {1, 3, 4}, R = {3, 2}, M = {1, 2, 3, 4}.

Так как бинарные отношения являются множествами, то все операции над множествами справедливы для отношений.

Пример4.

Пусть даны два бинарных отношения:

₁ = {1, 2, 2, 3, 3, 4} и ₂ = {1, 2, 1, 3, 2, 4}.

Объединение бинарных отношений: ₁  ₂ = {1, 2, 1, 3, 2, 3, 2, 4, 3, 4}.

Пересечение бинарных отношений: ₁  ₂ = {1, 2}.

Разность бинарных отношений: ₁ \ ₂ = {2, 3, 3, 4}.

Определим еще две операции над бинарными отношениями.

Определение.

Отношение называется обратным к отношению , если

Пример5.

Пусть дано бинарное отношение  = {1, 2, 2, 3, 3, 4}.

Тогда  ^–1= {2, 1, 3, 2, 4, 3}.

Определение.

Композицией двух отношений  и  называется отношение , где - внутреннее бинарное отношение^1, - внешнее бинарное отношение.

Пример6.

Пусть даны бинарные отношения:

и .

Тогда , значит, композиция не обладает свойством коммутативности.

Ознакомимся с основными свойствами бинарных отношений:

Свойства бинарных отношений:

1. Рефлексивность: для любого x X выполняется xx.

2. Симметричность: для любых x, y  X из xy следует y x.

3. Транзитивность: для любых x, y, z  X из xy и yz следует xz.

4. Эквивалентность: если бинарное отношение рефлексивно, симметрично и транзитивно на множестве X.

5. Антисимметричность: для любых x, y  X из xy и yx следует x=y.

6. Отношение частичного порядка: если бинарное отношение рефлексивно, антисимметрично и транзитивно на множестве X.

Если бинарное отношение обладает свойством эквивалентности, то это дает возможность выделить классы эквивалентности.

Определение.

Классом эквивалентности, порожденным элементом xX, называется множество всех элементов y, для которых xy .