Відношення еквівалентності, Детальна інформація

TH

ae

i

\x00F0

o

o

oe

o

u

ue

P

\x00B2

\x017E

 

c

:ля будь-якої множини 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.