PR_SEM4 (Семинары)

Семинар 4.Специальные свойства бинарных отношенийОпределение 4.1. Бинарное отношение ρ ⊆ A2 называется:1) рефлексивным, если idA ⊆ ρ , т.е.(∀x ∈ A)((x, x) ∈ ρ);2) иррефлексивным, если idA ∩ρ = ∅ , т.е.(∀x ∈ A)((x, x) ∈/ ρ);3) симметричным, если ρ−1 = ρ , т.е.(∀x∀y)((x, y) ∈ ρ ⇒ (y, x) ∈ ρ);4) антисимметричным, еслиρ ∩ ρ−1 ⊆ idA , т.е.(∀x∀y)(((x, y) ∈ ρ ∧ (y, x) ∈ ρ) ⇒⇒ (x = y))(в частности, м. б., что ρ ∩ ρ−1 = ∅ !);Эквивалентное определение:(∀x∀y)(((x, y) ∈ ρ ∧ x 6= y) ⇒⇒ ((y, x)) ∈/ ρ).5) транзитивным, если ρ ◦ ρ ⊆ ρ , т.е.(∀x∀y∀z)(((x, y) ∈ ρ ∧ (y, z) ∈ ρ) ⇒⇒ ((x, z) ∈ ρ));6) плотным, если(∀x∀y)(((x, y) ∈ ρ ⇒ (∃z)((z 6= x)∧∧ (z 6= y) ∧ ((x, z) ∈ ρ) ∧ ((z, y) ∈ ρ)).Определение 4.2. Бинарное отношение называется:1) эквивалентностью, если оно рефлексивно, симметрично и транзитивно;2) толерантностью, если оно рефлексивно и симметрично,3) порядком (или частичным порядком), если оно рефлексивно, антисимметричнои транзитивно;4) предпорядком (или квазипорядком), если оно рефлексивно и транзитивно;5) строгим порядком, если оно иррефлексивно, антисимметрично и транзитивно;6) строгим предпорядком, если оно иррефлексивно и транзитивно;Можно говорить: отношение эквивалентности, толерантности, порядка, предпорядка”.

. . “ и т.п.1СЕМИНАР 4.2Пример 4.1.а) Рассмотрим отношение ρ на множестве всех подмножеств некоторого множестваU : A ρ B ⇔ A ∩ B 6= ∅ и ∅ ρ ∅. Покажем, что это отношение толерантности:Поскольку для любого множества A ∈ U, A 6= ∅, A∩A = A 6= ∅ и ∅ ρ ∅, отношениеρ является рефлексивным.Поскольку из A ∩ B 6= ∅ следует, что B ∩ A 6= ∅, отношение ρ являетсясимметричным.Вывод: это отношение толерантности.Покажем, что ρ — не эквивалентность.Поскольку из A ∩ B 6= ∅ и B ∩ C 6= ∅ , никак не следует, что A ∩ C 6= ∅, что легковидеть из диаграммы, отношение ρ не транзитивно.б) Зададим на множестве натуральных чисел N следующее отношение: a | b = a”делит (является делителем) b “.Это отношение рефлексивно, поскольку любое число является делителем самого себя.Покажем антисимметричнсть.Пусть a делит b и, с другой стороны, b делит a .

Тогда найдется натуральное числоt1 , такое, что b = at1 , и найдется t2 , такое, что a = bt2 . Отсюда b = bt2 t1 , что намножестве натуральных чисел возможно только при t1 = t2 = 1 . Следовательно, a = b .Покажем транзитивность.Если a делит b , а b делит c , то найдутся такие натуральные числа t1 , t2 , такие,что b = at1 и c = bt2 . Отсюда имеем c = at1 t2 , т.е. a — делитель c .Таким образом, отношение делимости на множестве N является отношением порядка.Если распространить это отношение на множество целых чисел, то оно будет ужетолько предпорядком, поскольку не будет антисимметричным.

Например, 2 делится на−2 , и −2 делится на 2 , однако 2 6= −2 .в) Рассмотрим множество всех подмножеств множества A — B(A) . Покажем, чтоотношение включения ⊆ на множестве B(A) есть порядок.Это отношение рефлексивно, т.к. для любого множества X справедливо X ⊆ X .Поскольку для любых двух множеств X и Y из (X ⊆ Y ) и (Y ⊆ X) следует, чтоX = Y , рассматриваемое отношение антисимметрично.Из определения включения вытекает, что если (X ⊆ Y ) и (Y ⊆ Z) , то X ⊆ Z .Следовательно, отношение транзитивно.4.1. Исследовать свойства (рефлексивность, иррефлексивность, симметричность, антисимметричность, транзитивность) следующих отношений:(а) M = {a, b, c, d} ,Φ = {(a, a), (a, b), (c, a),(b, d), (a, d), (b, c)};(б) m ρ k , если m − k делится на n , где m ∈ Z , k ∈ Z , n ∈ Z ;(в) x ϕ y, если (x − y) ≤ 2 , x ∈ R , y ∈ R .4.2.

Пусть X = {x | x ∈ [0, 1]} , ρ = {(x, y) | x, y ∈ X, x < y и |x − y| < 0.5} . Построитьграфики отношений ρ и ρ−1 . Исследовать свойства отношения ρ . Что можно сказать освойствах обратного отношения?4.3. Отношение σ связывает клетки шахматной доски: две клетки связаны, если содной на другую можно перейти ходом коня.

Записать отношение с помощью логическихвысказываний, исследовать его свойства.4.4. Пусть τ и π — отношения на N × N : (a, b) τ (c, d) , если a ≤ c и b ≤ d ;(a, b) π (c, d) , если a ≤ c и b ≥ d . Являются ли τ и π отношениями порядка и почему?4.5. Пусть υ определено на множестве положительных рациональных чисел:(a/b)υ(с/d) , если ad ≤ bc . Показать, что υ является отношением линейного порядка.4.6. Пусть A — произвольное множество и ρ , σ — отношения на множестве 2A × 2A( прямом произведении множества всех подмножеств A на себя).(а) (P, Q)σ(X, Y ) , если (P ⊆ X) и (Q ⊆ Y ) ;(б) (P, Q)ρ(X, Y ) , если (P 4Q) ⊆ (X4Y ) ;СЕМИНАР 4.3Являются ли ρ и σ отношениями порядка?4.7.

Рассмотрим множество квадратных матриц размером 2 × 2 , элементами которыхявляются целые числа. Является ли заданное ниже отношение τ отношением порядка?Линейного порядка?(а) Aτ B , если aij ≤ bij , i, j = 1, 2 ;(б) Aτ B , если aij ≤ bij , i, j = 1, 2 и хотя бы для одной пары элементов неравенствострогое.4.8. Пусть F — множество функций, непрерывных на [a, b] . Исследовать свойстваотношения τ :Z bZ b(а) f (x)τ g(x) , еслиf (x) dx =g(x) dx .

Является ли τ отношением эквивалентности?aZaZb(б) f (x)τ g(x) , еслиbf (x) dx ≤ag(x) dx .Является ли τ отношением порядка?a4.9. Пусть M —некоторое множество, а 2M \{∅} — множество всех его подмножествбез пустого множества. Два множества из 2M связаны отношением τ , если они имеютхотя бы одно непустое общее подмножество. Является ли в общем случае τ отношениемпорядка. Какими свойствами будет обладать отношение τ , если M = {a, b}.