Властивості відношень
R A × A
4. Антисиметричність
5.Транзитивність
6.Порівняльність x, y A xRy yRx
Теорема про властивості
Властивості бінарних відношень 1- 6 еквівалентні наступним включенням та рівностям:
R A × A
1. I A R |
4. R R 1 I A |
|
2. R I A 5.R R R |
|
3. R R 1 |
6. R R 1 A2 |
6 |
Доведення п.5
R – транзитивне R2 R
(a,b) R2 aR Rb c aRc,cRb за транзитивністю aRb (a,b) R
Доведення п.5
R2 R R-транзитивне
aRb, bRc aR Rc (a,c) R R(a,c) R aRc
Відношення еквівалентності
Відношенням еквівалентності на множині A будемо називати рефлексивне, симетричне та транзитивне бінарне відношення на множині A.
1.Рефлексивне x A xRx
2.Симетричне xRy yRx
3.Транзитивне xRy, yRz xRz
Приклади відношеннь еквівалентності
Паралельність прямих Однакова остача при діленні на 2
Бути родичами
xRy x y mod 5
2 7, 7 32, 2 32