Спеціальна бінарні відношення (рефлексивні, іррефлексивні, симетричні, транзитивні, антисиметричні, асиметричні)

Бінарне відношення (бінарне відношення на множині) — в математиці окремий випадок відношення на множині, яке встановлюється між двома елементами множини.

Кажуть також, що елементи a,b Є M знаходяться у бінарному відношенні R (часто записують у вигляді aRb), якщо впорядкована пара (a,b) Є R. Отже, R є підмножиною декартового квадрата: R Є M×M.

Іноді розрізняють поняття бінарного відношення на множині та бінарного відношення між множинами, яке в цій енциклопедії називається відповідністю між множинами.

Нехай R — деяке відношення на множині M. Відношення R називається

рефлексивним, якщо для всіх aЄM має місце aRa.

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

симетричним, якщо для всіх a,b ЄM таких, що aRb маємо bRa.

асиметричним, якщо для всіх a,bЄM таких, що aRb не виконується bRa.

антисиметричним, якщо для всіх a,bЄM таких, що aRb і bRa маємо a = b.

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

повним, якщо для будь-яких a,bЄM випливає, що aRb або bRa.

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

Відношення, яке є рефлексивним, симетричним та транзитивним, називається відношенням еквівалентності.

Відношення, яке є рефлексивним, антисиметричним та транзитивним, називається відношенням часткового порядку.

Відношення часткового порядку, яке є повним, називається відношенням лінійного порядку (чи лінійним порядком).