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

І. Які з відношень завдань І-ІІІ до розділу «Види бінарних відношень» є відношеннями еквівалентності? Для кожного відношення еквівалент-ності визначити, яке розбиття воно породжує.

ІІ. Чи є відношеннями еквівалентності відношення:

1) R_mN², m>1, R_m={<a,b>| (a-b) ділиться на m},

2) Т(NN)², <a,b>Т<c,d>  a+d=b+c,

3) S(NN)², <a,b>S<c,d>  (ad=bc, b0, d0) або (a=c, b=d=0),

4) WR², aWb  (a-b) – раціональне число.

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

1) {,a,s,r,t},

2) книг університетської бібліотеки,

3) слів, що знаходяться на одній сторінці деякої книги,

4) мешканців одного будинку,

5) раціональних чисел,

6) житлових будинків Києва,

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

8) вищих навчальних закладів Києва,

9) читачів однієї бібліотеки,

10) квадратних матриць порядку n над деякою множиною Р,

11) точок площини,

12) N²,

13) паралелограмів на плошині,

14) парних цілих чисел,

15) непарних натуральних чисел,

16) літер українського алфавіту.

IV. Нехай R₁, R₂ – відношення еквівалентності на А. Довести, що:

1) R₁R₂ – відношення еквівалентності на А,

2) R₁^-1 – відношення еквівалентності на А,

3) R₁R₂ є відношенням еквівалентності на А  R₁R₂=R₂R₁,

4) R₁R₂ є відношенням еквівалентності на А  R₁R₂=R₁R₂,

5) (R₁) не є відношенням еквівалентності.

V. Нехай R₁, R₂ – відношення еквівалентності на А. Довести, що

1) R₁R₁=A²  R₁=A², 2) R₁R₂=A²  R₂R₁=A².

VI. Довести, що R є відношенням еквівалентності на А  (RR^-1)i_A=R.

VIІ. Нехай R є транзитивне та симетричне відношення на деякій множи-ні А й D(R)R(R)=А. Довести, що R – відношення еквівалентності на А.

VIІІ. Нехай R – рефлексивне та транзитивне відношення на деякій множині А. Довести, що RR^-1 є відношення еквівалентності.

Фактор-множина

Нехай R – відношення еквівалентності на А. Тоді, як відомо, існує розбиття множини А, яке визначається відношенням R. Позначимо це розбиття через А/R й називатимемо його фактор-множиною множини А по відношенню R, а множини, що складають дане розбиття – класами еквівалентності. Клас розбиття будемо іноді позначати через [x], де х – деякий елемент даного класу розбиття. Наприклад, якщо А/R={{a,c}, {b}, {d,e}}, то клас розбиття {a,c} можна позначити [а] або [с], а клас розбиття {d,e} – [d] або [е]. Якщо множина класів еквівалентності (тобто А/R) скінченна, то кількість класів еквівалентності називається індексом множини А, а множина А з відношенням еквівалентності R називається множиною скінченного індексу.

Наприклад, множина N з відношенням еквівалентності R, заданим умовою xRy  х та у – числа однакової парності, є множиною індексу 2. Якщо на N задано відношення тотожності і_N, то N/і_N = {{n}| nN}, тобто N/і_N не є скінченною множиною, отже, N з відношенням і_N не є множиною скінченного індексу.

За допомогою відношень еквівалентності на деякій множині А та фактор-множин цієї множини можна описати відображення множини А у інші множини.

Теорема 10. Будь-яке відображення 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, як показано у доведенні теореми 10, відношення еквівалентності 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>}.