Задачі та вправи

І. Побудувати приклади відображень та часткових відображень:

1) {a,b,c,d} у {g,h}, 2) {1,2,3} у {x,y,z,v,w}, 3) {1,2,3} у N,

4) N у Q, 5) Q у N, 6) Q у R,

7) R у N, 8) R у Q, 9) NN у R,

10) A={a,b,c} у P(A).

ІІ. На множинах A={1,2,3,4,5} та B={a,b,c} задані відношення. Які з них є: а) функціональними, б) відображеннями А у В?

R₁={<1,c>,<1,b>,<3,a>,<3,c>,<2,b>}, R₂={<2,b>,<3,c>,<1,b>},

R₃={<4,a>,<3,a>,<1,c>,<5,c>,<2,a>}, R₄={<1,a>,<3,a>,<4,a>},

R₅={<2,a>,<5,b>,<4,c>,<1,a>,<2,b>}, R₆={<2,a>,<2,b>,<2,c>},

R₇={<3,b>,<4,a>,<5,c>,<4,b>}, R₈={<1,c>,<5,a>,<2,b},

R₉=R₅\R₈, R₁₀={<2,a>}.

Скільки відношень існує на множинах: а) А та В? б) В та А?

Скільки існує відображень: а) А у В? б) В у А?

III. Знайти область значень та область визначення відношення R.

1) RN², R={<x,y>| x ділить y};

2) RN², R={<x,y>| y ділить x};

3) RR², R={<x,y>| x-y=5};

4) RR², R={<x,y>| x+y0};

5) RQ², R={<x,y>| x>0, xy<3};

6) RR², R={<x,y>| x+y0};

7) RR², R={<x,y>| 2x3y};

8) R[0,]², R={<x,y>| ycosx}.

ІV. Довести, що:

1) B  D(АВ)=А, 2) А  R(АВ)=В,

3) В  В^А, 4) В^АВ(АВ).

V. Довести твердження 2-10 теoреми 6.

VI. Нехай AD(F), BR(F) для деякого відображення F. Довести, що:

1) AF^-1(F(A)), 2) F(F^-1(B))=B, 3) F(A)B=F(AF^-1(B)), 4) F(A)B=  AF^-1(B)=, 5) F(A)B  AF^-1(B).

VII. Нехай f: AB, g: BC – відображення, xA. Визначити (fg)(x).

VIII. Довести, що для будь-якого бінарного відношення R:

1) D(R)=  R=  R(R)=, 2) D(R^-1)=R(R), 3) R(R^-1)=D(R).

ІХ. Нехай F, G – (часткові) відображення A у B. Довести, що F=G  D(F)=D(G), R(F)=R(G), для кожного елемента x з області визначення F та G F(x)=G(x).

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

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

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