2.3. Класи еквівалентності
Проаналізуємо більш ретельно останній приклад. Елементи множини {. . . ,-9,-6,-3, 0, 3, 6, 9, . . .} знаходятья у відношенні R один з одним, але не знаходяться в тому ж відношенні з жодним іншим цілим числом. Те ж саме явище спостерігаємо у множинах
{. . . ,-8,-5,-2, 1, 4, 7, . . .} і {. . . ,-7,-4,-1, 2, 5, 8, . . .}.
Іншими словами відношення R розбиває множину Z на підмножини без спільних елементів. Узагальнимо цей випадок.
Нехай R є відношення еквівалентності на множині A.
Означення 2.3.1. Для ( a ( A множина [a] = {b ( A : (a, b) ( R} називається класом еквівалентності A, що містить елемент a.
Лема 2A. Припустимо, що R є відношення еквівалентності на множині A і що a, b ( A. Тоді b ( [a]
тоді і тільки тоді коли [a] = [b].
Доведення. (() Припустимо, що b ( [a]. Тоді (a, b) ( R. Ми покажемо що [a] = [b] довівши, що (1)
[b] ( [a] і (2) [a] ( [b]. Щоб довести (1), візьмемо довільне c ( [b]. Тоді (b, c) ( R. По властивості транзитивностіIt маємо (a, c) ( R, так що c ( [a]. Звідси і слідує (1). Щоб довести (2), припустимо що c ( [a]. Тоді (a, c) ( R. Так як (a, b) ( R, по властивості симетричності маємо (b, a) ( R. Тепер по транзитивності заключаємо,
що (b, c) ( R, так що c ( [b]. (2) доведено.
(() Припустимо, що [a] = [b]. По рефлективності маємо (b, b) ( R, так що b ( [b], а значить і b ( [a].
LEMMA 2B. Припустимо, що R є відношення еквівалентності на множині A і що a, b ( A. Тоді або [a] ( [b] = (, або [a] = [b].
Доведення. Припусти [a] ( [b] ( ( і с ( [a] ( [b] . З Lemma 2A слідує, що [c] = [a] і [c] = [b], так що [a] = [b].
На основі цих лем одержимо наступну
ТЕОРЕМА 2C. Припустимо, що R є відношення еквівалентності на множині A. Тоді A є обєднання різних класів еквівалентності без спільних елементів.
Приклад 2.3.1. Нехай m ( N. Визначимо відношення в Z написавши x ( y (mod m) якщо x - y є кратним m. Неважко перевірити, що це буде відношенням еквівалентності і що Z розпадається на класи еквівалентності [0], [1], . . . , [m - 1]. Вони називаються класи еквівалентності по модулю m, а множина таких класів позначається Zm.
2.4. Функції
Нехай A і B множиниe. Функція (або відображення) f з A в B ставить у відповідність кожному елементу x ( A єдиний елемент f(x) ( B. Пишуть f : A ( B. A називають областю визначення f, a B областю значень. Елемент f(x) називають образом x .Далі, множина f(B) = {y ( B : y = f(x) для деякого x ( A}називається образом f.
Дві функції f : A (( B and g : A ( B вважаються рівними і позначаються f = g, якщо f(x) = g(x) для кожного x ( A. Часто функцію зручно представляти її графіком G. Графік визначається як G = {(x, f(x)) : x ( A} = {(x, y) : x ( A і y = f(x) ( B}.
Приклад 2.4.1. Розглянемо функцію f : N ( N визначену як f(x) = 2x для кожного x ( N. Тоді область визначення функції f є N, а образ f є множина всіх парних чисел.
Приклад 2.4.2. Розглянемо функцію f : Z ( Z : x ( |x|. Тут областю визначення є множина цілих чисел, а образом функції є множина невід’ємних цілих чисел.
Приклад 2.4.3. Існують всього чотири функції з {a, b} в {1, 2}. Запишіть їх.
Приклад 2.4.4. Припустимо, що A і B є скінчені множини відповідно з n і m елементами. Цікаво знати, скільки існує різних функцій f : A ( B. Так як природа елементів множин для відповіді на поставлене питання не має значення, для полегшення міркувань позначимо їх просто натуральними числами A = {1, 2, . . . , n}. Тоді існує m різних способів вибрати значення для f(1) з елементів B. Для кожного з цих способів вибору f(1) знову є m різних способів вибрати значення для f(2) з елементів B. Для кожного такого вибору значень f(1) і f(2) знову існує m різних способів вибору для f(3) з елементів B. І так далі. Звідси слідує, що число різних функцій f : A ( B , що можна утворити є число способів вибору (f(1), . . . , f(n)), а це є
Приклад 2.4.2 показує, що функція може відображати різні елементи А в одні і ті ж самі елементи В. Також, не всі елементи В є образами елементів А.
Означення. Функція f : A ( B називається ін’єктивною, якщо різним значенням x1 ( x2 відповідають різні значення f(x1) ( f(x2).
Означення. Функція f : A ( B називається сур’єктивною, якщо для кожного y ( B існує таке x ( A, що f(x) = y.
Зауваження.
Функція f : A ( B, яка одночасно є ін’єктивною і сур’єктивною називають бієктивною. Для такої функції існує обернена. Покажемо це, взявши будь яке y ( B. Так як функція f : A ( B сур’єктивна, то існує x ( A таке, що f(x) = y. Припустимо тепер, що існує z ( A відмінне від х, що теж задовольняє умову f(z) = y. Але такого не може бути в силу ін’єктивності функції f. Іншими словами, існує всього одне значення x ( A таке, що f(x) = y. Таким чином ми визначили обернену функцію f-1 : B ( A написавши f-1(y) = x, де x ( A є єдиний розв’язок рівняння f(x) = y.
Приклад 2.4.5. Розглянемо функцію f : N ( N : x ( x. Ця функція є бієктивною.
Приклад 2.4.6. Розглянемо функцію f : N ( Z : x ( x. Ця функція є ін’єктивна, але не сур’єктивна.
Приклад 2.4.7. Розглянемо функцію f : Z ( N ( {0} : x ( |x|. Ця функція сур’єктивна, але не ін’єктивна.
Приклад 2.4.8. Розглянемо функцію f : R ( R : x ( x/2. Це бієктивна функція. Оберненою функцією буде f-1 : R ( R : x ( 2x.
Приклад 2.4.9. Які з наступних функцій з N в N є сур’єктивні, інє’ктивні чи бієктивні. В останньому випадку знайти обернені функції.
• y = 2x + 3;
• y = 2x - 3;
• y = x2;
• y = x + 1 якщо x непарне, y = x - 1 якщо x парне.
Припустимо, що A, B і C є довільні множини і f : A ( B , g : B ( C . Визначимо композицію функцій (складну функцію) як g ( f : A ( C написавши (g ( f)(x) = g(f(x)) для будь якого x ( A.
СПОЛУЧНИЙ ЗАКОН. Припустимо, що A, B , C і D є довільні множини і f : A( B , g : B ( C , h: C( D. Тоді h ( (g ( f) = (h ( g) ( f.
Вправи на закріплення матеріалу.
1. Множиною потенцією P(A) множини A називають множину всіх підмножин A. Нехай A = {1, 2, 3, 4, 5}.
a) Скільки елементів містить P(A)?
b) Скільки елементів у множині P(A(P(A)) ( A?
c) Скільки елементів у множині P(A(P(A)) ( A?
2. Для кожного з наступних бінарних відношень R на Z визначіть, яи воно є рефлексивним, симетричним, транзитивним і у випадку відношення еквівалентності вказати класи еквівалентності Z.
a) (a, b) (( R якщо a є дільником b b) (a, b) ( R якщо a + b парне
c) (a, b) ( R якщо a + b не парне d) (a, b) (R якщо a ( b
e) (a, b) ( R якщо a2 = b2 f) (a, b) ( R якщо a < b
3. Для кожного з наступних бінарних відношень R на N визначіть, яи воно є рефлексивним, симетричним, транзитивним і у випадку відношення еквівалентності вказати класи еквівалентності N.
a) (a, b) ( R якщо a < 3b b) (a, b) ( R якщо 3a ( 2b
c) (a, b) ( R якщо a - b = 0 d) (a, b) ( R якщо 7 є дільником 3a + 4b
4. Розглянемо множину A = {1, 2, 3, 4, 6, 9}. Визначіть R на A написавши (x, y) ( R тоді і тільки тоді коли
x - y є кратним 3.
a) Опишіть R як підмножину A A.
b) Покажіть, що R є відношенням еквівалентності на A.
c) Знайдіть класи еквівалентності відношення R?
5. Нехай A = {1, 2, 4, 5, 7, 11, 13}. Визначте відношення R на A написавши (x, y) ( R тоді і тільки тоді коли x - y є кратним 3.
a) Покажіть, що R є відношенням еквівалентності на A.
b) Скільки класів еквівалентності має відношення R ?
6. Визначте відношення R на Z написавши (x, y) ( R тоді і тільки тоді коли x - y є одночасно кратним 3 і 2.
а)Покажіть, що R є відношенням еквівалентності на Z.
b) Скільки класів еквівалентності має відношення R ?
7. Визначте відношення R на N написавши (x, y) ( R тоді і тільки тоді коли x - y є одночасно кратним 3 і 2.
a) Чи є R рефлексивним? симетричним? транзитивним?
b) Знайти підмножину A множини N таку, щоб відношення R на A було б відношенням еквівалентності.
8. Нехай A = {1, 2} і B = {a, b, c}. Для кожного з наступних випадків визначить, чи множина є графом функції f : A ( B; і якщо так, то знайти f(1) і f(2) і дослідити функцію на інєктивність і сурєктивність.
a) {(1, a), (2, b)} b) {(1, b), (2, b)} c) {(1, a), (1, b), (2, c)}
9. Нехай f, g і h функції з N в N визначені як
g(x) = x2 + 1 і h(x) = 2x + 1 для будь якого x ( N.
a) .Дослідити кожну функцію на інєктивність і сурєктивність.
b) Знайти h ( (g ( f) і (h ( g) ( f і перевірити справедливість сполучного закону для композиції функцій.
10. Розглянемо функцію f : N ( N, задану як f(x) = x + 1 для кожного x ( N.
a) Що єсть областю визначення функції?
b) Що єсть областю значень функції?
c) Чи ця функція інєктивна?
d) Сурєктивна?
11. Нехай f : A (B і g : B ( C . Доведіть:
a) Якщо f і g є інєктивні, то g ( f теж інєктивна.
b) Якщо g ( f інєктивна, тоді f теж інєктивна.
c) Якщо f сурєктивна і g ( f інєктивна, тоді g є інєктивна.
d) Якщо f і g сурєктивні, то g ( f теж сурєктивна.
e) Якщо g ( f сурєктивна, то g також сурєктивна.
f) Якщо g ( f сурєктивна і g інєктивна, то f сурєктивна.
12. a) Дати приклад функцій f : A (B і g : B ( C таких, що g ( f інєктивна , а g ні.
b) Дати приклад функцій f : A (B і g : B ( C таких, що g ( f сурєктивна , а g ні.
13. Припустимо, що f : A ( B, g : B ( A і h : A ( B ( C і що функція k : A ( B ( C визначена як k(x, y) = h(g(y), f(x)) для всіх x ( A і y ( B.
a) Показати, що коли f, g і h інєктивні, то k також інєктивна.
b) Показати, що коли f, g і h сурєктивні, то k також сурєктивна.
14. Припустимо, що множина A має 5 eлементів і множина B має 2 eлементи.
a) Скільки різних функцій f : A ( B можна утворити?
b) Скільки з цих функцій не є сурєктивними?
c) Скільки з цих функцій не є інєктивними?
15. Припустимо, що множина A має 2 eлементи і множина B має 5 eлементів.
a) Скільки різних функцій f : A ( B можна утворити?
b) Скільки з цих функцій не є сурєктивними?
c) Скільки з цих функцій не є інєктивними?
16. Припустимо, що A, B , C і D є скінчені множини і f : A( B , g : B ( C , h: C( D. Нехай виконуються наступні умови:
B, C і D мають однакову кількість елементів.
f : A ( B є інєктивна.
g : B ( C є сурєктивна.
h : C ( D є інєктивна.
Довести h ( (g ( f) : A ( D є бієктивна.
17. Нехай A = {1, 2} і B = {2, 3, 4, 5}. Випишіть всі елементи наступних множин:
a) A A
b) множину функцій з A в B
c) множину інєктивних функцій з A в B
d) множину сурєктивних функцій з A в B
e) множину бінарних відношень в B
f) множину відношень еквівалентності в B для яких існують в точності два класи еквівалентності
g) множину всіх відношень еквівалентності B
h) множину інєктивних функцій з B в A
i) множину сурєктивних функцій з B в A
j) множину бієктивних функцій з B в B
18. Визначимо бінарне відношення R на N N як (a, b)R(c, d) тоді і тільки тоді, коли a + b = c + d.
a) Довести, що R є відношенням еквівалентності на N N.
b) Нехай S означає множину класів еквівалентності в R. Довести, що існує бієктивна функція з S в N.
19. Нехай R є бінарне відношення визначене на N як (a, b) ( R тоді і лише тоді коли [4/a] = [4/b]. Тут для кожного x ( R, [x] означає ціле число n , що задовольняє умову n ( x < n+ 1.
a) Довести, що R є відношення еквівалентності в N.
b) Нехай S означає множину класів еквівалентності в R. Довести, що існує бієктивна функція з S в {1, 2, 3, 4}.
Тексти для більш поглибленого вивчення
Бінарні відношення