Отображения. Виды отображений. Композиция отображений. Примеры.
1) f:X®Y – отображение с областью задания X и областью значений Y, если "xÎX $! f(x)ÎY.
2) Пусть f:X®Y – отображение, если Y=X, то f – преобразование мн-ва X. 3) –²– Imf={f(x)| xÎX} – образ мн-ва X при действии отобр. f. 4) –²– f-1(y)={xÎX| f(x)=y}– преобразование элемента y при отображении f. 5) Отобр. f:X®Y – сюрьективно (отображение ²на²), если Imf=Y (т.е. "yÎY $ xÎX: f(x)=y). 6) Отобр. f:X®Y – инъективное, если x=x¢ Û f(x)¹f(x¢), где x,x¢ÎX.
7) Отобр. f:X®Y – биективное, если f – сюрьективно и инъективно. 8) Пусть f:X®Y и g:A®B – отображения; f и g одинаковые (совпадают), если: 1. X=A, Y=B и 2. f(x)=g(x) "xÎX. Пр.: f:R®R (x|®x2), g:R®R+ (x|®x2), H:R+®R+ (x|®x2), т.е. f,g,h – все разные.
9) ex – единичное (тождественное) преобразования мн-ва X, если ex:X®X (x|®x). 10) ] f:U®V, g:V®W, то f°g:U®W (u®g(f(u)) – композиция отобр. f и g). Замеч.: f:X®X, g:X®X, тогда, вообще говоря, f°g¹g°f. Пр.: f:a|®b, b|®a и g:a|®a, b|®a, X={a,b}, тогда f°g: a|®b, b|® b и g°f:a|®a, b|®a. 11) ] f:X®Y, g:Y®X, если f°g=eY и g°f=eX, то отображение g – обратное к f и обозначается f-1. 12) 1.] X – конечное мн-во, |X| - мощность мн-ва X и равна числу элементов этого мн-ва (#X=|X|); 2. мн-ва X и Y равномощны, если $j:X®Y: j– биективно; 3. мн-во X – счетное, если X и N – равномощны.
Утв.: Отображение f:X®Y – обратно Û f– биективно. ◄Для док-ва потребуется Лемма. L1: Если f:X®Y, g:Y®X, т.ч. f×g=eХ, то f– инъективно, g– сурьективно ■ Покажем, что f– инъективно. Допустим, что f– не инъективно, т.е. $ x,x¢ÎX, т.ч. f(x)=f(x¢) (x=x¢). Тогда x=eX(x)=g(f(x))=g(f(x¢))= =eX(x¢)=x¢, т.е. получено противоречие с условием допущения (x¹x¢), т.е. f– инъективно. Покажем, что g– сурьективно. ] xÎX (произвольное). Заметим, что x×eX(x)=g×f(x)=g(f(x))=x. Рассмотрим y=f(x)ÎY, тогда g(y)=g(f(x))=eX(x)=x Þ по определению g– сурьективно. ■ Докажем утверждение: ²Þ² т.е. из обратимости f Þ f– биективно. Но т.к. f– обратимо, то $ g:Y®X: g– обратное к f, т.е. f×g=eY и g×f=eX Þ по L1 g– инъективно и f– сурьективно (f×g=eY), g– сурьективно и f– инъективно (g×f=eX) Þ f– биективно. ²Ü² Покажем, что если f– биективно, то f– обратимо. Т.к. f– биективно, то "yÎY $!xÎX: f(x)=y. Рассмотрим отобр. g: Y®X (y|®x: f(x)=y). Но g×f(x)=g(y)=x, т.е. g×f=eX, и f×g(y)=f(x)=y, т.е. f×g=eY. По определению g – обр. отобр. к f, т.е. f– обратно►. Св-ва: 1. f: X®Y – биективно Þ f-1– биективно. 2. f:X®Y, h:Y®Z – биективное отображение (обратимо), тогда h°f– биективно (обратимо) и (h°f )-1=f--1°h-1◄Доказывается с помощью полной росписи определения биективности и обратимости►. Пр.: 1) Z, Q – счетные мн-ва, $ j: Z®N – биективно, $ g: Q®N – биективно, но NÌZÌQ (¹ ¹) ◄►. 2) R – несчетное мн-во.
Бинарные отношения на мн-вах. Отношение эквивалентности. Примеры.
Def: ] X и Y –мн-ва. Всякое подмножество OÌX´Y– бинарное отношение между мн-вами X и Y. Если Y=X, то OÌX´X – бинарное отношение на мн-ве X. Говорят, что эл-нт xÎX находится в отношении O с элементом yÎY, если (x,y)ÎO. Иногда в качестве отношения используют обозначение напр., S т.е. элементнт x находится в отн. S с эл-том y (обозн. xSy), если (x,y)ÎOSÌX´Y. Пр.:1. X=Y=R, рассмотрим отношение ²<². a<b, т.е. (a,b)ÎO ²<², если число a меньше b; O²<²={(a,b)| a,bÎR и a меньше b}.
r– обозначение отношения на X. Оr– само отношение на X (т.е. ОrÌX´X), (x,y)ÎОr. Пр.:2. Бинарное отношение на X, |X|=3. ]X={1,2,3}. Обозначим это отношение через r:
Def: Бинарное отношение ²~² на мн-ве X называется отношением эквивалентности, если 1) "xÎX x~x (т.е. (x,x)ÎO~)– рефлективность; 2) если x~y, то y~x (т.е. (x,y)ÎO~, то (y,x)ÎO~)– симметричность; 3) если x~y, y~z, то x~z (т.е. если (x,y)ÎO~ и (y,z)ÎO~, то (x,z)ÎO~)– транзитивность. Def: ] ²~² отношение эквивалентности на мн-ве X. Мн-во x={yÎX| y~x} называется классом эквивалентности, причем любой элемент из x– называется представителем класса эквивалентности. Утв.: ] ²~² – отношение эквивалентности на X, х и х¢ÎX, тогда x=x¢ Û x~x¢◄²Ü² ] x~x¢, пусть x²Îx, тогда из x²Îx Þ x²~x Þтранз x²~x¢ Þ x²Îx¢ Þ xÌx¢ . Т.к. из x~x¢ Þ x¢~x, то выполняя аналогичные преобразования получим x¢Ìx, т.е. x=x¢. ²Þ², т.е. xÎx и x¢Îx¢, то x~x¢(по определению). ► Из x=x¢ след.: a~x~x¢.
