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

Означення. Рефлективним називається таке бінарне відношення R на множині A, Для якого виконується умова

Означення. Відношення R на множині А називається антирефлексивним (іррефлексивним), якщо виконується умова

Ø

Ø

Означення. Відношення R на множині А називається симетричним, якщо виконується умова

Для таких відношень виконується рівність

Означення. Відношення R на множині А називається антисиметричним, якщо виконується умова

Для антисиметричних відношень має місце співвідношення

Ø

Означення. Відношення R на множині А називається асиметричним, якщо виконується умова

Означення. Відношення R на множині А називається транзитивним, якщо виконується умова

(a;b)

Для транзитивного відношення R на множині A , задане булевою матрицею М=

=

Відзначимо, що:

1) якщо R є рефлексивним відношенням, то всі елементи головної діагоналі матриці М дорівнюють одиниці;

2) якщо R є антирефлексивним відношенням, то всі елементи головної діагоналі матриці М дорівнюють нулеві;

3) якщо R є симетричним відношенням, то матриця М є симетричною;

4) якщо R є антисиметричним відношенням, то матриця М має такі властивості:

(m_ij = m_ji = 0 ) v ([(i ≠ j) ^ m_ij = 1)] =>(m_ji = 0))

Якщо, крім того, відношення не є асиметричним, то існує таке і, таке що m_ii = 1

Припустимо що відношення R задано орієнтованим графом. Тоді будуть справедливими такі твердження:

1. відношення R є рефлексивним, якщо в кожній вершині графа є петля;

2. відношення R є симетричним, якщо для кожної дуги графа між двома різними вершинами є протилежно напрямлена дуга;

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

4. відношення R є транзитивним, якщо поряд з дугами (a;b) та (b;c) граф обов’язково містить дугу (a;c);

Теорема 1: Для того щоб відношення R було рефлексивним, необхідно та достатньо щоб відношення R = U \ R, де U = A × A, було антирефлексивним.

Теорема 2: Для того щоб відношення R було симетричним, необхідно та достатньо щоб відношення R було симетричним.

Відношення еквівалентності

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

=, ≡, ~, I, U

Означення: Переріз R_a відношення еквівалентності R с A × A за елементом а є А називається класом еквівалентності і позначається [a].

Якщо b є [a], то b називається представником класу еквівалентності [a], зокрема а є [a].

Теорема: Довільні класи еквівалентності за відношенням R або не мають спільних елементів, або збігаються.

Теорема: Довільні відношення еквівалентності, задане на множині А, породжує розбиття цієї множини на класи еквівалентності.

Означення: Множина відмінних між собою класів еквівалентності називається фактор-множиною множини А за відношенням R і позначається так:

А \ R = {[a] | a є M}.

Відношення порядку. Впорядковані множини

Означення: Відношення R на множині А називається відношенням нестрогого порядку, якщо воно є рефлексивним, антисиметричним і транзитивним (≤).

Означення: Множину А, на якій введено відношення нестрогого порядку R, називають нестрого впорядкованою множиною та позначають (A, R)

Означення. Два елементи a та b нестрого впорядкованої множини називаються порівняльними, якщо a ≤ b U b ≤ a, при цьому, якщо a ≤ b, то кажуть, що елемент а не є більшим за елемент b, або елемент b не є меншим за елемент а.

Якщо Якщо ж елементи а і b є такими, що (a;b) ¢ (≤) ^ (b;a) є (≤), то вони називаються не порівняльними.

Означення. Якщо множина (A,R) є нестрого впорядкованою де два різні елементи є порівняльними, то така множина називається лінійно (цілком) нестрого впорядкованою, а порядок R називається лінійним (повним) порядком. Якщо ж існують непорівняльні елементи, то (A,R) називають частково впорядкованою множиною, а відношення R – частковим порядком.

Означення. Булевим вектором (кортежем) довжини n

називається вектор (a₁;a₂;…;a_n) є Bⁿ, B= (0;1)

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

Теорема. Якщо відношення R є нестрогого (строгого) порядку на множині А, то R^-1 є також відношенням нестрогого (строгого) порядку на A.

Теорема Цермело. Впорядкувати можна довільну, не лише числову множину.

(Аксіома вибору)

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

Міноранти та мажоранти. Найменший і найбільший елементи.

Розглянемо підмножину M^’ впорядкованої за відношенням R множини М.

Означення. Елемент m_λ Є М називається мажорантою множини М^’ , якщо

будь-яке m Є М’ : m ≤ m_λ ,

А елемент m_β Є М називається мінорантою множини М^’ , якщо

будь-яке m Є М’ : m_β ≤ m .

Означення. Якщо m_λ Є М’ , то m_λ називається максимальним елементом множини М’, а якщо m_β Є М’, то m_β називається мінімальним елементом множини М’. Позначаються m_λ = max (M’,R) , m_β = min (M’,R)

(M’)^- = {a Є M | a ≤ x будь-яке x Є M’} – сукупність усіх мінорант,

(M’)⁺ = {a Є M | x ≤ a будь-яке x Є M’} – сукупність усіх мажорант.

Означення. sup M’ = min (M’)⁺ - точна верхня грань множини М’, inf M’ = max (M’)^- - точна нижня грань множини M’.

Теорема. Впорядкована множина М має не більше ніж один максимальний (мінімальний) елемент.