Печать презентации сем4 (Семинары)

ОТНОШЕНИЯ И СООТВЕТСТВИЯСпециальные свойствабинарных отношений• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitБинарное отношение ρ ⊆ A2 называется:1) рефлексивным, если (∀x ∈ A)((x, x) ∈ ρ) ,т.е. idA ⊆ ρ .2) иррефлексивным, если (∀x ∈ A)((x, x) ∈/ ρ) ,т.е. idA ∩ρ = ∅ .3) симметричным, если (∀x∀y)((x, y) ∈ ρ ⇒ (y, x) ∈ ρ) ,т.е. ρ−1 = ρ .4) антисимметричным, если(∀x∀y)(((x, y) ∈ ρ ∧ (y, x) ∈ ρ) ⇒ (x = y))т.е. ρ ∩ ρ−1 ⊆ idA (в частности, м.

б., что ρ ∩ ρ−1 = ∅ !).Эквивалентное определение:(∀x∀y)(((x, y) ∈ ρ ∧ x 6= y) ⇒ ((y, x)) ∈/ ρ).• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit5) транзитивным, если(∀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) ∈ ρ)).• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitБинарное отношение называется:1) эквивалентностью, если оно рефлексивно, симметрично итранзитивно;2) толерантностью, если оно рефлексивно и симметрично;3) порядком (или частичным порядком), если оно рефлексивно,антисимметрично и транзитивно;4) предпорядком (или квазипорядком), если оно рефлексивно итранзитивно;5) строгим порядком, если оно иррефлексивно, антисимметрично итранзитивно;6) строгим предпорядком, если оно иррефлексивно и транзитивно;Говорят: отношение эквивалентности, толерантности, порядка, предпорядка . .”.

“ и т.п.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 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= ∅, что легко видеть что, отношение ρ не транзитивно.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 2.Зададим на множестве натуральных чисел N следующее отношение:a | b в том и только том случае, когда a является делителем b “.”Это отношение рефлексивно, поскольку любое число является делителемсамого себя.Покажем антисимметричнсть.Пусть a делит b и, с другой стороны, bделит a .Тогда найдется натуральное число t1 , такое, что b = at1 ,инайдется t2 , такое, что a = bt2 .Отсюда b = bt2t1 , что на множественатуральных чисел возможно только при t1 = t2 = 1 .Следовательно,a = b.Покажем транзитивность.Если a делит b , а b делит c , то найдутсятакие натуральные числа t1 , t2 , такие, что b = at1 и c = bt2 .

Отсюдаимеем c = at1t2 , т.е. a — делитель c .Таким образом, отношение делимости на множестве N является отношением порядка.Это отношение на множество целых чисел Z будет только предпорядком, поскольку не будет антисимметричным.Например, 2 делится на −2 , и −2 делится на 2 , однако 2 6= −2 .• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 3.Рассмотрим множество всех подмножеств множества A — 2(A) . Покажем, что отношение включения ⊆ на множестве 2(A) есть порядок.Это отношение рефлексивно, т.к.

для любого множества X справедливоX⊆X.Поскольку для любых двух множеств X и Y из (X ⊆ Y ) и (Y ⊆ X)следует, что X = Y , рассматриваемое отношение антисимметрично.Из определения включения вытекает, что если (X ⊆ Y ) и (Y ⊆ Z) ,то X ⊆ Z . Следовательно, отношение транзитивно.Таким образом, отношение рефлексивно, антисимметрично и транзитивно, т. е. это отношение порядка.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitЗадачи.4.1 Исследовать свойства (рефлексивность, иррефлексивность, симметричность, антисимметричность, транзитивность) следующих отношений:(а) M = {a, b, c, d} ,Φ = {(a, a), (a, b), (c, a), (b, d), (a, d), (b, c)};(б) 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 Пусть τ — отношение на N × N : (a, b) τ (c, d) , если a ≤ c иb ≤ d . Является ли τ отношением порядка и почему?4.4 Пусть υ определено на множестве положительных рациональныхчисел: (a/b)υ(с/d) , если ad ≤ bc . Показать, что υ являетсяотношением линейного порядка.• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit4.5 Пусть A — произвольное множество и σ — отношение намножестве 2A ×2A ( прямом произведении множества всех подмножествA на себя):(P, Q)σ(X, Y ), если(P ⊆ X) и (Q ⊆ Y );Является ли σ отношением порядка?4.6 Рассмотрим множество квадратных матриц размером 2 × 2 ,элементами которых являются целые числа.

Является ли заданное нижеотношение τ отношением порядка? Линейного порядка?(а) Aτ B , если aij ≤ bij , i, j = 1, 2 ;(б) Aτ B , если aij ≤ bij , i, j = 1, 2 и хотя бы для одной пары элементовнеравенство строгое.4.7 Пусть F — множество функций, непрерывных на [a, b] . Исследовать свойства отношенияτ: Z bZ bf (x) dx ≤f (x)τ g(x) , еслиaнием предпорядка? порядка?g(x) dx .Является ли τ отноше-a• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitОтношение эквивалентности.Определение 4.1. Бинарное отношение называется: эквивалентностью, если оно рефлексивно, симметрично и транзитивно.Определение 4.2.

Пусть ρ ⊆ A2 — экивалентность. Множество[x]ρ = {y | yρx}называют классом эквивалентности элемента x по отношению ρ .Определение 4.3. Множество всех классов эквивалентности поданному отношению эквивалентности ρ на множестве A называетсяфактор-множеством множества A по отношению ρ и обозначаетсяA/ρ , т.е.A/ρ = {[x]ρ | x ∈ A}.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 4.

На множестве целых чисел Z определим отношениеm ≡(mod 2) n ( m равно n по модулю 2 “ ) имеющее место тогда итолько тогда,”когда m − n делится на 2 : 2 | m − n .Это отношение рефлексивно и симметрично, поскольку m − m = 0делится на 2, и из того, что m − n делится на 2, вытекает, что n − mделится на 2.Покажем транзитивность. Пусть m ≡(mod 2) n и n ≡(mod 2) p.

Если m−nделится на 2 и n−p делится на 2, то числа m, n и p либо все четные,либо нечетные.Поэтому m−p делится на 2, что означает m ≡(mod 2) p.Таким образом, ≡(mod 2) — транзитивность.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitНайдем фактор-множество множества целых чисел Z по данномуотношению эквивалентности.Рассмотрим множество чисел, связанных отношением ≡(mod 2) с числом0. Разность некоторого числа n и 0 будет нацело делиться на 2 толькоесли число n — четное. Таким образом, [0]≡(mod 2) — множество четныхчисел.Рассмотрим множество чисел, связанных отношением ≡(mod 2) с числом1. Разность некоторого числа m и 1 будет нацело делиться на 2 толькоесли число m — нечетное.

Таким образом, [1]≡(mod 2) — множествонечетных чисел.В итоге получаем ровно 2 попарно различных классов эквивалентностипо данному отношению: [0]≡(mod 2) и [1]≡(mod 2) .Можем записатьZ/ ≡(mod 2) ∼ {0, 1}.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitЗадача 4.8 На множестве рациональных дробей вида a/b , a ∈ Z ,b ∈ N задано бинарное отношениеτ = {(a/b, c/d) | ad = cb}.Показать, что τ является отношением эквивалентности. Что является фактор-множеством множества рациональных дробей по данномуотношению?Задача 4.9 Пусть в R3 задана плоскость ax + by + cz = 0 .Точки с радиус-векторами r1 и r2 связаны отношением τ , если((r1 − r2), n) = 0 , где n — нормаль к плоскости, а (·, ·) — скалярноепроизведение.

Показать, что τ — отношение эквивалентности. Накакие классы эквивалентности разбивается R3 . Что будет фактормножеством множества R3 по данному отношению эквивалентности.Задача 4.10 Пусть F — множество функций, непрерывных на [a, b] .Исследовать свойстваZ отношенияZ τ:bf (x)τ g(x) , еслиbf (x) dx =aем эквивалентности?g(x) dx .

Является ли τ отношениa• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitИндексированное семейство множеств {Bi}i∈I называется разбиением [множества A , если:1)Bi = A ,i∈I2) если i 6= j , то Bi ∩ Bj = ∅ .Таким образом, разбиение множества A — это семейство попарно непересекающихся подмножеств A , объединение которых равно A .Например, множества [0, 1/3) , [1/3, 2/3) и [2/3, 1] образуют разбиениеотрезка [0, 1] .Теорема. Любое отношение эквивалентности определяет однозначно некоторое разбиение данного множества и обратно, любое разбиениемножества однозначно определяет некоторое отношение эквивалентности на нем.Задача 4.11 Пусть A — конечное множество.

Какое отношение эквивалентности на нем дает наибольшее число классов эквивалентности.Сколько? Сколькими способами можно задать отношение эквивалентности, разбивающее A на два класса?• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitДомашнее задание4.12 Отношение σ связывает клетки шахматной доски: две клеткисвязаны, если с одной на другую можно перейти ходом коня. Записатьотношение с помощью логических высказываний, исследовать его свойства.4.13 Пусть π — отношение на N × N : (a, b) π (c, d) , если a ≤ c иb ≥ d .

Является ли π отношением порядка и почему?4.14 Пусть A — произвольное множество и ρ — отношение намножестве 2A ×2A ( прямом произведении множества всех подмножествA на себя).(P, Q)ρ(X, Y ) , если (P 4Q) ⊆ (X4Y ) ;Является ли ρ отношением порядка?4.15 Пусть M —некоторое множество, а 2M \ {∅} — множествовсех его подмножеств без пустого множества. Два множества из 2Mсвязаны отношением τ , если они имеют хотя бы одно непустое общееподмножество. Является ли в общем случае τ отношением порядка.Какими свойствами будет обладать отношение τ , если M = {a, b}• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit4.16 Пусть f : R → R — отображение, и x1 τ x2 если и только еслиf (x1) = f (x2) .

Показать, что τ является отношением эквивалентности.Указать фактор-множество R/τ .• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit.