Види відображень

Відображення 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 є відображення А на В. Нехай F₁:А®В, F₁={<1,a>,<2,c>,<3,c>,<4,a>}. Оскільки F₁^-1(b)=Æ, F₁ не є відображенням 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>}. Відображення F₁={<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 – взаємно однозначне відображення. Відображення F₁={<1,a>,<2,c>,<3,a>} множини Х={1,2,3} у множину Y={a,c} не ін’єктивне, хоча є відображенням Х на Y, отже F₁ не є взаємно однозначним. Взаємно однозначним є відображення 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: Aⁿ®B (nÎN⁺) назвемо n-арною функцією з А у В. Будемо позначати n-арну функцію через Fⁿ. Відображення виду Fⁿ: Aⁿ®А (nÎN) називається n-арною операцією на множині А. При n=0 операція називається нульарною. Така операція фіксує у множині А деякий елемент а, тобто F⁰ºa для деякого аÎА. При n=1 операція називається унарною; F¹ є відображенням множини А у себе. При n=2 операція називається бінарною; при n=3 операція називається тернарною.

Прикладом 2-арної функції з А={1,2} у В={a,b,c} є відображення F²={<<1,1>,c>,<<1,2>,a>,<<2,1>,a>,<<2,2>,b>}. Оскільки А¹В, дане відобра-ження F² не є бінарною операцією на множині А. Прикладами бінарних опе-рацій на множині Z є додавання, множення, віднімання. Прикладом унарної операції на множині N є факторіал (!). Оскільки не для усіх невід’ємних цілих чисел n та m (n-m)ÎN, віднімання не є бінарною операцією на N.

Відображення виду F: Aⁿ®{0,1} (nÎN⁺) називається n-арним преди-катом на множині А.

Нехай, наприклад, А={a,b}. Відображення F={<<a,a>,1>,<<a,b>,0>, <<b,a>,0>,<<b,b>,1>} множини А² у множину {0,1} є бінарним предикатом на множині А.

Нехай n,mÎN⁺, N_n, N_m означають множини чисел виду {1,2,..,n} та {1,2….,m}, S довільна множина чисел. Відображення A:N_n´N_m®S називається прямокутною матрицею (матрицею розмірності n´m) над множиною S. Образ A(i,j) пари <i,j> позначають a_ij й називають елементом матриці А. Матрицю А зображують у вигляді таблиці, що має n рядків та m стовпчиків, на перетині і-го рядка та j-го стовпчика знаходиться елемент a_ij. Якщо n=m, то матриця А називається квадратною (матрицею порядку n). Якщо у квадратній матриці a_ij=0 при i¹j й a_ij¹0 при i=j, то така матриця називається діагональною. Діагональна матриця називається одиничною, якщо a_iі=1, iÎ{1,…,n}.

Наприклад, матрицею розмірності 2´3 над множиною {0,1,2,3} є відображення

А={<<1,1>,3>,<<1,2>,1>,<<1,3>,1>,<<2,1>,2>,<<2,2>,3>,<<2,3>,0>}.

Відображення {<<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 елементів. Позначимо елементи множин А та В через x_i та y_j (iÎN_n, jÎN_m). Нехай R – відношення, задане на множинах А та В. Тоді R подається матрицею виду А_R:N_n´N_m®{0,1}, заданою таким чином: а_ij=1, якщо <x_i,y_j>ÎR, a_ij=0, якщо <x_i,y_j>ÏR. Наприклад, нехай А={a₁,a₂,a₃}, B={b₁,b₂}, RÍA´B, R={<a₂,b₁>,<a₁,b₂>}. Тоді

A_R={<<1,1>,0>,<<1,2>,1>,<<2,1>,1>,<<2,2>,0>, <<3,1>,0>,<<3,2>,0>}

За допомогою відношень еквівалентності на деякій множині А та фактор-множин цієї множини можна описати відображення множини А у інші множини.

Теорема 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, від-ношення еквівалентності R_F=i_AÈ{<2,4>,<4,2>,<3,5>, <5,3>} та відповідну фактор-множину A/R_F={{1},{2,4},{3,5}}. Тоді [1]={1}, [2]=[4]={2,4}, [3]=[5]={3,5}. Отже:

Р={<1,{1}>,<2,{2,4}>,<3,{3,5}>,<4,{2,4}>,<5,{3,5}>},

B={<{1},b>,<{2,4},c>,<{3,5},a>},

i={<a,a>,<b,b>,<c,c>}.