Отношения на множествах

Поскольку изначально во множествах никакого порядка не предполагается: {Ь, 0, р} ={р, О, b} = {b, р, 0} = • • •, то мы формулируем:

Определение 3.7. Упорядоченной парой элементов, а и b называется множество {а, {а, Ь)}, обозначенное для краткости символом (а, Ь), где, а называют первым элементом пары (а, Ь) и b — вторым.

Аналогично определяется для грех элементов а, b и с упорядоченная

тройка: (а, Ь, с) ={а,{Ь, (Ь, с)}} и по индукции определяется упорядоченная л-ка: (а, а₂,…,"")={"i> {а,(а₂,.

Упорядоченную/г-ку называют также «-набором, /7-кортежем и нр.

Гипотеза 3.2. Теоремой является утверждение

Утверждение, обратное данному, почти очевидно. Действительно, из {а = c)8i (b = d)=>{a, b}={c, d} и далее {я, {а, 6}} = {с, {с, cl)}. Эти рассуждения дают начало проверки гипотезы: по определению пары из (я, b) = (с, {я, {я, Ь)} = {с₉ {с, cl)}. Теперь по определению равенства множеств либо (я = с)&({я, b} = {с, d)), либо я = {с, d} и с = {я, 6}. Далее, … дерзайте, Читатель! (Или см. [7, с. 82], [22, с. 9], [53, с. 180]).

Определение 3.8. Прямым произведением множеств, А и В называется множество всех тех упорядоченных пар (я, b), где, а е, А и Ъ е В.

Формальная запись: А х В={(а, Ь):а е, А &Ь е В}.

Это множество называют также декартовым произведением множеств А и В. Сами множества А и В в отношении к их прямому произведению называют первой и, соответственно, второй проекцией:

Наконец, множество {а} х В назовем слоем над а в прямом произведении Ах В для а е А .

Пример 3.1. Числовая плоскость ХОУ есть прямое произведение двух числовых прямых.

Определение 3.9. Бинарным отношением р между множествами А и В называется всякое подмножество р прямого произведения Ах В этих множеств.

Для всякого отношения р * 0 между множествами А и В можно построить обратное к р отношение р^-1, определяемое формулой.

Если А = В, то говорят, что бинарное отношение р q Ах, А задано во множестве А. Аналогично определяется декартово произведение п множеств A_l9A₂₉…₉A_fJ и и-арные отношения между ними. Если все сомножители декартового произведения равны, то произведение А х, А х ••• х А называется декартовой степенью множества Л.

Подмножество D_pc^, D_p ={х: By (х, у) е р q, А х В} ^ А, называют областью (множеством) определения отношения р, т. е. Dp= РГ| jC. Если D_p = А, то говорят, что р задано на множестве А.

Аналогично, R_p ={у: Зх (х₉ у) е р е А х В} с В, называют множеством значений бинарного отношения р, т. е. R_p = Рг_7/ рей.

Пример 3.2. Пусть А = {-1, 0, 2, 3}, В = { 1, — 2,3}. Тогда, например, А хВ={(-1,-2), (-1,1), (-1,3),(0,-2), (0,1), (0,3), (2,-2), (2,1), …, (3,3)}, А х {3} = {(-1, 3), (О, 3), (2,3), (3, 3)}, {2} х В = {(2, — 2), (2,1), (2,3)}:

Рис. 3.4.

Определение ЗЛО. Полным образом (прообразом) в отношении р cz Л х 5 элемента, а е, А {элемента be В) называют подмножество

р(а) с В (р" (b) q А), определяемое формулой

Иллюстрацию этих множеств дает следующий ниже рис. 3.5.

Рис. 3.5.

Графиком Gr_p отношения рс^хй называют объединение по всем элементам а е D_p слоев вида D_p х р(а) над полными образами в данном отношении р ^ Ах В элементов а е Z)_p на прямом произведении D_p х R_p,.

т. е. Gr_p = _u (D_pxp (a)) <^D_pxR_p.

aeD_p

Определение 3.11. Бинарное отношение pc /1×5 называется функциональным в точке а, если образ р(а) <= В есть одноэлементное множество. Функциональное в каждой точке, а области определения D_p бинарное отношение р называется отображением или функцией.

Употребительны также следующие термины: соответствие, преобразование, правило, морфизм, операция, оператор, закон, функционал, стрелка и др. Так, операцией (л-арной) чаще называют функцию, заданную на Ах Ах • • • х А со значениями в А, знак (термин) стрелка используется в схемах и диаграммах: А-^>В, f: А—> В, /: я —"Z?, или как на рис. 3.6. Для каждой функциональной стрелки f определенной на, а со значением b, существует функциональная стрелка g, определенная на b со значением а

(J: а^> Ь) о (g: 6—>я). Поэтому при f[a) = Ь и g (b) = a пишут / = g⁴ и g = /": f (f~)) = b и g (g~a)) = a. Попытки доказать сформулированное выше утверждение уведут любознательного читателя глубоко в основания теории множеств и откроют ему бездну неизведанного, и пусть напутствием ему будет седьмой дополнительный параграф этой главы.

Рис. 3.6.