Бінарне відношення: відмінності між версіями
| [неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
Рядок 44:
Відношення, яке є рефлексивним, симетричним та транзитивним, називається [[відношення еквівалентності|відношенням еквівалентності]].
З поняттям відношення еквівалентності тісно пов’язане поняття розбиття.
==== ''Теорема 1''. Відношення Е є відношенням еквівалентності на множині R тоді і тільки тоді, коли воно визначає розбиття П<sub>Е </sub>на множині R. ====
'''''Доведення'''''.
'''а) Пряме'''. Нехай задане розбиття П. Розглянемо відношення Е(П) таке, що означає, що належать одній і тій ж підмножині R<sub>i</sub> розбиття П. Тоді відношення Е(П) – рефлексивне (тому що за побудовою ми включаємо в нього пари вигляду '' ''для кожного симетричне (тому що за побудовою, якщо ми включаємо в нього пару вигляду то включаємо і пару вигляду, тран�зи�тивне (тому що за побудовою, якщо ми включаємо в нього пари вигляду то включаємо і пару вигляду Таким чином, відношення Е(П) – відношення еквівалентності.
'''б) Обернене'''. Нехай задано на R відношення еквівалентності E. Легко побудувати функцію котра елементу r<sub>i</sub> ставить у відповідність підмножину Тому що відношення Е рефлексивне, то а отже Залишається показати, що будь-які дві підмножини або не пере�ти�на�ю�ться, або є рівними. Нехай це не так і є загальний елемент але підмножини і не рівні. Але тоді справедливо В силу симетричності відношення E, якщо виконується то виконується За наявності в відношенні E пар в силу транзитивності відношення E в ньому присутня пара З того, що для будь-якого справедливо і, отже, в силу транзитивності справедливо<sub> </sub>слідує, що Помінявши місцями елементианалогічно встановлюємо справедливість Але це означає Іншими словами, будь-які підмножини або не пере�ти�на�ю�ться, або є рівними. З кожної групи таких рівних підмножин залишимо по одній підмножині, отримавши різні підмножини, що задовільняють другому обмеженню на розбиття. ''Теорема доведена''.
Відношення, яке є рефлексивним, антисиметричним та транзитивним, називається [[відношення часткового порядку|відношенням часткового порядку]].
| |||