Определение. Упорядоченная пара <x, y> интуитивно определяется как совокупность, состоящая из двух элементов x и y, расположенных в определенном порядке. Две пары <x, y> и <u, v> считаются равными тогда и только тогда, когда x = u и y = v.
Замечание. Предыдущее определение апеллирует к таким неопределенным понятиям как "совокупность" и "расположенные в определенном порядке". Для наших целей это вполне достаточно. Но понятие "упорядоченная пара" можно определить точно, используя понятия "множество", "элемент" и отношение принадлежности.
Упорядоченная n-ка элементов x1, x2,…,xn обозначается <x1, x2,…,xn> и, по определению, есть <<x1, x2,…,xn-1>, xn>.
Математическое понятие "отношение", так же, как и понятие "множество", является очень широким и общим. Три специальных типа отношений являются чрезвычайно важными: 1) функции; 2) отношения эквивалентности; 3) отношения порядка.
Определение. Бинарным (или двуместным) отношением r называется множество упорядоченных пар. Если r есть некоторое отношение и пара <x, y> принадлежит этому отношению, то наряду с записью <x, y>Оr употребляется запись xry. Элементы x и y называются координатами или компонентами отношения r. n-арным отношением называется множество упорядоченных n-ок.
Областью определения бинарного отношения r называется множество Dr = {x | существует такое y, что xry}.
Определение. Областью значений бинарного отношения r называется множество Rr={y | существует такое x, что xry}.
Пример 1.6.
1. Множество {<1, 2>, <2, 4>, <3, 3>, <2, 1>} - бинарное отношение.
2. Отношение равенства на множестве действительных чисел есть множество {<x, y> | x и y - действительные числа и x равно y}. Для этого отношения существует специальное обозначение =. Область определения Dr совпадает с областью значений Rr и является множеством действительных чисел.
3. Отношение "меньше чем" на множестве целых чисел есть множество {<x,y> | для целых чисел x и y найдется положительное число z такое, что x+ z = y}. Для этого отношения существует специальное обозначение <. Область определения Dr совпадает с областью значений Rr и является множеством целых чисел.
Определение. Прямым произведением множеств X и Y называется множество всех упорядоченных пар <x, y> таких, что xОX и yОY. Обозначается прямое произведение множеств X и Y через XґY.
Каждое отношение r есть подмножество прямого произведения некоторых множеств X и Y таких, что Dr Н X и RrНY. Если X =Y, то говорят, что r есть отношение на множестве X.
Определение. Прямым произведением множеств X1, X2,…, Xn называется множество всех упорядоченных n-ок <x1, x2,…,xn> таких, что xiОXi, i = 1, 2,…, n. Обозначается прямое произведение множеств X1, X2,…, Xn через X1ґX2ґ…,ґXn. Если X1=X2=…=Xn=X, то пишут X1ґX2ґ…ґXn=Xn. Любое n-местное отношение есть подмножество прямого произведения некоторых множеств X1, X2,…, Xn.
Пример 1.7.
1. Пусть X = {1, 2, 3}, Y = {0,1}. Тогда XґY = {<1, 0>, <1, 1>, <2, 0>, <2, 1>, <3, 0>, <3, 1>};
YґX = {<0, 1>, <0, 2>, <0,3>, <1,1>, <1, 2>, <1,3>}.
Мы указали, кроме того, такие множества X и Y, что XґY № YґX.
2. Пусть X - множество точек отрезка [0, 1], а Y - множество точек отрезка [1, 2]. Тогда XґY - множество точек квадрата [0, 1]ґ[1, 2] с вершинами в точках (0, 1), (0, 2), (1, 1) и (1, 2).
3. Пусть A = {1, 2, 3, 4, 5}. Пусть отношение r задано на A: x r y ó x делитель y. (Символ ó заменяет слова "тогда и только тогда, когда".)
Тогда r = {<1,1>, <1,2>, <1,3>, <1,4>, <1,5>, <1,6>, <2,2>, <2,4>, <2,6>, <3,3>, <3,6>, <4,4>, <5,5>, <6,6>}. Очевидно, r Í A2.
Для бинарных отношений обычным образом определены теоретико-множественные операции объединения, пересечения и т. д.
Определение. Обратным отношением для r называется отношение
r-1 = {<x, y> | <y, x>Оr}.
Определение.Композицией отношений r1 и r2 называется отношение r2 л r1 = {<x,z>| существует y такое, что <x, y>Оr1 и <y, z>Оr2}.
Для любых бинарных отношений выполняются следующие свойства:
(r-1)-1 = r ;
(g л j)-1 = j -1 л g -1 .
Первое свойство очевидно. Для доказательства второго свойства покажем, что множества, записанные в левой и правой частях равенства, состоят из одних и тех же элементах. Действительно, <x, y>О(g л j)-1 у <y,x> О gлj у существует z такое, что <y, z>j и <z, x>Оg у существует z такое, что <z, y>Оj-1 и <x, z>Оg-1 у <x, y>О j-1л g-1.