Дискретная математика. Азарнова Т.В - 21 стр.

                                 21
Теория множеств
упорядоченного множества изображаются точками на плоскости, и если
элемент y покрывает элемент x , то точки x и y соединяются отрезком,
причем точку, соответствующую x , располагают ниже y .
      Задача 1. Доказать, что бинарное отношение на множестве целых
чисел
                          ρ ={(x, y )∈Ζ ×Ζ : x = y}
 является отношением эквивалентности, и построить соответствующее ему
фактор-множество Ζ / ρ .
      Решение.     Проверку       рефлексивности,    симметричности и
транзитивности данного бинарного отношения выполните самостоятельно.
Построим классы эквивалентности для данного отношения эквивалентности.
Класс эквивалентности, порожденный любым элементом x ∈Ζ , имеет вид
                  [x] ={y ∈Ζ : x ≈ y}={y ∈Ζ : x = y}={x}.
Таким образом, для данного отношения эквивалентности класс
эквивалентности, порожденный элементом x ∈Ζ , состоит только из этого
элемента x и фактор-множество Ζ / ρ имеет вид
                            Ζ / ρ ={{x}: x ∈Ζ }.

        Задача 2. Пусть m - некоторое натуральное число. Проверить,
является ли отношением эквивалентности следующее бинарное отношение
на множестве целых чисел:
                       ρ ={(x, y )∈Ζ ×Ζ : x −y делится на m}.
Построить фактор-множество Ζ / ρ .
        Решение. Проверим три основных свойства для отношения
эквивалентности.
1. Рефлексивность.
Для произвольного x ∈Ζ разность x −x =0 =0 ⋅ m ⇒ (x, x )∈ ρ .
2. Симметричность.
Пусть
(x, y )∈ ρ ⇒ ∃k ∈Ζ x −y =k ⋅ m ⇒ ∃k ∈Ζ y −x =−k ⋅ m ⇒ (y, x )∈ ρ.
3. Транзитивность.
Пусть
(x , y )∈ ρ, (y , z )∈ ρ ⇒ ∃k , n ∈Ζ x −y =k ⋅ m , y −z =n ⋅ m ⇒
⇒ ∃k , n ∈Ζ x −z =(k +n )⋅ m ⇒ ∃r =(k +m )∈Ζ x −z =r ⋅ m ⇒ (x , z )∈ ρ
        Итак, исследуемое бинарное отношение является отношением
эквивалентности. Построение классов эквивалентности начнем с класса
эквивалентности, порожденного 0 ∈Ζ
[0] ={y ∈Ζ : 0 ≈ y}={y ∈Ζ : 0 −y делится на m}=
={y ∈Ζ : ∃k ∈Ζ 0 −y =k ⋅ m}={y ∈Ζ : ∃k ∈Ζ y =−k ⋅ m}=
={0, m,−m,2m,−2m,3m,−3m,..., km,−km,...}.