Дискретная математика. Элементы теории задачи и упражнения. Булгакова И.Н - 22 стр.

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,...}.
Если m =1 , то данный класс эквивалентности [0] =Ζ , других классов эк-
вивалентности просто не существует, и Ζ / ρ ={[0]}. Если m >1 , то суще-
ствуют элементы, не попавшие в построенный класс, например, элемент 1.
Построим класс эквивалентности, порожденный 1
[1] ={y ∈Ζ : 1 ≈ y}={y ∈Ζ : 1 −y делится на m}=
={y ∈Ζ : ∃k ∈Ζ 1 −y =k ⋅ m}={y ∈Ζ : ∃k ∈Ζ y =1 −k ⋅ m}=
={1,1 −m,1 +m,1 −2m,1 +2 m,1 −3m,1 +3m,...,1 −km,1 +km,...}.
При m =2 построенные два класса эквивалентности при объединении да-
ют все множество Ζ и поэтому построение классов эквивалентности за-
кончено, в противном случае существует элемент, например 3, не попав-
ший ни в один из этих классов эквивалентности, и нужно перейти к по-
строению класса эквивалентности, порожденного 2. Продолжая данный
процесс, при любом m мы построим классы эквивалентности
                                 [0], [1],..., [m −1],
которые не пересекаются и при объединении дают все множество Ζ . Та-
ким образом,
          Ζ / ρ ={{n, n −m, n +m,..., n −km, n +km,...}: n =1, 2,..., m −1}.

        Пример 3. На плоскости Ρ выбрана некоторая декартова прямо-
угольная система координат. На Ρ заданы три отношения эквивалентно-
сти:
              ρ1 ={((a1 , a 2 ), (b1 , b2 ))∈Ρ ×Ρ : a1 =b1 , a 2 −b2 ∈Ζ };
              ρ2 ={((a1 , a2 ), (b1 , b2 ))∈Ρ ×Ρ : a1 −b1 ∈Ζ , a 2 −b2 ∈Ζ };
              ρ3 ={((a1 , a2 ), (b1 , b2 ))∈Ρ ×Ρ : a1 −b1 +a 2 −b2 ∈Ζ }.
Найдите фактор-множества для данных отношений эквивалентности.
        Решение. Построим фактор-множество для отношения ρ1 . Класс эк-
вивалентности, порожденный произвольным элементом (a1 , a2 )∈Ρ , име-
ет вид
[(a1 , a2 )] ={(x, y )∈Ρ : ((a1 , a2 ), (x, y ))∈ρ1}={(x, y )∈Ρ : x =a1 , a2 −y ∈Ζ }=
={(x , y )∈Ρ : ∃k ∈Ζ x =a1 , a2 −y =k }=
={(x, y )∈Ρ : ∃k ∈Ζ x =a1 , y =a 2 −k}=