Упорядоченные пары. Декартово (прямое) произведение множеств. Отношения

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

Определение 2.1. Упорядоченной парой (набор из 2 объектов) из элементов a и b (a,b), взятых именно в этом порядке, называется множество, состоящее из двух множеств, включающих элемент a: { a },{ a,b }.

(a,b) = {{ a },{ a,b }}

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

Лемма: упорядоченные пары (a,b) и (c,d) равны тогда и только тогда, когда выполняется условие: (a,b) = (c,d) | a = с & b = d

Обобщением понятия упорядоченной пары является упорядоченный n-набор или картеж. В отличии от конечного множества {a₁, … a_n} картеж (a₁, … a_n) на множествах А₁, … А_n, характеризуется не только входящими в него элементами, но и порядком в котором они перечисляются, как и для упорядоченных пар роль порядка в картеже фиксируется определением равенства картежей.

Определение 2.2. Множество всех картежей длины n на множествах А₁, … А_n называется декартовым.

Пусть А и В – два множества.

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

Обозначают: А ´ В:= {(а,b) | а Î А & b Î B }

Степенью множества А называется его прямое произведение самого на себя.

Соответственно: А ¹:= A; А ²:= A ´ A; А ³:= A ´ A ²; и вообще А ⁿ:= A ´ A ^n-1

Теорема: |А´В| = |А| ´ |В|

Доказательство:

Первый компонент упорядоченной пары можно выбрать |А| способами, второй - |В| способами (|А| - число элементов множества А; |В| - число элементов множества В.)

Таким образом, всего имеется |А| · |В| упорядоченных пар.

Пример 2.1.: А = {1,2,3}, |A| = 3; B = {4,5}, |B| = 2;

|А ´ В| = |А| ´ |В| = 3·2 = 6;

|А ´ В| = |{(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)}| = 6;

Пусть А и В – два множества.

Определение 2.4. Бинарным отношением R из множества А в множество В называется подмножество прямого произведения: R Ì A ´ B.

Для бинарных отношений обычно используется инфиксная форма записи:

a R b:(a,b)Î R Ì A ´ B.

Если А = В, то говорят, что R есть отношение на множестве А и записывают R Ì A ´ А или R Ì A ².