ати наступна Умова: если в і-того рядку и в j-тому стовпці стоит одиниця, тобто, то всім Одиниця в -тому рядку и -тому стовпці повінні ВІДПОВІДАТИ одиниці в -тому рядку и у тихий же -Тихо стовпцях, тобто (і, может буті, в других стовпцях).
например, відношення, - транзітівні. Отношения, на множіні дійсніх чисел транзітівні.
Приклад. Нехай и відношення є множини. Які Властивості має завданні відношення?
розв язання:
Побудуємо матрицю відношення:
Відношення рефлексивне, того что для кожного,. Головна діагональ матриці відношення містіть одиниці.
Відношення НЕ є антирефлексивне, того что з умови не вимагають, например,, альо.
Розглянувші всі Можливі випадки методом безпосередно перескладання (табл. 2.2а) можна показати, что відношення симетрично. Крім того, матриця відношення симетрично относительно головної діагоналі.
НЕ є антисиметричних, того что І, альо.
Скоріставшісь методом безпосередно перескладання можна такоже показати, что відношення транзитивності.
Приклад.
Які Властивості мают відношення на множіні натуральних чисел:
а) - буті НЕ менше raquo ;;
б) - буті рівнім raquo ;;
в) - їхня сума - хлопця число raquo ;.
розв язання:
На множіні натуральних чисел:
а)
рефлексивне, що не антирефлексивне, того что віконується для всіх. Например,;
НЕ симетричного, того что, но - невірно;
антисиметричних, того что и віконуються только коли;
транзитивного, того что коли І, то. Например,, і.
б)
рефлексивне, що не антирефлексивне, того что віконується для всіх. Например,;
симетричного, того что коли, то і;
антисиметричних, того что коли І, то;
транзитивного, того что коли І, то і.
в)
рефлексивне, що не антирефлексивне, того что сума двох парних чисел и двох непарний чисел є число хлопця. Например, - хлопця і - хлопця;
симетричного, що не антисиметричних, того что кіль - хлопця, то і - теж хлопця (від переставленими доданків сума НЕ міняється). Например, - хлопця і - теж хлопця, - хлопця і - теж хлопця;
транзитивного, того что если - хлопця, - хлопця, то і - теж хлопця. Например, - хлопця і - хлопця, то і - теж хлопця.
2.4 Відношення еквівалентності
Визначення. Відношення R назівається відношенням еквівалентності, если воно має Такі Властивості:
а) рефлектівності: (x, х)? R при будь-якому х? Х;
б) сіметрічності: з (x1, х2)? R віпліває (x2, х1)? R;
в) транзітівності: если (x1, х2)? R і (x2, х3)? R, то (x1, х3)? R;
Замість того, щоб писати (x1, х2)? R, часто пишуть x1 ~ x2 або x1? x2 (mod R) (чітається так: x1 Конгруентність x2 за модулем R) чи, простіше, (x1 ~ x2 або x1? x2, если немає необхідності ще раз вказуваті, что мова идет про Одне ї ті самє відношення R).
Для x? X позначімо через K (x) підмножіну, что складається з елементів, еквівалентніх x, тобто K (x)={y | y? X; y ~ x}. Таку підмножіну будемо назіваті класом еквівалентності. Зрозуміло, что клас еквівалентності є множини всех елементів, еквівалентніх довільному елементи з цього класу. Справедлива наступна теорема:
Теорема 1. Два класи еквівалентності б або не перетінаються або співпадають.
Доведення. Припустиме, что перетин множини K (x) i K (х ) непорожній, и візьмемо z? K (x)? K (х ). Клас еквівалентності K (x) Утворення з елементів, еквівалентніх одному зі своих елементів x. Оскількі x и z еквівалентні, то за властівістю транзітівності отрімуємо, что K (x) Утворення такоже з елементів, еквівалентніх z. Аналогічно K (х ) Утворення з елементів, еквівалентніх z. Таким чином, K (х) i K (х ) співпадають.
Відношення еквівалентності на множіні Х породжує деяке розбіття множини Х, тобто Деяк сім ю непорожніх підмножін множини X (класів еквівалентності), Які попарно НЕ перетінаються, а їх про єднання рівне X. Будь-які дві елєменти з одного класу зв язані відношенням еквівалентності, тобто еквівалентні; з різніх класів - НЕ еквівалентні.
Навпаки, будь-яке розбіття множини X:
