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

UptoLike

Составители: 

22
Пример 2. Пусть
m
некоторое натуральное число. Проверить, яв-
ляется ли отношением эквивалентности следующее бинарное отношение
на множестве целых чисел:
(
)
{
}
mнаделитсяyxyx
-
´
Î
=
:,
Z
Z
r
.
Построить фактор-множество
r
Z
.
Решение. Проверим три основных свойства для отношения эквива-
лентности.
1. Рефлексивность.
Для произвольного
Z
Î
x
разность
(
)
r
Î
Þ
×
=
=
-
xxmxx ,00 .
2. Симметричность.
Пусть
(
)
(
)
.,,
r
r
Î
Þ
×
-
=
-
Î
$
Þ
×
=
-
Î
$
Þ
Î
xymkxykmkyxkyx
Z
Z
3. Транзитивность.
Пусть
(
)
(
)
Þ
×
=
-
×
=
-
Z
Î
$
Þ
Î
Î
mnzy,mkyxn,kz,y,y,x
r
r
(
)
(
)
(
)
r
Î
Þ
×
=
-
Z
Î
+
=
$
Þ
×
+
=
-
Z
Î
$
Þ
z,xmrzxmkrmnkzxn,k
.
Итак, исследуемое бинарное отношение является отношением экви-
валентности. Построение классов эквивалентности начнем с класса экви-
валентности, порожденного
Z
Î
0
[
]
{
}
{
}
=
-
Î
=
»
Î
=
mнаделитсяyyyy 0:0:0
Z
Z
{
}
{
}
=
×
-
=
Î
$
Î
=
×
=
-
Î
$
Î
=
mkykymkyky
Z
Z
Z
Z
:0:
{
}
,...,,...,3,3,2,2,,,0 kmkmmmmmmm
-
-
-
-
=
.
Если
1
=
m
, то данный класс эквивалентности
[
]
Z
=
0 , других клас-
сов эквивалентности просто не существует, и
[
]
{
}
0/
=
r
Z
. Если
1
>
m
, то
существуют элементы, не попавшие в построенный класс, например, эле-
мент 1. Построим класс эквивалентности, порожденный 1
[
]
{
}
{
}
=
-
Î
=
»
Î
=
mнаделитсяyyyy 1:1:1
Z
Z
{
}
{
}
=
×
-
=
Î
$
Î
=
×
=
-
Î
$
Î
=
mkykymkyky 1:1:
Z
Z
Z
Z
{
}
,...1,1,...,31,31,21,21,1,1,1 kmkmmmmmmm
+
-
+
-
+
-
+
-
=
.
При
2
=
m
построенные два класса эквивалентности при объедине-
нии дают все множество
,
Ζ
и поэтому построение классов эквивалентно-
сти закончено, в противном случае существует элемент, например 3, не
попавший ни в один из этих классов эквивалентности, и нужно перейти к
построению класса эквивалентности, порожденного 2. Продолжая данный
процесс, при любом
m
мы построим классы эквивалентности
[
]
[
]
[
]
1,...,1,0
-
m ,
которые не пересекаются и при объединении дают все множество
Z
. Та-
ким образом,
{
}
{
}
1,...,2,1:,...,,...,,,/
-
=
+
-
+
-
=
mnkmnkmnmnmnn
r
Z
.