3. Поняття бінарного відношення. Граф відношення

У випадку, коли відношення визначене між елементами двох рівних множин і , тобто коли , або, що те саме, області відправлення і прибуття відношення збігаються, то кажуть про відношення між елементами множини , яке також називають відношенням на множині Для нього зберігаються ті ж характеристики, що й для відношення між елементами двох множин.

Означення відношення.

Нехай є множина Встановимо на цій множині відношення «бути більшим» Тоді: .

Встановимо відношення "більше на 1". Одержимо нерівність: .

Відношення "більше в 2 рази": .

Можна встановити і інші відношення. Та кожного разу будемо утворювати впорядковані пари елементів даної множини, які зв'язані заданим відношенням.

О. Відношенням між елементами множини X або на множині X називається будь-яка підмножина декартового добутку .

Якщо - відношення на множині А, то це записується .

3. Способи задання бінарних відношень

Відношення на множині задаються аналогічно як і відповідності – відношення між елементами різних множин.

1. за допомогою множини пар або графіком;

2. графом;

3. точковим графіком, якщо множини числові;

4. характеристичною властивістю пар, що належать відношенню.

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

О. Графом називається креслення, яке складається з точок, що позначають елементи множин та стрілок, які з'єднують відповідні точки, вказуючи на відповідні відношення між елементами даної множини.

Побудуємо графи розглянутих відношень.

: « х > у » : « більше в 2 рази»

Побудуємо граф відношення "бути кратним" на множині

Граф відношення на множині має особливості:

1. оскільки області прибуття і відправлення збігаються, то вершинами графа відношення є елементи однієї і тієї ж множини;

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

3. якщо дві різні вершини графа з’єднуються двома дугами, напрями яких протилежні, то для спрощення дві дуги замінюють однією і називають її подвійною;

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

Задамо на множині А за допомогою переліку елементів відношення "більше в 2 рази"

={(2,1),(4,2),(8,4)}.

Також відношення на множині можна задати за допомогою характеристичної властивості: Наприклад, "число х більше числа у в 2 рази".

3. Властивості відношень

Більшість відношень за змістом різні, але в чомусь схожі між собою. Схожість дає можливість виділити у відношеннях найбільш характерні їх властивості. Розглянемо деякі з них.

1. Відношення на множині називається рефлексивним, якщо про будь-який елемент множини можна сказати, що він знаходиться у відношенні сам із собою.

рефлексивне на .

Приклади рефлексивних відношень: рівність, паралельність, кратність, подільність.

2. Відношення на множині називається антирефлексивним, якщо про будь-який елемент множини можна сказати, що він не знаходиться у відношенні сам із собою.

рефлексивне на .

Приклади антирефлексивних відношень: більший, менший у числових множинах,, перпендикулярність – у множині прямих на площині.

3. Відношення на множині називається симетричним, якщо для будь-яких елементів множини з того, що елемент 𝑥 знаходиться у відношенні з елементом слідує, що елемент знаходиться у відношенні з елементом .

симетричне на

Приклади симетричних відношень: паралельність, перпендикулярність, рівність, рівносильність.

4. Відношення на множині називається антисиметричним, якщо для будь-яких елементів і з множини з того, що елемент знаходиться у відношенні з елементом , і елемент знаходиться у відношенні з елементом . слідує, що

антисиметричне на <=>

Приклади антисиметричних відношень: більше або дорівнює , менше або дорівнює , бути підмножиною .

5. Відношення на множині називається асиметричним, якщо для будь-яких елементів і з множини з того, що елемент знаходиться у відношенні з елементом слідує, що елемент не знаходиться у відношенні з елементом .

асиметричне на <=>

Приклади асиметричних відношень: більший, менший, кратність, подільність,

6. Відношення на множині називається транзитивним, якщо для будь-яких елементів множини з того, що елемент знаходиться у відношенні з елементом і елемент знаходиться у відношенні з елементом , слідує, що елемент знаходиться у відношенні з елементом .

транзитивне на <=> .

7. Відношення на множині називається зв’язним, якщо для довільних елементів і множини виконується принаймні одне з відношень: знаходиться у відношенні з елементом , знаходиться у відношенні з елементом , або дорівнює .

Приклади транзитивних відношень: рівність, паралельність, довший, вищий, нижчий, подільність, кратність, подібність.

Якщо відношення на множині має деякі із перелічених властивостей, то й обернене йому відношення має ті ж самі властивості.

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

1. рефлексивного відношення у кожній вершині є петля;

2. антирефлексивного відношення немає петель;

3. симетричного відношення всі дуги подвійні;

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

5. транзитивного відношення, якщо три вершини з’єднані дугами, то аналогічно додаванню векторів.

Різні за змістом відношення можуть мати спільні властивості. Це дає можливість виділяти відношення з певними наборами властивостей. Найважливішими з них є відношення еквівалентності і порядку.