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

UptoLike

(
)
{
}
Ζ
Ρ
=
kkaa :,
21
.
Таким образом, в класс эквивалентности, порожденный элементом
(
)
Ρ
21
, aa 10,
21
<
aRa , попадают вместе с элементом
(
)
Ρ
21
, aa
элементы, у которых первая координата равна
1
a , а вторая координата от-
личается от
2
a
на целое число. Классы эквивалентности, порожденные
элементами с 10,
21
<
aRa , не пересекаются и в объединении дают
все множество
Ρ
. Следовательно, фактор-множество
1
/
ρ
Ρ
можно запи -
сать в виде
(
)
[
)
{
}
1,0,:}:,{/
1
+
=
β
α
β
α
ρ
Rkk
Ζ
Ρ
.
Фактор-множество для отношений
32
,
ρ
ρ
постройте самостоятель-
но.
Пример 4. Придумайте минимальное (по числу элементов) отноше-
ние эквивалентности
ρ
на множестве
{
}
5,4,3,2,1
=
Α
так, чтобы
(
)
ρ
2,1 и
(
)
ρ
3,2 .
Решение. Отношение эквивалентности рефлексивно, поэтому дан-
ному отношению обязательно должны принадлежать пары
(
)
1,1
,
(
)
2,2
,
(
)
3,3
,
(
)
4,4 ,
(
)
5,5 . Отношение эквивалентности симметрично, поэтому на-
ряду с парами
(
)
2,1
,
(
)
3,2
данному отношению обязаны принадлежать пары
(
)
1,2
,
(
)
2,3
. В силу транзитивности отношения
ρ
ему обязана принадле-
жать вместе с парами
(
)
2,3 ,
(
)
1,2 пара
(
)
1,3 ( и, следовательно,
(
)
3,1 ). Та -
ким образом, минимальное отношение эквивалентности, которое мы мо-
жем построить, имеет вид
{
}
3113233212215544332211 ,,,,,,,,,,,,,,,,,,,,,
=
ρ
.
Пример 5. Докажите, что
{
}
{
}
{
}
{
}
{
}
7643521 ,,,,,,
=
Μ
- разбиение мно-
жества
{
}
7654321 ,,,,,,
=
Α
и перечислите все элементы отношения эквива -
лентности
ρ
, соответствующего разбиению
Μ
.
Решение.
Μ
является разбиением множества
Α
, поскольку множе-
ства , являющиеся элементами множества
Μ
, не пересекаются и при объе-
динении дают все множество
Α
. Отношение эквивалентности,
соответствующее данному разбиению , строится по правилу
(
)
ρ
yx , тогда
и только тогда, когда
x
и
y
принадлежат одному подмножеству
разбиения, т.е.
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
()()()()()
=
3,3,6,7,7,6,4,7,7,4
,4,6,6,4,7,7,6,6,4,4,2,5,5,2,5,5,2,2,1,1
ρ .
Пример 6. Покажите, что объединение двух отношений эквивалент-
ности может не являться отношением эквивалентности.
Решение. На множестве
{
}
5,4,3,2,1
=
Α
рассмотрим два отношения
эквивалентности