Бінарне відношення: відмінності між версіями

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

'''а) Пряме'''. Нехай задане розбиття П. Розглянемо відношення Е(П) таке, що  означає, що належать одній і тій ж підмножині R_i розбиття П. Тоді відношення Е(П) – рефлексивне (тому що за побудовою ми включаємо в нього пари вигляду '' ''для кожного  симетричне (тому що за побудовою, якщо ми включаємо в нього пару вигляду  то включаємо і пару вигляду, тран�зи�тивнетранзитивне (тому що за побудовою, якщо ми включаємо в нього пари вигляду то включаємо і пару вигляду  Таким чином, відношення Е(П) – відношення еквівалентності.

'''б) Обернене'''. Нехай задано на R відношення еквівалентності E. Легко побудувати функцію  котра елементу r_i ставить у відповідність підмножину Тому що відношення Е рефлексивне, то а отже Залишається показати, що будь-які дві підмножини  або не пере�ти�на�ю�тьсяперетинаються, або є рівними. Нехай це не так і є загальний елемент але підмножини і  не рівні. Але тоді справедливо  В силу симетричності відношення E, якщо виконується  то виконується За наявності в відношенні E пар  в силу транзитивності відношення E в ньому присутня пара  З того, що для будь-якого  справедливо і, отже, в силу транзитивності справедливослідує, що  Помінявши місцями елементианалогічно встановлюємо справедливість  Але це означає  Іншими словами, будь-які підмножини або не пере�ти�на�ю�тьсяперетинаються, або є рівними. З кожної групи таких рівних підмножин залишимо по одній підмножині, отримавши різні підмножини, що задовільняють другому обмеженню на розбиття. ''Теорема доведена''.