Відображення F множини А у множину В називається відображенням А на В (або сюр’єктивним відображенням, або сюр’єкцією), якщо F-1(b)¹Æ для будь-якого елементу b з множини В, тобто якщо кожний елемент b з множини В має принаймні один прообраз.
Нехай, наприклад, А={1,2,3,4}, B={a,b,c}, F:A®B, F={<1,b>,<4,a>,<2,c>, <3,a>}. Обчислимо F-1(y) для кожного елемента у множини В. Маємо:
F-1(a)={3,4}, F-1(b)={1}, F-1(c)={2}.
Таким чином, для кожного yÎВ F-1(у)¹Æ, отже, F є відображення А на В. Нехай F1:А®В, F1={<1,a>,<2,c>,<3,c>,<4,a>}. Оскільки F1-1(b)=Æ, F1 не є відображенням A на B.
Відображення F множини А у множину В називається ін’єктивним (або ін’єкцією), якщо для будь-яких елементів х та у з множини А з х¹у випливає F(x)¹F(y), тобто різні елементи з області значень відображення мають різні образи.
Прикладом ін’єктивного відображення множини A={a,b,c,d} у множину B={1,2,3,4,5} є відображення F={<a,3>,<b,1>,<c,2>,<d,4>}. Відображення F1={<a,1>,<b,2>,<c,2>,<d,3>} А у В не ін’єктивне, тому що різні елементи b та с мають однакові образи.
Відображення F множини А на множину В називається взаємно однозначним (взаємно однозначною відповідністю між А та В, взаємно однозначною функцією з А у В, бієкцією), якщо F ін’єктивне.
Нехай, наприклад, F:A®B, A={1,2,3,4}, B={a,b,c,d}, F={<1,a>, <2,b>,<3,c>,<4,d>}. Відношення F є відображенням А на В, оскільки кожен елемент множини В має прообраз; крім того, різні елементи множини А мають різні образи, отже, F є ін’єктивним. Таким чином, F – взаємно однозначне відображення. Відображення F1={<1,a>,<2,c>,<3,a>} множини Х={1,2,3} у множину Y={a,c} не ін’єктивне, хоча є відображенням Х на Y, отже F1 не є взаємно однозначним. Взаємно однозначним є відображення F(x)=2x множини додатних цілих чисел у множину додатних парних чисел.
Теорема 12. Нехай F: A®B – взаємно однозначне відображення. Тоді F-1 – взаємно однозначне відображення В на А.
Доведення. Покажемо, що F-1 – функціональне відношення на множинах В та А. Припустимо, що це не так. Тоді існує такий елемент b у множині В, що для деяких різних елементів х та у з множини А <b,x>ÎF-1 та <b,y>ÎF-1. Звідси маємо: <x,b>ÎF, <y,b>ÎF, тобто різні елементи множини А мають однакові образи, отже, F не ін’єктивне, але це суперечить умові. Таким чином, відношення F-1 функціональне. Покажемо, що D(F-1)=В. Припустимо, що це не так. Тоді у множині В є елемент b такий, що <b,x>ÏF-1 для усіх елементів х з А. А це означає, що F-1(b)=Æ, отже, F не є відображення А на В, що суперечить умові. Таким чином, F-1 – відображення В у А. Покажемо, що відображення F-1 сюр’єктивне. Припустимо, що це не так. Тоді існує елемент аÎА такий, що (F-1)-1(а)=Æ. Це означає, що "bÎB <b,a>ÏF-1, отже, "bÎB <а,b>ÏF, тобто D(F)¹A, що суперечить умові. Таким чином, F-1 сюр’єктивне. Покажемо, що F-1 ін’єктивне. Припустимо, що це не так. Тоді у множині В існують такі різні елементи a та b, що F-1(a)=F-1(b)=с, де сÎА. Це означає, що <c,a>ÎF та <c,b>ÎF, що суперечить функціональності F. Отже, F-1 ін’єктивне. Таким чином, F-1 – взаємно однозначне відображення В на А.
Відображення виду F: An®B (nÎN+) назвемо n-арною функцією з А у В. Будемо позначати n-арну функцію через Fn. Відображення виду Fn: An®А (nÎN) називається n-арною операцією на множині А. При n=0 операція називається нульарною. Така операція фіксує у множині А деякий елемент а, тобто F0ºa для деякого аÎА. При n=1 операція називається унарною; F1 є відображенням множини А у себе. При n=2 операція називається бінарною; при n=3 операція називається тернарною.
Прикладом 2-арної функції з А={1,2} у В={a,b,c} є відображення F2={<<1,1>,c>,<<1,2>,a>,<<2,1>,a>,<<2,2>,b>}. Оскільки А¹В, дане відобра-ження F2 не є бінарною операцією на множині А. Прикладами бінарних опе-рацій на множині Z є додавання, множення, віднімання. Прикладом унарної операції на множині N є факторіал (!). Оскільки не для усіх невід’ємних цілих чисел n та m (n-m)ÎN, віднімання не є бінарною операцією на N.
Відображення виду F: An®{0,1} (nÎN+) називається n-арним преди-катом на множині А.
Нехай, наприклад, А={a,b}. Відображення F={<<a,a>,1>,<<a,b>,0>, <<b,a>,0>,<<b,b>,1>} множини А2 у множину {0,1} є бінарним предикатом на множині А.
Нехай n,mÎN+, Nn, Nm означають множини чисел виду {1,2,..,n} та {1,2….,m}, S довільна множина чисел. Відображення A:Nn´Nm®S називається прямокутною матрицею (матрицею розмірності n´m) над множиною S. Образ A(i,j) пари <i,j> позначають aij й називають елементом матриці А. Матрицю А зображують у вигляді таблиці, що має n рядків та m стовпчиків, на перетині і-го рядка та j-го стовпчика знаходиться елемент aij. Якщо n=m, то матриця А називається квадратною (матрицею порядку n). Якщо у квадратній матриці aij=0 при i¹j й aij¹0 при i=j, то така матриця називається діагональною. Діагональна матриця називається одиничною, якщо aiі=1, iÎ{1,…,n}.
Наприклад, матрицею розмірності 2´3 над множиною {0,1,2,3} є відображення
Відображення {<<1,1>,3>,<<1,2>,1>,<<2,1>,0>,<<2,2>,3>} є квадратною матрицею (порядку 2) над множиною {0,1,2,3}. Відображення {<<1,1>,2>, <<1,2>,0>,<<2,1>,0>,<<2,2>,3>} є діагональною матрицею порядку 2 над множиною {0,1,2,3}, а відображення {<<1,1>,1>, <<1,2>,0>,<<2,1>,0>, <<2,2>,1>} – одиничною матрицею.
Матриця є зручним способом подання відношень, заданих на скінченних множинах А та В. Нехай множина А містить n елементів, множина В – m елементів. Позначимо елементи множин А та В через xi та yj (iÎNn, jÎNm). Нехай R – відношення, задане на множинах А та В. Тоді R подається матрицею виду АR:Nn´Nm®{0,1}, заданою таким чином: аij=1, якщо <xi,yj>ÎR, aij=0, якщо <xi,yj>ÏR. Наприклад, нехай А={a1,a2,a3}, B={b1,b2}, RÍA´B, R={<a2,b1>,<a1,b2>}. Тоді
За допомогою відношень еквівалентності на деякій множині А та фактор-множин цієї множини можна описати відображення множини А у інші множини.
Теорема 13. Будь-яке відображення F:A®B є композицією P*B*i відображень Р, В та і, де Р:А®А/R для деякого відношення еквівалентності R на А, В – деяке взаємно однозначне відображення А/R на F(A), і – тотожне відображення F(A) у В.
Доведення. Побудуємо бінарне відношення R за відображенням F таким чином: хRу Û F(х)=F(у). Покажемо, що R є відношенням еквівалентності. Оскільки F(х)=F(х) для будь-якого елементу х множини А, то хRх для кожного х з А, отже, R рефлексивне. R симетричне, тому що хRу Þ F(х)=F(у) Þ F(у)=F(х) Þ уRх. R транзитивне, бо хRу, уRz Þ F(x)=F(y), F(y)=F(z) Þ F(x)=F(z) Þ xRz. Визначимо відображення Р:А®А/R, В:А/R®F(A), і:F(A)®В таким чином: Р={<х,[x]>| xÎA, [x]ÎA/R}, В={<[x],F(x)>| xÎA}, i={<x,x>| xÎF(A)}. (Нагадаємо, що [x] означає клас еквівалентності, який містить х.) Неважко перевірити, що відображення В є взаємно однозначним, а Р*В*і – відображенням А у В. Покажемо, що F(x)=(Р*В*і)(х). За визначеннями Р, В та і маємо: (Р*В*і)(х) = і(В(Р(х))) = і(В([x])) = i(F(x)) = F(x). Отже, F=P*B*i.
Рівність F=P*B*i називається канонічним розкладом F.
Нехай, наприклад, А={1,2,3,4,5}, B={a,b,c,d}, F:A®B, F={<1,b>,<2,c>, <3,a>,<4,c>,<5,a>}. Знайдемо відображення Р, В та і для канонічного розкла-ду відображення F. Визначимо за F, як показано у доведенні теореми 13, від-ношення еквівалентності RF=iAÈ{<2,4>,<4,2>,<3,5>, <5,3>} та відповідну фактор-множину A/RF={{1},{2,4},{3,5}}. Тоді [1]={1}, [2]=[4]={2,4}, [3]=[5]={3,5}. Отже:
