Реферат на тему:

Відношення еквівалентності

Відношення R на множині M називається відношенням еквівалентності (або
просто еквівалентністю), якщо воно рефлексивне, симетричне і
транзитивне.

Враховуючи важливість відношення еквівалентності, дамо розгорнуте
означення цього поняття. Таким чином, відношення R на множині M є
відношенням еквівалентності або евівалентністю, якщо

1. aRa для всіх a(M (рефлексивність);

2. Якщо aRb, то bRa для a,b(M (симетричність);

3. Якщо aRb і bRc, то aRc для a,b,c(M (транзитивність).

Приклад 1.15. 1. Відношення рівності iM на будь-якій множині M є
відношенням еквівалентності. Рівність — це мінімальне відношення
еквівалентності, бо при видаленні бодай одного елемента з iM відношення
перестає бути рефлексивним, а отже, і відношенням еквівалентності.

2. Відношення рівнопотужності множин є еквівалентністю.

3. Важливу роль відіграє в математиці відношення «мають однакову остачу
при діленні на k» або «конгруентні за модулем k», яке є відношенням
еквівалентності на множині N натуральних чисел для будь-якого
фіксованого k(N. Відношення конгруентності за модулем k часто позначають
a ( b (mod k). Цьому відношенню належать, наприклад, пари натуральних
чисел (17,22), (1221,6), (42,57) для k=5, тобто 17 ( 22(mod 5), 1221 ( 6
(mod 5), 42 ( 57 (mod 5).

4. Еквівалентністю є відношення подібності на множині всіх трикутників.

Bi=A і Bi(Bj = ( для i(j. Множини Bi, i(I є підмножинами множини A і
називаються класами, суміжними класами, блоками або елементами розбиття.
Очевидно, що кожний елемент a(A належить одній і тільки одній множині
Bi, i(I.

Припустимо, що на множині M задано відношення еквівалентності R.
Виконаємо таку побудову. Виберемо деякий елемент a(M і утворимо
підмножину SaR = { x | x(M і aRx}, яка складається з усіх елементів
множини M еквівалентних елементу a. Відтак, візьмемо другий елемент b(M
такий, що b(SaR і утворимо множину SbR = { x | x(M і bRx } з елементів
еквівалентних b і т.д. Таким чином одержимо сукупність множин (можливо,
нескінченну) {SaR,SbR,…}. Побудована сукупність множин { SiR | i(I}
називається фактор-множиною множини M за еквівалентністю R і
позначається M/R.

Приклад 1.16. 1. Фактор-множина за відношенням рівності E для будь-якої
множини M має вигляд M/E = { {a} | a(M}.

2. Фактор-множина для відношення «конгруентні за модулем 3» на множині N
натуральних чисел складається з трьох класів { 3k | k(N }, { 3k-1 | k(N
} і { 3k-2 | k(N}.

SiR = M. Відтак припустимо, що для деяких SaR(SbR існує елемент
c(SaR(SbR. Тоді з c(SaR випливає aRc, а з c(SbR випливає bRc. Iз
симетричності і транзитивності відношення R виводимо aRb і bRa. Iз
співвідношення aRb і правила побудови множини SaR маємо SaR(SbR, а з bRa
і правила побудови множини SbR одержуємо протилежне включення SbR(SaR.
Отже, SaR=SbR, і з одержаної суперечності випливає справедливість
сформульованого твердження.

Очевидно, що будь-які два елементи з одного класу SiR еквівалентні між
собою, в той час як будь-які два елементи з різних класів фактор-множини
M/R нееквівалентні. Класи SiR називають класами еквівалентності за
відношенням R. Клас еквівалентності, який містить елемент a(M часто
позначають через [a]R.

Потужність фактор-множини |M/R| називається індексом розбиття або
індексом відношення еквівалентності R.

З іншого боку, припустімо, що для множини M задано деяке розбиття {Si |
i(I }. Побудуємо відношення T на множині M за таким правилом: aTb для
a,b(M тоді і тільки тоді, коли a і b належать тій самій множині Si
розбиття. Неважко переконатись, що відношення T є рефлексивним,
симетричним і транзитивним, тобто є відношенням еквівалентності на
множині M.

Отже, справедлива така теорема.

Теорема 1.10. Iснує взаємно однозначна відповідність між усіма можливими
еквівалентностями на множині M і всіма розбиттями множини M. Тобто,
кожному відношенню еквівалентності на множині M відповідає єдине
розбиття даної множини на класи і, навпаки, кожне розбиття множини M
однозначно задає деяке відношення еквівалентності на M.

Нехай R відношення еквівалентності на множині M. Відображення множини M
на фактор-множину M/R, яке кожному елементу a(M ставить у відповідність
клас еквівалентності SaR, якому належить елемент a, називається
канонічним або природним відображенням множини M на фактор-множину M/R.

Похожие записи