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

UptoLike

Теория множеств
23
Фактор-множество для отношений
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 ). Таким образом,
минимальное отношение эквивалентности, которое мы можем построить,
имеет вид
()( )()( )( )()()( )( )()(){}
3,1,1,3,2,3,3,2,1,2,2,1,5,5,4,4,3,3,2,2,1,1
=
ρ
.
Задача 5
. Докажите, что
{}{ }{}{ }{}
7,6,4,3,5,2,1
=
Μ
ΜΜ
Μ
- разбиение
множества
{}
7,6,5,4,3,2,1
=
Α
ΑΑ
Α
и перечислите все элементы отношения
эквивалентности
ρ
, соответствующего разбиению
Μ
ΜΜ
Μ
.
Решение.
Μ
ΜΜ
Μ
является разбиением множества
Α
ΑΑ
Α
, поскольку
множества, являющиеся элементами множества
Μ
ΜΜ
Μ
, не пересекаются и при
объединении дают все множество
Α
ΑΑ
Α
. Отношение эквивалентности,
соответствующее данному разбиению, строится по правилу
()
ρ
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
=
Α
ΑΑ
Α
рассмотрим два отношения
эквивалентности
()()()()()()(){}
1,22,1,5,5,4,4,3,3,2,2,1,1
1
=
ρ
;
()()()()()()(){}
3,22,3,5,5,4,4,3,3,2,2,1,1
1
=
ρ
.
Объединение данных отношений эквивалентности
()()()()()()()()(){}
3,2,2,3,1,22,1,5,5,4,4,3,3,2,2,1,1
21
=
ρ
ρ
не является отношением эквивалентности, так как для него не выполнено
свойство транзитивности (
()
21
2,3
ρ
,
()
21
1,2
ρ
ρ
, а
()
21
1,3
ρ
ρ
).
Задача 7
. Докажите , что отношение
(){}
yxRRyx
×=
:,
ρ
является
отношением порядка на множестве
R
, является ли это отношение
отношением линейного порядка.