Відношення лінійного та повного порядку

 

Відношенням лінійного порядку (лінійним порядком) на множині А називається такий частковий порядок на множині А, відносно якого порівнюються будь-які елементи х та у множини А. Множина, на якій задано лінійний порядок, називається лінійно упорядкованою, або упорядкованою, або ланцюгом.

Наприклад, лінійно упорядкованою є множина А ={1,2,3}, на якій задано частковий порядок R ={<1,1>,<2,2>,<3,3>,<1,3>,<3,2>,<1,2>}, оскільки R є лінійним порядком на А. Множина N з відношенням £ є лінійно упорядкованою. Дійсно, якими б не були невід’ємні цілі числа n та m, завжди принаймні одне з тверджень n £ m чи m £ n є істинним, тобто будь-які числа n та m з множини N порівнюються відносно часткового порядку £. Булеан множини { a, b, c }, на якому задано відношення включення, не є упорядкованою множиною, оскільки він містить елементи, що не порівнюються відносно Í (наприклад, { a } та { b }).

Нехай R – частковий порядок на множині А. Елемент х множини А називається мінімальним (максимальним) елементом відносно R, якщо для кожного елемента у множини А, що порівнюється з х, < x, y >Î R (< y, x >Î R).

Нехай, наприклад, на множині А ={1,2,3} задано частковий порядок R = і_А È{<2,1>,<3,1>}. Знайдемо мінімальні та максимальні елементи множини А відносно заданого порядку R. Елемент 1 порівнюється з елементами 1, 2, 3 й <1,1>, <2,1>, <3,1>Î R, отже, 1 є максимальним елементом відносно R. Елемент 2 порівнюється з елементами 1 та 2 й <2,2>, <2,1>Î R, отже, 2 є мінімальним елементом відносно R. Елемент 3 порівнюється з елементами 1 та 3 й <3,3>, <3,1>Î R, отже, 3 є мінімальним елементом відносно R. Розглянемо частковий порядок R ₁= і_А È{<3,1>,<1,2>,<3,2>} на множині А. Елемент 1 порівнюється з елемен-тами 1, 2, 3 й <1,1>, <1,2>Î R ₁, але <1,3>Ï R ₁, отже, елемент 1 не є мінімальним відносно R ₁. Елемент 1 не є також й максимальним відносно R ₁, тому що <1,1>,<3,1>Î R ₁, але <2,1>Ï R ₁. Мінімальним елементом відносно R ₁ є елемент 3, тому що для усіх елементів, з якими він порівнюється відносно R ₁ (тобто для 1, 2 та 3) <3,1>, <3,2>,<3,3>Î R ₁. Максимальним елементом відносно R ₁ є елемент 2, оскільки <1,2>, <2,2>,<3,2>Î R ₁.

Нехай R – частковий порядок на множині А. Елемент х множини А називається найменшим (найбільшим) елементом відносно R, якщо для кожного елемента у множини А < x, y >Î R (< y, x >Î R).

Нехай, наприклад, на множині А ={1,2,3} задано частковий порядок R = i_A È{<1,2>,<2,3>,<1,3>}. Найменшим відносно R є елемент 1, оскільки він порівнюється з кожним елементом множини А й <1,1>, <1,2>, <1,3>Î R. Найбільшим відносно R є елемент 3, бо він порівнюється з кожним елементом множини А й <1,3>, <2,3>, <3,3>Î R. Множина N, лінійно упорядкована відношенням £, має найменший елемент відносно £. Таким елементом є число 0. Дійсно, для будь-якого n Î N 0£ n. Водночас множина N не має найбільшого елемента відносно £. Дійсно, не існує невід’ємного цілого числа m такого, що для будь-якого n Î N n £ m. Множина Z, лінійно упоряд-кована відношенням £, не має ні найменшого, ні найбільшого елементу відносно £ (не існує такого цілого числа z, що для будь-якого х Î Z z £ х й не існує такого цілого числа у, що для будь-якого х Î Z х £ у). Множина N ^- усіх від’ємних цілих чисел, лінійно упорядкована відношенням £, має найбільший елемент відносно £ (число –1), але не має найменшого елементу відносно £.

Відношення лінійного порядку на множині А називається відношенням повного порядку (повним порядком) на А, якщо кожна непорожня підмножина множини А має найменший елемент відносно R. Множина А, на якій задано відношення повного порядку, називається повністю упорядкованою.

Прикладом відношення повного порядку є відношення £ на множині N. Дійсно, множина N має найменший елемент відносно £ (це число 0) й кожна непорожня підмножина А множини N містить таке число m, що m £ x для будь-якого х Î А. Відношення £ на множині Z не є повним порядком, адже Z не має найменшого елементу відносно £.

Наведемо без доведення один з важливих результатів теорії множин.

Теорема 10 (теорема Цермело). Будь-яку непорожню множину можна повністю упорядкувати.

 

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

 

І. Які з відношень завдань XXVIІ-XXІX до попереднього розділу є відношен-нями: 1) часткового порядку, 2) строгого порядку, 3) передпорядку, 4) лінійного порядку, 5) повного порядку.

ІІ. Побудувати частково упорядковану множину, яка має:

1) найменший елемент, максимальний елемент й не має найбільшого елементу;

2) мінімальний елемент й не має найменшого елемента;

3) два мінімальних та два максимальних елемента.

ІІІ. Побудувати відношення часткового порядку на множині:

1) мешканців одного міста;

2) трикутників на площині;

3) поліномів порядку n від однієї змінної;

4) спектаклів з репертуару одного театру;

5) назв населених пунктів України;

6) літаків, приписаних до одного аеропорту;

7) Z ².

IV. Побудувати:

1) на множині літер українського алфавіту частковий порядок, який не є лінійним;

2) відношення строгого порядку на множині студентів однієї групи;

3) передпорядок на множині студентів одного університету,

4) передпорядок на множині N ².

V. Побудувати відношення лінійного порядку на множині:

1) {+,-,*,­,!},

2) P({ а, b, cd },

3) N ²,

4) N È N ²,

5) комплексних чисел,

6) A ², де A ={ u, v, w, z, x },

7) слів орфографічного словника,

8) учнів школи,

9) країн світу.

VІ. Побудувати такий лінійний порядок R на множині натуральних чисел, що існує найбільший елемент відносно R.

VІІ. Побудувати повний порядок на множині:

1) вулиць Києва,

2) цілих від’ємних чисел,

3) цілих чисел Z.

VІІІ. Довести, що i_A є частковий порядок на множині А.

ІХ. Нехай £ _B, £ _A – часткові порядки на множинах B та A відповідно. Довести, що < a ₁, b ₁> £ < a ₂, b ₂> Û a ₁ £ _A a ₂ й b ₁ £ _B b ₂ – частковий порядок на A * B.

Х. Показати, що якщо відношення R на множині А іррефлексивне та транзитивне, то відношення R ₁ на А, таке що xR ₁ y Û xRy або x = y, є частковим порядком на А.

ХІ. Нехай A – непорожня частково упорядкована множина, що має n елементів. Довести, що А містить мінімальний та максимальний елементи.

ХІІ. 1) Нехай £ – частковий порядок на множині А. Визначимо на А відно-шення R: xRy Û x £ y й x ¹ y. Довести, що R – строгий порядок на А.

2) Нехай < – строгий порядок на множині А. Визначимо на А відношення R: xRy Û x < y або x = y. Довести, що R – частковий порядок на А.

3) Нехай Q – передпорядок на множині А. Визначимо на А відношення R: xRy Û хQу та < y, x >Ï Q. Довести, що R – строгий порядок на А.

4) Нехай Q – передпорядок на множині А. Визначимо на А відношення R: xRy Û хQу й yQx. Довести, що R – відношення еквівалентності на А.

ХІІІ. Довести, що будь-яка підмножина частково упорядкованої множини частково упорядкована.

 

 

ЛЕкція 4. Відображення

 

Поняття відображення

 

Відношення R, задане на множинах А та В, називається функціональним, якщо для кожного елемента x Î А існує не більше одного елемента y Î В такого, що < x, y >Î R. Іншими словами, у функціональному відношенні R, заданому на множинах А та В, кожен елемент множини А може бути (першим) компонентом не більш, як однієї пари, що належить R.

Наприклад, відношення R ={<1, b >,<3, a >,<4, b >}, задане на множинах A ={1,2,3,4} та B ={ a, b, c }, є функціональним, оскільки кожен з елементів 1,3,4 з множини А є першим компонентом лише однієї пари відношення R, а елемент 2 з множини А не є першим компонентом жодної пари відношення R. Відношення Q ={<1, a >,<1, b >,<2, c >}, задане на тих самих множинах А та В, не функціональне, тому що елемент 1 з множини А зустрічається двічі (тобто більше одного разу) на першому місці у парах, які належать Q. Не функціональними є також відношення < та £ на множині N, оскільки для кожного числа n з N існує не одне число m Î N таке, що n < m й n £ m.

Нехай R – відношення, задане на множинах А та В. Назвемо областю визначення відношення R (позначається D(R)) множину { x | x Î A, існує y Î В такий, що < x, y >Î R }. Областю значень відношення R (позначається R(R)) назвемо множину { y | y Î B, існує такий x Î A, що < x, y >Î R }.

Нехай, наприклад, R Í A ´ B, A ={1,2,3,4}, B ={1,3,5}, R ={<1,1>, <1,5>,<2,3>,<3,5>,<3,3>}. Тоді D(R)={1,2,3}, R(R)={1,3,5}.

Функціональне відношення F на множинах А та В назвемо відображенням множини А у множину В (або функцією з А у В), якщо D(F)= А. Функціональне відношення F на множинах А та В назвемо частковим відображенням множини А у множину В (або частковою функцією з А у В), якщо D(F)Ì А. Позначатимемо (часткове) відображення F множини А у множину В через F: А ® В. Якщо < a, b >Î F, то елемент b називають образом елементу а, елемент а – прообразом елементу b при відображенні F й пишуть b = F (a). Множина усіх відображень А у В позначається В^А.

Часто відображення множини A у множину B задається у вигляді F (x)= t (x), де x Î A, t (x) – деякий вираз. Наприклад, відображення F: N ® N, F ={< x, y >| x, y Î N, y =2 x }, можна задати у вигляді F (x)=2 x.

Відображення множини А у множину А називають перетворенням множини А.

Через F ^-1(b) позначимо множину { a | a Î A, F (a)= b }; F^-1(b) називається повним прообразом елементу b при відображенні F. Нехай F: А ® В й Х Í А. Образом множини Х при відображенні F (позначається F (Х)) назвемо множину { y | y Î B, F ^-1(y)¹Æ}.

Наведемо приклади відображень. Відношення F ={<1, a >,<2, a >,<3, c >, <4, d >,<5, d >}, задане на множинах А ={1,2,3,4,5} та В ={ a, b, c, d, e }, є відо-браженням А у В, тому що F функціональне й D(F)={1,2,3,4,5}= А. F ^-1(a)={1,2}, F ^-1(b)=Æ, F ^-1(c)={3}, F ^-1(d)={4,5}, F ^-1(e)=Æ, F (A)={ a, c, d }, F ({1,2,3})={ a, c }. Відно-шення Q ={<2, c >,<3, d >,<5, b >}, задане на тих самих множинах, є частковим відображенням А у В, тому що Q функціональне й D(Q)={2,3,5}Ì А.

Зауважимо, що коли F (F: A ® B) – відображення, то відношення F ^-1 може не бути відображенням. Розглянемо, наприклад, множини A ={1,2}, B ={ a, b } та відображення F ={<1, a >,<2, a >} А у В. F ^-1={< a,1>,< a,2>}. F ^-1 – нефункціональне відношення на множинах В та А, отже, F ^-1 не є відображенням В у А.

Якщо А = А ₁´…´ А_n, то (часткове) відображення F: А ® В називають (частковим) відображенням множини А ₁´…´ А_n у множину В (або (частковою) функцією з А ₁´…´ А_n у В).

Нехай, наприклад, A ₁={1,2,3}, A ₂={2,4}, A ₃={ a, b }, B ={ d, f, g }. Відношення F ={<1,4, a, f >,<2,2, a, d >,<1,2, b, f >,<3,2, a, d >}, задане на множинах А ₁, А ₂, А ₃, В, є частковим відображенням А ₁´ А ₂´ А ₃ у В. Відношення R ={<1,2, a, d >,<1,2, a, f >, <2,4, b, g >}, задане на тих самих множинах, не функціональне на множинах А ₁´ А ₂´ А ₃ та В, оскільки для елементу <1,2, a > множини А ₁´ А ₂´ А ₃ існує два (тобто більше одного) елемента у з множини В (це елементи d та f) таких, що <1,2, a, у >Î В, отже, R не є відображенням А ₁´ А ₂´ А ₃ у В.

Теорема 11. Довести, що для будь-якої функції F виконується:

1) F (A È B)= F (A)È F (B), 2) F (A Ç B) Í F (A)Ç F (B),

3) F (A)\ F (B)= F (A \ B), 4) A Í B Þ F (A)Í F (B),

5) F (A)=Æ Û A ÇD(F)=Æ, 6) F ^-1(A È B)= F ^-1(A)È F ^-1(B),

7) F ^-1(A Ç B)= F ^-1(A)Ç F ^-1(B), 8) F ^-1(A \ B)= F ^-1(A)\ F ^-1(B),

9) A Í B Þ F ^-1(A)Í F ^-1(B), 10) F ^-1(A)=Æ Û A ÇR(F)=Æ.

Доведемо перше твердження. Нехай x Î F (A È B). Тоді у множині A È B існує такий елемент у, що х = F (y); y Î A або у Î В. Розглянемо перший з цих випадків: y Î A Þ x Î F (A) Þ x Î F (A)È F (B). У випадку y Î B маємо: y Î В Þ x Î F (B) Þ x Î F (A)È F (B). Отже, F (A È B)Í F (A)È F (B). Нехай тепер х Î F (A)È F (B). Тоді x Î F (A) або x Î F (B). У випадку x Î F (A) у множині А існує такий елемент у, що х = F (y), але у Î А È В й тоді х Î F (A È B). Якщо x Î F (B), то у множині В існує такий елемент z, що х = F (z). Оскільки z Î B Þ z Î A È B, то х Î F (A È B). Таким чином, F (A)È F (B)Í F (A È B). Отже, F (A È B)= F (A)È F (B).

 

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

 

Відображення 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 >}.

 

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

 

І. Визначити, які з відображень є: а) частковими, б) сюр’єктивними,

в) ін’єктивними, г) взаємно однозначними. А ={ a, b, c, d }, B ={ b, c, d, f }.

1) F: A ® B, F ={< a, b >,< c, f >,< d, d >};

2) F: B ® A, F ={< c, b >,< f, a >,< d, a >,< b, c >};

3) F: B ® A, F ={< c, c >,< f, d >,< d, b >,< b, a >};

4) F: A ²® B, F ={<< a, a >, d >,<< a, b >, c >,<< c, c >, f >,<< c, b >, b >,<< c, d >, f >, << d, d >, d >, << d, a >, b >,<< b, a >, c >,<< d, c >, b >,<< c, a >, d >};

5) F: A ® B ², F ={< a,< b, c >>,< b,< c, d >>,< c,< d, d >>,< d,< c, d >>}.

II. Нехай А ={ a, b, c, d }, B ={1,2,3}. Побудувати:

1) 2-арну функцію з А у В, 2) 3-арну функцію з В у А,

3) тернарну операцію на В, 4) бінарний предикат на А,

5) матрицю розмірності 3´4 над А, 6) матрицю порядку 5 над В.

ІІІ. Побудувати:

1) функцію з N у Z, 2) 4-арну функцію з Q у R,

3) тернарну операцію на Z, 4) унарну операцію на Q,

5) бінарний предикат на R, 6) унарний предикат на N.

IV. Визначити, за яких умов:

1) n -арна функція з А у В є n -арною операцією на А,

2) n -арна функція з А у В є n -арним предикатом на А,

3) n -арна операція на А є n -арним предикатом на А,

4) бінарна операція на А є матрицею над А,

5) матриця порядку n над А є n -арною операцією на А,

6) матриця порядку n над А є n -арним предикатом на А.

V. Нехай f, g – функції. За яких умов:

1) f ^-1 є функцією, 2) f * g є взаємно однозначною функцією.

VI. Нехай існує взаємно однозначна відповідність між множинами А та В й між множинами С та D. Показати, що існує взаємно однозначна відповідність між множинами:

1) А ´ C та B ´ D, 2) А^C та B^D, 3) А È C та B È D, якщо А Ç C =Æ й B Ç D =Æ.

VII. Нехай A, B, C – множини. Побудувати взаємно однозначну відповідність між множинами:

1) A ´ B та B ´ A, 2) A ´(B ´ C) та (A ´ B)´ C,

3) (A ´ B)^C та A^C ´ B^C, 4) (A^B) ^C та A^{B ´ C},

5) A^{B È C} та A^B ´ A^C, якщо B Ç C =Æ.

VIII. Довести, що для того, щоб відношення R, задане на множинах А та В, було взаємно однозначною відповідністю між А та В, необхідно й достатньо, щоб R * R ^-1= i_А й R ^-1* R = i_В.

ІХ. Нехай F – взаємно однозначне відображення множини А на множину В, G – взаємно однозначне відображення множини В на множину С. Довести, що H = F * G є взаємно однозначне відображення А на С.

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

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).

XІ. На множинах 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 >}.

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

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

XII. Знайти область значень та область визначення відношення 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 >| 2 x ³3 y };

8) R Í[0,p]², R ={< x, y >| y ³cos x }.

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

1) B ¹Æ Þ D(А ´ В)= А, 2) А ¹Æ Þ R(А ´ В)= В,

3) В ¹Æ Þ В^А ¹Æ, 4) В^А Í В (А ´ В).

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

XV. Нехай 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).

XVI. Нехай f: A ® B, g: B ®C – відображення, x Î A. Визначити (f * g)(x).

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

1) D(R)=Æ Û R =Æ Û R(R)=Æ, 2) D(R ^-1)=R(R), 3) R(R ^-1)=D(R).

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

ХІХ. Нехай задано відображення f: A * A ® A таке, що для будь-яких елементів x, y, z множини A f (x, y)= f (y, x), f (x, f (y, z))= f (f (x, y), z), f (x, x)= x. Визначимо xRy Û f (x, y)= x. Довести, що R – частковий порядок на А.

ХХ. Нехай R – бінарне відношення на n -елементній множині А. Сформулювати правила перетворення матриці відношення R на матрицю відношення: 1) R_r; 2) R_s.

ХХІ. Нехай R – перетворення множини А. Чи будуть перетвореннями множини А відношення R_r, R_s, R_t?

XХІI. Для заданого відображення множини А ={ a, b, c, d } у множину В ={1,2,3,4,5} побудувати канонічний розклад.

1) F ={< a,1>,< b,2>,< c,2>,< d,1>}, 2) F ={< a,2>,< b,2>,< c,2>,< d,2>},

3) F={<a,3>,<b,5>,<c,4>,<d,1>}, 4) F={<a,1>,<b,2>,<c,3>,<d,4>},

5) F ={< a,1>,< b,1>,< c,2>,< d,3>}, 6) F ={< a,3>,< b,5>,< c,5>,< d,5>}.