ВУЗ:
Составители:
Рубрика:
21
r
определяет разбиение множества
C
на классы эквивалентности отно-
сительно этого отношения.
Совокупность классов эквивалентности элементов множества
C
по
отношению эквивалентности
r
называется фактор-множеством множества
C
по отношению
r
и обозначается
r
/
C
.
Рефлексивное, антисимметричное и транзитивное отношение назы-
вается отношением частичного порядка на множестве
C
и вместо записи
(
)
r
Î
yx, для данного отношения часто используют запись
y
x
£
. Отноше-
ние частичного порядка на множестве
C
, для которого любые два элемен-
та сравнимы, т.е. для любых
C
Î
y
x
,
выполнено либо
y
x
£
, либо
x
y
£
,
называется отношением линейного порядка. Множество
C
с заданным на
нем частичным (линейным) порядком называется частично (линейно) упо-
рядоченным.
Пусть
C
– непустое конечное множество, на котором задано отноше-
ние частичного порядка. Запишем
y
x
<
, если
y
x
£
и
y
x
¹
. Говорят, что
элемент
y
покрывает элемент
x
, если
y
x
<
, и не существует такого элемен-
та
u
, что
y
u
x
<
<
. Для
y
x
<
можно записать yxxxx
n
=
<
<
<
=
...
21
, где
1+i
x покрывает
i
x .
Частично упорядоченные множества можно изображать с помощью
так называемых диаграмм Хассе. На диаграмме Хассе элементы частично
упорядоченного множества изображаются точками на плоскости, и если
элемент
y
покрывает элемент
x
, то точки
x
и
y
соединяются отрезком,
причем точку, соответствующую
x
, располагают ниже
y
.
Пример 1. Доказать, что бинарное отношение на множестве целых
чисел
(
)
{
}
yxyx
=
´
Î
=
:,
Z
Z
r
является отношением эквивалентности, и построить соответствующее ему
фактор-множество
r
/
Z
.
Решение. Проверку рефлексивности, симметричности и транзитив-
ности данного бинарного отношения выполните самостоятельно. Постро-
им классы эквивалентности для данного отношения эквивалентности.
Класс эквивалентности, порожденный любым элементом
Z
Î
x
, имеет вид
[
]
{
}
{
}
{
}
xyxyyxyx
=
=
Î
=
»
Î
=
::
Z
Z
.
Таким образом, для данного отношения эквивалентности класс экви-
валентности, порожденный элементом
Z
Î
x
, состоит только из этого эле-
мента
,
x
и фактор-множество
r
/
Z
имеет вид
{
}
{
}
Z
Z
Î
=
xx :/
r
.
Страницы
- « первая
- ‹ предыдущая
- …
- 19
- 20
- 21
- 22
- 23
- …
- следующая ›
- последняя »