Приклад 1.16. 1. Фактор-множина за відношенням рівності E для будь-якої множини M має вигляд M/E = { {a} | aÎM}.
2. Фактор-множина для відношення "конгруентні за модулем 3" на множині N натуральних чисел складається з трьох класів { 3k | kÎN }, { 3k-1 | kÎN } і { 3k-2 | kÎN}.
Доведемо, що фактор-множина M/R є розбиттям множини M. Оскільки за побудовою кожний елемент множини M належить принаймні одній з множин SiR, iÎI, то 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.
13. Відношення порядку
Відношення R на множині M називається відношенням часткового (нестрогого) порядку, якщо воно рефлексивне, антисиметричне і транзитивне, тобто
1. aRa для всіх aÎM (рефлексивність),
2. Якщо aRb і bRa, то a = b (антисиметричність),
3. Якщо aRb і bRc, то aRc (транзитивність).
Множина M, на якій задано деякий частковий порядок, називається частково впорядкованою множиною. Елементи a,bÎM назвемо порівнюваними за відношенням R, якщо виконується aRb або bRa.
Частково впорядкована множина M, в якій будь-які два елементи є порівнюваними між собою, називається лінійно впорядкованою множиною або ланцюгом. Відповідне відношення R, задане на лінійно впорядкованій множині, називається лінійним (досконалим) порядком. Таким чином, відношення R на множині M називається відношенням лінійного порядку, якщо воно рефлексивне, антисиметричне, транзитивне і для будь-якої пари елементів a,bÎM виконується aRb або bRa.
Для позначення відношень порядку будемо використовувати знаки £ і ³, які повторюють звичайні математичні знаки £ і ³. Тобто для відношення порядку R замість aRb будемо записувати a£b або b³a і читати "a менше або дорівнює b" або "b більше або дорівнює a" відповідно. Очевидно, що £ є оберненим відношенням до відношення ³.
За кожним відношенням часткового порядку £ на довільній множині M можна побудувати інше відношення < на M, поклавши a < b тоді і лише тоді, коли a£b і a¹b. Це відношення називається відношенням строгого порядку на множині M. Зрозуміло, що відношення строгого порядку антирефлексивне, транзитивне, а також задовольняє умові так званої сильної антисиметричності або асиметричності, тобто для жодної пари a,bÎM не може одночасно виконуватись a<b і b<a.
З іншого боку, за довільним відношенням строгого порядку < на множині M однозначно можна побудувати відповідне відношення часткового (нестрогого) порядку £, поклавши a£b тоді і тільки тоді, коли a < b або a = b, a,bÎM. З огляду на такий простий зв'язок між відношеннями часткового (нестрогого) і строгого порядку можна обмежитись вивченням лише одного з цих порядків, наприклад, £.
Приклад 1.17. 1. Відношення £ і < ( ³ і > ) є відношеннями відповідно часткового і строгого порядку на множинах чисел N, Z і R. Більше того, множини N, Z і R, а також будь-які їхні підмножини, є лінійно впорядкованими множинами за відношеннями £ або ³.
2. Частковим порядком є відношення рівності iM на будь-якій множині M. Цей порядок іноді називають тривіальним.
3. Відношення нестрогого включення є відношенням часткового порядку, а відношення - відношенням строгого порядку на множині b(A) всіх підмножин (булеані) заданої множини A.
4. Задамо відношення £ і < на множині R кортежів дійсних чисел довжини n наступним чином: (a1,a2,...,an)£(b1,b2,...,bn ), якщо a1£b1, a2£b2,..., an£bn; аналогічно (a1,a2,...,an)<(b1,b2,...,bn), якщо (a1,a2,...,an)£(b1,b2,...,bn) і принаймні для однієї координати i=1,,...,n виконується ai<bi.
Тоді (2,3.75,-4)<(2.1, 24,0), але кортежі (1,4,-1.7 ) і (2,2,4) непорівнювані.
Аналогічно може бути введено частковий порядок на множинах Nn, Zn і Qn.
5. Зафіксуємо строгий порядок розташування символів у довільному скінченному алфавіті A={a1,a2,...,an}, наприклад, покладемо, що a1<a2<...<an. Тоді природним чином означається так званий лексикографічний порядок на множині A всіх слів довжини m в алфавіті A. А саме, вважаємо ai1ai2... ain < aj1aj2...ajn тоді і тільки тоді, коли ais = ajsпри s=1,2,...,k-1 і aik < ajk для певного k.
Лексикографічний порядок можна поширити на множину A всіх слів в алфавіті A, якщо доповнити алфавіт A додатковим ("порожнім") символом b і вважати, що b<ai, i=1,2,...,n. При порівнюванні двох слів різної довжини спочатку слово меншої довжини доповнюється справа такою кількістю "порожніх" символів b, щоб зрівнятися по довжині з другим словом, після чого обидва слова порівнюються за правилом порівнювання слів однакової довжини.
Нехай A = {a,b,c} і a<b<c, тоді aac<aba, abbc<abcb, ab<abab, b<cba тощо.
Лексикографічний порядок лежить в основі впорядкування всіх словників, енциклопедій, індексів (предметних або іменних покажчиків), довідників, списків, таблиць тощо.
6. В множині N натуральних чисел відношення "ділить" є відношенням часткового порядку. Маємо 4 £ 28, 11 £ 132, 5 £ 5, 1 £n для будь-якого nÎN. Пари 7 і 22, 13 і 35 непорівнювані.
Нехай M частково впорядкована множина і A деяка непорожня підмножина множини M. Верхньою гранню підмножини AÍM в множині M називається елемент bÎM такий, що a£b всіх aÎA. Елемент b називається найбільшим елементом множини M, якщо b - верхня грань множини M.
Відповідно, елемент c частково впорядкованої множини M називається нижньою гранню підмножини AÍM, якщо c£a для будь-якого aÎA. Елемент c - найменший в множині M, якщо c - нижня грань самої множини M.
Таким чином, вважається, що найбільший і найменший елементи, а також верхня та нижня грані (якщо вони існують), є порівнюваними з усіма елементами даної множини M або підмножини A відповідно.
Елемент xÎM називається максимальним в множині M, якщо не існує елемента aÎM такого, що x<a. Відповідно, елемент nÎM називається мінімальним у множині M, якщо не існує елемента aÎM такого, що a<n. Очевидно, якщо в частково впорядованій множині M існує найбільший елемент, то він же є єдиним максимальним елементом множини M. Аналогічно, найменший елемент множини M - єдиний мінімальний елемент даної множини. Зауважимо також, що частково впорядкована множина M може не мати найбільшого (найменшого) елемента і в той же час мати один або декілька максимальних (мінімальних) елементів. У лінійно впорядкованій множині поняття найбільшого і максимального (найменшого і мінімального) елементів збігаються.