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

UptoLike

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