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

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

Определение 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².