Функціональне бінарне відношення

Бінарне відношення Γ називається функціональним, якщо воно не містить упорядкованих пар з однаковими першими елементами.

Властивості бінарних відношень.

Наведемо список важливих властивостей, за якими класифікують відношення.

Нехай R - деяке відношення на множині M.

а). Відношення R називається рефлексивним, якщо для всіх a Î M має місце aRa.

Очевидно, що відношення R ₁, R ₂, R ₄, R ₅, R ₇ - рефлексивні.

б). Відношення R називається антирефлексивним (іррефлексивним), якщо для жодного a Î M не виконується aRa.

Відношення "більше", "менше", "є сином" антирефлексивні. В той же час, відношення R ₆не є ні рефлексивним, ні антирефлексивним.

Всі елементи головної діагоналі матриці C для рефлексивного відношення на скінченній множині M дорівнюють 1, а для антирефлексивного відношення дорівнюють 0.

в). Відношення R називається симетричним, якщо для всіх a, b Î M таких, що aRb маємо bRa.

г). Відношення R називається антисиметричним, якщо для всіх a, b Î M таких, що aRb і bRa маємо a = b.

Наприклад, відношення R ₃, R ₄, R ₅, R ₆, R ₈ - симетричні, а відношення R ₁, R ₂, R ₇ - антисиметричні.

Неважко переконатись, що відношення R симетричне тоді і тільки тоді, коли R = R ^-1.

д). Відношення R називається транзитивним, якщо зі співвідношень aRb і bRc випливає aRc.

Наприклад, відношення R ₁, R ₂, R ₄, R ₅, R ₇, R ₈, R ₉ - транзитивні, а відношення R ₃, R ₆ - не транзитивні.

Неважко переконатись, що відношення R транзитивне тоді і тільки тоді, коли R ° R Í R.