МНОЖИНИ І ВІДНОШЕННЯ

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

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

Доведемо, що фактор-множина M/R є розбиттям множини M. Оскільки за побудовою кожний елемент множини M належить принаймні одній з множин SiR, iI, то SiR = M. Відтак припустимо, що для деяких SaRSbR існує елемент cSaRSbR. Тоді з cSaR випливає aRc, а з cSbR випливає bRc. Iз симетричності і транзитивності відношення R виводимо aRb і bRa. Iз співвідношення aRb і правила побудови множини SaR маємо SaRSbR, а з bRa і правила побудови множини SbR одержуємо протилежне включення SbRSaR. Отже, SaR=SbR, і з одержаної суперечності випливає справедливість сформульованого твердження.

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

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

З іншого боку, припустімо, що для множини M задано деяке розбиття {Si | iI }. Побудуємо відношення 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.

13. Відношення порядку

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

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

2. Якщо aRb і bRa, то a = b (антисиметричність),

3. Якщо aRb і bRc, то aRc (транзитивність).

Множина M, на якій задано деякий частковий порядок, називається частково впорядкованою множиною. Елементи a,bM назвемо порівнюваними за відношенням R, якщо виконується aRb або bRa.

Частково впорядкована множина M, в якій будь-які два елементи є порівнюваними між собою, називається лінійно впорядкованою множиною або ланцюгом. Відповідне відношення R, задане на лінійно впорядкованій множині, називається лінійним (досконалим) порядком. Таким чином, відношення R на множині M називається відношенням лінійного порядку, якщо воно рефлексивне, антисиметричне, транзитивне і для будь-якої пари елементів a,bM виконується aRb або bRa.

Для позначення відношень порядку будемо використовувати знаки і , які повторюють звичайні математичні знаки і . Тобто для відношення порядку R замість aRb будемо записувати a b або b a і читати "a менше або дорівнює b" або "b більше або дорівнює a" відповідно. Очевидно, що є оберненим відношенням до відношення .