Соответствия. Отображения. Отношения

Прямым произведением множеств А и В называют множество, обозначаемое А´В и состоящее из всех и только тех упорядоченных пар, первая компонента которых принадлежит множеству А, а вторая – множеству В, т.е. А´В={(x,y)|xÎA, yÎB}. Прямое произведение дистрибутивно относительно объединения и пересечения.

Соответствием между множествами Х и Y называется подмножество . Если (x, y) , то говорят, что у соответствует х при соответствии G. Множество Пр₁G называется областью определения соответствия, множество Пр₂G – областью значений соответствия. Если Пр₂G=Y, то соответствие называется сюръективным. Множество всех соответствующих элементу называется образом х в Y при соответствии G. Множество всех х, которым соответствует у, называется прообразом у в Х при соответствии G.

Соответствие называется функциональным (или однозначным), если образом любого элемента Пр₁G является единственный элемент из Пр₂G. Функцией называется функциональное соответствие.

Если функция f устанавливает соответствие между множествами Х и Y, то говорят, что функция f имеет тип Х®Y и обозначается f:X®Y.

Полностью определенная функция f:X®Y называется отображением Х в Y. Образ Х при отображении f обозначается f(X). Если соответствие при этом сюръективно, т.е. каждый элемент Y имеет прообраз в Х, то говорят, что имеет место отображение Х на Y (сюръективное отображение).

Если и , то есть функция, определенная на А со значениями в Y. Эту функцию называют сужением f на множество А и обозначают f|A или f_A.

Пример 10. {(1,2), (2,2), (Иванов, Петров)} есть функция с областью определения {1, 2, Иванов} и областью значений {2, Петров}.

Пример 11. {(1,2), (1,3), (2,5)} не является функцией, т.к. различные элементы (1,2) и (1,3) имеют одинаковую первую координату.

Пример 12. Множество {(a,b), (c,b), (e,d), (k,m)} есть функция, а подмножество этого множества {(a,b), (e,d)} является сужением этой функции на множество {a,e}.

Отображение представляет собой отображение множества Х в самого себя и определяется парой (Х, R), где . В этом случае для обозначения данного отображения используется термин отношение и вводят специальную символику: yRx – у находится в отношении R к х.

Подмножество называется n-местным отношением между А₁, А₂, …..A_n. Если n=2, то R называется бинарным отношением.

Пример 13. Множество {(3,4), (4,6), (7,9), (4,12)} будучи множеством упорядоченных пар натуральных чисел, есть бинарное отношение на N, где N – множество натуральных чисел.

Отношение R называется ( ):

Ø рефлексивным, если для любого имеет место ;

Ø антирефлексивным, если ни для какого не выполняется ;

Ø симметричным, если для пары из aRb следует bRa;

Ø антисимметричным, если из a_iRa_j и a_jRa_i следует, что a_i=a_j;

Ø транзитивным, если для любых a, b, c из aRb и bRc следует aRс.

Отношение R называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. Обозначается символом º.

Пример 14. Докажите, что отношение равенства «=» на любом множестве является отношением эквивалентности.

Решение. Действительно, для данного отношения выполняются свойства: рефлексивности (а=а); симметричности (а=в в=а); транзитивности [(а=в и в=с) а=с].

Отношением предпорядка на множестве А называется отношение , если оно рефлексивно и транзитивно.

Отношением порядка называется отношение, если оно рефлексивно, антисимметрично и транзитивно.

Отношением строгого порядка называется отношение, если оно антирефлексивно, антисимметрично и транзитивно.

Пример 15. Задано бинарное отношение R на множестве М={1, 2, 3, 4}. Является ли оно рефлексивным, симметричным, антисимметричным, транзитивным? Найти область определения d_R, область значений r_R, обратное отношение R^-1, пересечение и объединение отношений R и R^-1

R={(1,1), (1,2), (1,3), (1,4), (4,1), (4,2), (4,3), (4,4).

Решение.

Отношение R, заданное на множестве М, называется рефлексивным, если для всякого х из этого множества хRх истинно. Заданное отношение не является рефлексивным, так как нет пар (2,2) и (3,3).

Отношение R, заданное на множестве M называется симметричным, если на этом множестве из xRy следует yRx. Заданное отношение не является симметричным, т.к., например, пара (1,2) R, а (2,1) R.

Отношение R, заданное на множестве M называется антисим-метричным, если на этом множестве из xRy и yRx следует x=y. Заданное отношение не является антисимметричным, так как ему принадлежат пары (1,4) и (4,1), но 1¹4.

Отношение R, заданное на множестве M называется антирефлексивным, если для любого xRx ложно. Заданное отношение антирефлек-сивно, так как (уже было показано) нет пар (2,2) и (3,3).

Отношение R, заданное на множестве M называется транзитивным, если на этом множестве из xRy и yRz следует xRz. Заданное отношение является транзитивным, так как для любых двух пар (a,b) и (b,c) следует, что (a,c) R, где а, в, с М.

Областью определения отношения R называется множество d_R ={x| $(у) xRy}. Следовательно, областью определения R является двухэлементное множество {1, 4}.

Областью значений отношения R называется множество r_R={y|$(x) xRy}. Следовательно, областью значений является все множество М={1, 2, 3, 4}.

Обратным отношением для R называется отношение R^-1={(y,x)|(x,y) R}.

Обратное отношение R^-1={(1,1), (2,1), (3,1), (4,1), (1,4), (2,4), (3,4), (4,4)}.

Пересечение R и R^-1 равно R R^-1={(1,1), (4,1), (1,4), (4,4)}.

Объединение R и R^-1 равно R R^-1={(1,1), (1,2), (1,3), (1,4), (4,1), (4,2), (4,3), (4,4), (2,1), (3,1)}.

Пример 16. График функции f(x) (cм. рис. 1.2) представляет собой ломанную, звенья которой параллельны координатной оси, либо биссектрисам координатных углов. Координаты каждой вершины ломанной являются целыми числами. Функция f(x) определяет отношение R_f на множестве Х=[0, 5]: xR_fy f(x)=f(y), т.е. х находится в отношении R_f с у тогда и только тогда, когда f(x)=f(y).

Доказать, что R_f – эквивалентность на Х. Перечислить все классы эквивалентности.

a 2+a

Рис. 1.2

A