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

Відображення 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)=2 x множини додатних цілих чисел у множину додатних парних чисел.

Теорема 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 >}.