Відношенням лінійного порядку (лінійним порядком) на множині А називається такий частковий порядок на множині А, відносно якого порівнюються будь-які елементи х та у множини А. Множина, на якій задано лінійний порядок, називається лінійно упорядкованою, або упорядкованою, або ланцюгом.
Наприклад, лінійно упорядкованою є множина А ={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 1= іА È{<3,1>,<1,2>,<3,2>} на множині А. Елемент 1 порівнюється з елемен-тами 1, 2, 3 й <1,1>, <1,2>Î R 1, але <1,3>Ï R 1, отже, елемент 1 не є мінімальним відносно R 1. Елемент 1 не є також й максимальним відносно R 1, тому що <1,1>,<3,1>Î R 1, але <2,1>Ï R 1. Мінімальним елементом відносно R 1 є елемент 3, тому що для усіх елементів, з якими він порівнюється відносно R 1 (тобто для 1, 2 та 3) <3,1>, <3,2>,<3,3>Î R 1. Максимальним елементом відносно R 1 є елемент 2, оскільки <1,2>, <2,2>,<3,2>Î R 1.
Нехай R – частковий порядок на множині А. Елемент х множини А називається найменшим (найбільшим) елементом відносно R, якщо для кожного елемента у множини А < x, y >Î R (< y, x >Î R).
Нехай, наприклад, на множині А ={1,2,3} задано частковий порядок R = iA È{<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 2.
IV. Побудувати:
1) на множині літер українського алфавіту частковий порядок, який не є лінійним;
2) відношення строгого порядку на множині студентів однієї групи;
3) передпорядок на множині студентів одного університету,
4) передпорядок на множині N 2.
V. Побудувати відношення лінійного порядку на множині:
1) {+,-,*,,!},
2) P({ а, b, cd },
3) N 2,
4) N È N 2,
5) комплексних чисел,
6) A 2, де A ={ u, v, w, z, x },
7) слів орфографічного словника,
8) учнів школи,
9) країн світу.
VІ. Побудувати такий лінійний порядок R на множині натуральних чисел, що існує найбільший елемент відносно R.
VІІ. Побудувати повний порядок на множині:
1) вулиць Києва,
2) цілих від’ємних чисел,
3) цілих чисел Z.
VІІІ. Довести, що iA є частковий порядок на множині А.
ІХ. Нехай £ B, £ A – часткові порядки на множинах B та A відповідно. Довести, що < a 1, b 1> £ < a 2, b 2> Û a 1 £ A a 2 й b 1 £ B b 2 – частковий порядок на A * B.
Х. Показати, що якщо відношення R на множині А іррефлексивне та транзитивне, то відношення R 1 на А, таке що xR 1 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 не є відображенням В у А.
Якщо А = А 1´…´ Аn, то (часткове) відображення F: А ® В називають (частковим) відображенням множини А 1´…´ Аn у множину В (або (частковою) функцією з А 1´…´ Аn у В).
Нехай, наприклад, A 1={1,2,3}, A 2={2,4}, A 3={ a, b }, B ={ d, f, g }. Відношення F ={<1,4, a, f >,<2,2, a, d >,<1,2, b, f >,<3,2, a, d >}, задане на множинах А 1, А 2, А 3, В, є частковим відображенням А 1´ А 2´ А 3 у В. Відношення R ={<1,2, a, d >,<1,2, a, f >, <2,4, b, g >}, задане на тих самих множинах, не функціональне на множинах А 1´ А 2´ А 3 та В, оскільки для елементу <1,2, a > множини А 1´ А 2´ А 3 існує два (тобто більше одного) елемента у з множини В (це елементи d та f) таких, що <1,2, a, у >Î В, отже, R не є відображенням А 1´ А 2´ А 3 у В.
Теорема 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 1: А ® В, F 1={<1, a >,<2, c >,<3, c >,<4, a >}. Оскільки F 1-1(b)=Æ, F 1 не є відображенням 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 1={< 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={<1, a >,<2, c >,<3, a >} множини Х ={1,2,3} у множину Y ={ a, c } не ін’єктивне, хоча є відображенням Х на Y, отже F 1 не є взаємно однозначним. Взаємно однозначним є відображення 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: An ® B (n Î N +) назвемо n-арною функцією з А у В. Будемо позначати n-арну функцію через Fn. Відображення виду Fn: An ® А (n Î N) називається n-арною операцією на множині А. При n =0 операція називається нульарною. Така операція фіксує у множині А деякий елемент а, тобто F 0º a для деякого а Î А. При n =1 операція називається унарною; F 1 є відображенням множини А у себе. При n =2 операція називається бінарною; при n =3 операція називається тернарною.
Прикладом 2-арної функції з А ={1,2} у В ={ a, b, c } є відображення F 2={<<1,1>, c >,<<1,2>, a >,<<2,1>, a >,<<2,2>, b >}. Оскільки А ¹ В, дане відобра-ження F 2 не є бінарною операцією на множині А. Прикладами бінарних опе-рацій на множині 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>,<<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 елементів. Позначимо елементи множин А та В через xi та yj (i Î Nn, j Î Nm). Нехай R – відношення, задане на множинах А та В. Тоді R подається матрицею виду АR: Nn ´ Nm ®{0,1}, заданою таким чином: аij =1, якщо < xi, yj >Î R, aij =0, якщо < xi, yj >Ï R. Наприклад, нехай А ={ a 1, a 2, a 3}, B ={ b 1, b 2}, R Í A ´ B, R ={< a 2, b 1>,< a 1, b 2>}. Тоді
AR ={<<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, від-ношення еквівалентності 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}. Отже:
Р ={<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 2® 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 2, 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 та BD, 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 та AC ´ BC, 4) (AB) C та AB ´ C,
5) AB È C та AB ´ AC, якщо 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={<1, c >,<1, b >,<3, a >,<3, c >,<2, b >}, R 2={<2, b >,<3, c >,<1, b >},
R 3={<4, a >,<3, a >,<1, c >,<5, c >,<2, a >}, R 4={<1, a >,<3, a >,<4, a >},
R 5={<2, a >,<5, b >,<4, c >,<1, a >,<2, b >}, R 6={<2, a >,<2, b >,<2, c >},
R 7={<3, b >,<4, a >,<5, c >,<4, b >}, R 8={<1, c >,<5, a >,<2, b },
R 9= R 5\ R 8, R 10={<2, a >}.
Скільки відношень існує на множинах: а) А та В? б) В та А?
Скільки існує відображень: а) А у В? б) В у А?
XII. Знайти область значень та область визначення відношення R.
1) R Í N 2, R ={< x, y >| x ділить y };
2) R Í N 2, R ={< x, y >| y ділить x };
3) R Í R 2, R ={< x, y >| x - y =5};
4) R Í R 2, R ={< x, y >| x + y £0};
5) R Í Q 2, R ={< x, y >| x >0, x ´ y <3};
6) R Í R 2, R ={< x, y >| x + y £0};
7) R Í R 2, R ={< x, y >| 2 x ³3 y };
8) R Í[0,p]2, 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) Rr; 2) Rs.
ХХІ. Нехай R – перетворення множини А. Чи будуть перетвореннями множини А відношення Rr, Rs, Rt?
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>}.
