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

UptoLike

Теория множеств
20
15.
Докажите, что если
ρ
- транзитивное и симметричное бинарное
отношение на множестве
Α
ΑΑ
Α
, область определения которого совпадает с
Α
ΑΑ
Α
,
то
ρ
рефлексивно.
§ 3. Специальные бинарные отношения
Рефлексивное, симметричное и транзитивное отношение
ρ
на
множестве
Χ
ΧΧ
Χ
называется отношением эквивалентности на множестве
Χ
ΧΧ
Χ
.
Для отношения эквивалентности вместо записи
()
ρ
yx
,
часто используют
запись
yx
(читается :
x
эквивалентен
y
)
Классом эквивалентности, порожденным элементом
x
, называется
подмножество множества
Χ
ΧΧ
Χ
, состоящее из тех элементов
Χ
ΧΧ
Χ
y
, для
которых
()
ρ
yx
,
. Класс эквивалентности, порожденный элементом
x
,
обозначается через
[]
x
:
[]
(){}
.,:
ρ
=
yxyx
Χ
ΧΧ
Χ
Разбиением множества
Χ
ΧΧ
Χ
называется совокупность попарно
непересекающихся подмножеств
Χ
ΧΧ
Χ
таких, что каждый элемент множества
Χ
ΧΧ
Χ
принадлежит одному и только одному из этих подмножеств. Всякое
разбиение множества
Χ
ΧΧ
Χ
определяет на
Χ
ΧΧ
Χ
отношение эквивалентности
ρ
:
()
ρ
yx
,
тогда и только тогда, когда
x
и
y
принадлежат одному
подмножеству разбиения. С другой стороны, всякое отношение
эквивалентности
ρ
определяет разбиение множества
Χ
ΧΧ
Χ
на классы
эквивалентности относительно этого отношения.
Совокупность классов эквивалентности элементов множества
Χ
ΧΧ
Χ
по
отношению эквивалентности
ρ
называется фактор-множеством множества
Χ
ΧΧ
Χ
по отношению
ρ
и обозначается
ρ
/
Χ
ΧΧ
Χ
.
Рефлексивное, антисимметричное и транзитивное отношение
называется отношением частичного порядка на множестве
Χ
ΧΧ
Χ
и вместо
записи
()
ρ
yx
,
для данного отношения часто используют запись
yx
.
Отношение частичного порядка на множестве
Χ
ΧΧ
Χ
, для которого любые два
элемента сравнимы, т.е. для любых
Χ
ΧΧ
Χ
yx
, выполнено либо
yx
, либо
xy
, называется отношением линейного порядка. Множество
Χ
ΧΧ
Χ
с
заданным на нем частичным (линейным) порядком называется частично
(линейно) упорядоченным.
Пусть
Χ
ΧΧ
Χ
- непустое конечное множество, на котором задано отношение
частичного порядка. Запишем
yx <
, если
yx
и
yx
. Говорят, что
элемент
y
покрывает элемент
x
, если
yx <
и не существует такого элемента
u
, что
yux <<
. Для
yx <
можно записать
yxxxx
n
=<<<=
...
21
, где
1
+
i
x
покрывает
i
x
.
Частично упорядоченные множества можно изображать с помощью так
называемых диаграмм Хассе. На диаграмме Хассе элементы частично