Спеціальні бінарні відношення на множині
Рефлексивне, симетричне і транзитивне на множині А відношення Q називається відношенням еквівалентності
Толерантності — рефлексивне і симетричне.
Порядку нестрогого — рефлексивне, транзитивне і кососиметричне
Порядку строгого — іррефлексивне, транзитивне і кососиметричне
Передпорядку нестрогого — рефлексивне і транзитивне.
Передпорядку строгого — іррефлексивне і транзитивне
Відношення Q
на множині А
називається відношенням
тотожності,
якщо воно збігається з множиною всіх
можливих пар
при
.
Відношення тотожності позначають
(ще позначають
):
;
його ще називають діагоналлю множини А. Діагональ є тотожним відображенням множини А на себе. Матрицею цього відношення є одинична матриця Е (на діагоналі стоять одиниці, а поза діагоналлю — нулі). Граф містить лише вершини з петлями. Відношенням тотожності ?? є відношення =.
Відношення Q на множині А називається рефлексивним, якщо
для всіх
.
Умова рефлексивності
відношення:
.
Всі елементи головної діагоналі матриці
— одиниці. Граф містить петлі всіх
вершин. Рефлексивними є відношення
на числовій множині, “мати спільний
дільник” на множині цілих чисел.
Відношення Q на множині А називається іррефлексивним (ще кажуть: антирефлексивним), якщо
для всіх
.
Умова іррефлексивності
відношення:
(або
,
тобто доповнення до іррефлексивного
відношення
є рефлексивним). Всі елементи головної
діагоналі матриці — нулі. Граф не містить
жодної петлі. Іррефлексивним є відношення
“бути сином”.
Відношення Q на множині А називається симетричним, якщо
з
.
Умовою симетричності
відношення є рівність
.
Матриця симетрична (тобто
— початкова і транспонована матриці
рівні). Вершини графа пов’язані лише
парами протилежно напрямлених дуг
(ненапрямленими ребрами). Симетричним
є відношення дружби, відношення “бути
родичем” на множині людей.
Відношення Q на множині А називається кососиметричним (ще кажуть: антисиметричним), якщо
з
і
або: з
і
).
Матриця кососиметрична (тобто, якщо
і
,
то
).
У графі можуть бути петлі, але зв’язок
між різними вершинами графа, якщо він
є, то лише однонаправлений, тобто, якщо
є дуга з вершини а в відмінну від неї
вершину b, то дуга з вершини b в вершину
а обов’язково відсутня. Антисиметричним
є відношення
на множині дійсних чисел, включення
на множині підмножин деякої множини.
Зауважимо, що
існують відношення, які одночасно можуть
мати властивості симетричності й
кососиметричності: наприклад, відношення
на множині
водночас симетричне й кососиметричне.
Існують відношення, які не мають жодної
з цих властивостей: наприклад, визначене
на множині
відношення
.
Відношення Q
на множині А
називається асиметричним
(ще кажуть: несиметричним), якщо з двох
співвідношень
і
хоч би одне не виконується. Іншими
словами це можна сказати так: відношення
асиметричне, якщо для всіх а і b
із А з того, що
,
випливає, що
.
Якщо відношення асиметричне, то воно і
іррефлексивне, тобто
.
Крім того, будь-яке асиметричне відношення
має бути й кососиметричним; але обернене
твердження невірне. Матриця кососиметрична
з нульовими елементами на головній
діагоналі. Граф петель не має, а дві
вершини можуть бути зв’язані тільки
однією напрямленою дугою. Асиметричним
є відношення
на множині дійсних чисел, точне включення
на множині підмножин деякої множини,
“бути батьком” на множині людей.
Відношення Q на множині А називається транзитивним, якщо
з
і
.
Умова транзитивності
відношення:
.
Властивість матриці транзитивного
відношення коротко і наочно схарактеризувати
важко. У цій матриці для кожної пари
одиничних елементів, один з яких
розміщений на перетині рядка і
і стовпчика j,
а інший — рядка j
і стовпчика k,
на перетині рядка і
і стовпчика k
обов’язково має бути одиничний елемент;
при цьому наявність одиничних елементів
на головній діагоналі не порушує
транзитивності. У графі одночасно з
дугами з вершини а
в вершину b
і із вершини b
в вершину с
обов’язково має бути дуга з вершини а
в вершину с;
у графі також можуть бути петлі. Тобто,
якщо у графі існує шлях, то будь-які дві
вершини цього шлях, з’єднані дугою.
Транзитивним є відношення
,
і
на множині дійсних чисел, “бути дільником”
на множині цілих чисел, відношення “жити
в одному будинку”, “бути начальником”
на множині людей, але відношення дружби,
відношення “бути васалом” (оскільки
“васал мого васала не мій васал”) не
транзитивні.
Відношення Q на множині А називається антитранзитивним, якщо
з
і
.
Антитранзитивним є відношення “бути сином”.
Задача. Що можна сказати про властивості таких відношень:
а) х ділить у на множині натуральних чисел. Рефлексивне — х ділить сам себе; не симетричне 6:3 але не 3:6; транзитивне якщо х ділить у у ділить z, то у=mx, z=ny отже, z=ny=(nm)x ; кососиметричне оскільки з припущень х ділить у і у ділить х зразу витікає, що у=х.
б)
на множині цілих чисел — не рефлексивне,
бо вислів
неправильний; симетричне, бо
;
не транзитивне, бо
і
,
але
;
не кососиметричне, бо із умов
і
не випливає, що
