Відношення лінійного та повного порядку
Відношенням лінійного порядку (лінійним порядком) на множині А називається такий частковий порядок на множині А, відносно якого порівнюються будь-які елементи х та у множини А. Множина, на якій задано лінійний порядок, називається лінійно упорядкованою, або упорядкованою, або ланцюгом.
Наприклад, лінійно упорядкованою є множина А={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. Розглянемо частковий порядок R1=іАÈ{<3,1>,<1,2>,<3,2>} на множині А. Елемент 1 порівнюється з елемен-тами 1, 2, 3 й <1,1>, <1,2>ÎR1, але <1,3>ÏR1, отже, елемент 1 не є мінімальним відносно R1. Елемент 1 не є також й максимальним відносно R1, тому що <1,1>,<3,1>ÎR1, але <2,1>ÏR1. Мінімальним елементом відносно R1 є елемент 3, тому що для усіх елементів, з якими він порівнюється відносно R1 (тобто для 1, 2 та 3) <3,1>, <3,2>,<3,3>ÎR1. Максимальним елементом відносно R1 є елемент 2, оскільки <1,2>, <2,2>,<3,2>ÎR1.
Нехай 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) Z2.
IV. Побудувати:
1) на множині літер українського алфавіту частковий порядок, який не є лінійним;
2) відношення строгого порядку на множині студентів однієї групи;
3) передпорядок на множині студентів одного університету,
4) передпорядок на множині N2.
V. Побудувати відношення лінійного порядку на множині:
1) {+,-,*,,!},
2) P({а,b,cd},
3) N2,
4) NÈN2,
5) комплексних чисел,
6) A2, де A={u,v,w,z,x},
7) слів орфографічного словника,
8) учнів школи,
9) країн світу.
VІ. Побудувати такий лінійний порядок R на множині натуральних чисел, що існує найбільший елемент відносно R.
VІІ. Побудувати повний порядок на множині:
1) вулиць Києва,
2) цілих від’ємних чисел,
3) цілих чисел Z.
VІІІ. Довести, що iA є частковий порядок на множині А.
ІХ. Нехай £B, £A – часткові порядки на множинах B та A відповідно. Довести, що <a1,b1> £ <a2,b2> Û a1 £A a2 й b1 £B b2 – частковий порядок на A*B.
Х. Показати, що якщо відношення R на множині А іррефлексивне та транзитивне, то відношення R1 на А, таке що xR1y Û 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=2x}, можна задати у вигляді F(x)=2x.
Відображення множини А у множину А називають перетворенням множини А.
Через 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 у В).
Нехай, наприклад, A1={1,2,3}, A2={2,4}, A3={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 є відображення А на В. Нехай F1:А®В, F1={<1,a>,<2,c>,<3,c>,<4,a>}. Оскільки F1-1(b)=Æ, F1 не є відображенням 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>}. Відображення F1={<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 – взаємно однозначне відображення. Відображення F1={<1,a>,<2,c>,<3,a>} множини Х={1,2,3} у множину Y={a,c} не ін’єктивне, хоча є відображенням Х на Y, отже F1 не є взаємно однозначним. Взаємно однозначним є відображення 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: An®B (nÎN+) назвемо n-арною функцією з А у В. Будемо позначати n-арну функцію через Fn. Відображення виду Fn: An®А (nÎN) називається n-арною операцією на множині А. При n=0 операція називається нульарною. Така операція фіксує у множині А деякий елемент а, тобто F0ºa для деякого аÎА. При n=1 операція називається унарною; F1 є відображенням множини А у себе. При n=2 операція називається бінарною; при n=3 операція називається тернарною.
Прикладом 2-арної функції з А={1,2} у В={a,b,c} є відображення F2={<<1,1>,c>,<<1,2>,a>,<<2,1>,a>,<<2,2>,b>}. Оскільки А¹В, дане відобра-ження F2 не є бінарною операцією на множині А. Прикладами бінарних опе-рацій на множині 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. Наприклад, нехай А={a1,a2,a3}, B={b1,b2}, RÍA´B, R={<a2,b1>,<a1,b2>}. Тоді
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:A2®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®B2, 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} задані відношення. Які з них є: а) функціональними, б) відображеннями А у В?
R1={<1,c>,<1,b>,<3,a>,<3,c>,<2,b>}, R2={<2,b>,<3,c>,<1,b>},
R3={<4,a>,<3,a>,<1,c>,<5,c>,<2,a>}, R4={<1,a>,<3,a>,<4,a>},
R5={<2,a>,<5,b>,<4,c>,<1,a>,<2,b>}, R6={<2,a>,<2,b>,<2,c>},
R7={<3,b>,<4,a>,<5,c>,<4,b>}, R8={<1,c>,<5,a>,<2,b},
R9=R5\R8, R10={<2,a>}.
Скільки відношень існує на множинах: а) А та В? б) В та А?
Скільки існує відображень: а) А у В? б) В у А?
XII. Знайти область значень та область визначення відношення R.
1) RÍN2, R={<x,y>| x ділить y};
2) RÍN2, R={<x,y>| y ділить x};
3) RÍR2, R={<x,y>| x-y=5};
4) RÍR2, R={<x,y>| x+y£0};
5) RÍQ2, R={<x,y>| x>0, x´y<3};
6) RÍR2, R={<x,y>| x+y£0};
7) RÍR2, R={<x,y>| 2x³3y};
8) RÍ[0,p]2, R={<x,y>| y³cosx}.
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>}.