Классы эквивалентности

Пусть ε – отношение эквивалентности на множестве А. а  А.

Опр. Классом эквивалентности, образованным элементом а называется множество элементов х  А, таких что х ~ а. Обозначается класс эквивалентности через .

Если отношение ε – эквивалентность на множестве Z, заданная следующим образом: а ε b ↔ а и b имеют одинаковые остатки при делении на 3, то  = {х Z / х ~ 1}. Легко видеть, что числа эквивалентные единице, это все числа, которые при делении на 3 дают остаток 1, поэтому можно записать следующее:

 = {х Z / х = 3к + 1, к Z}. Аналогично,  = { х Z / х = 3к + 2, к Z}и т. д.

Классы эквивалентности обладают следующими свойствами:

1. Каждый класс эквивалентности не пустой.

В силу свойства рефлексивности а .

2. Если b , то  = , т. е. класс эквивалентности однозначно определяется любым своим элементом.

Пусть b , т. е. b ~ а. Для доказательства = воспользуемся определением равных множеств, т. е.  = тогда и только тогда, когда и .

Покажем, что . Пусть u , тогда u ~ b и по условию b ~ а. По свойству транзитивности имеем, что u ~ а. Следовательно, u . По определения включения . Аналогично доказывается, что . Т. о.  = . Свойство доказано.

3. Классы эквивалентности совпадают или не пересекаются.

Доказательство. Пусть имеются классы эквивалентности , . Если  = Ø, то свойство верно. Предположим, что  ≠ Ø. Т. е. существует элемент с . По определению пересечения, с  и с . Из предыдущего свойства следует, что т. к. с , то  =  и т. к. с , то  = .Получаем. что  = , т. е. классы эквивалентности совпали. Свойство доказано.

4. Объединение классов эквивалентности составляет множество А, т. е.  = А.

Для доказательства достаточно воспользоваться определением равенства двух множеств.  = А тогда и только тогда, когда А и А , т. е. показать, что любой элемент х  будет принадлежать множеству А и наоборот.

Разбиение множества

Множество всех различных классов эквивалентности множества А по эквивалентности ε обозначается через А/ ε и называется фактор – множеством множества А по эквивалентности ε.

По сути, отношение эквивалентности является обобщением понятия равенства. Некоторый общий способ задания отношений эквивалентности на произвольном множестве А связан с понятием разбиения множества.

Опр. Система непустых подмножеств множества А называется разбиением множества А, если выполнены условия:

1. Подмножества не пересекаются;

2. Объединение подмножеств составляет множество А.

Разбиение множества обозначается символом S(А).

Пример. А = Z

Разбиение множества Z  составляют такие подмножества целых чисел: А₁ = {0}, А₂ = {Z⁺}, А₃ = {Z^-}. Имеет место запись S(Z) = {А₁, А₂, А₃}

Связь между эквивалентностью и разбиением выражена следующей теоремой:

Теорема. Любое отношение эквивалентности на множестве вызывает разбиение этого множества . Любое разбиение множества задает на этом множестве отношение эквивалентности.

Доказательство. Покажем, что отношение эквивалентности ε на множестве А вызывает разбиение этого множества S(А) . Т. к. на множестве А задана эквивалентность ε, то можно рассмотреть классы эквивалентности . Выберем все различные классы эквивалентности и составим из них множество – фактор множество множества А по эквивалентности ε - А/ ε. Сравним S(А) и А/ ε. Они оба состоят из подмножеств множества А и обладают одинаковыми свойствами. Т. е. S(А) = А/ ε. Т.о. фактор множества множества А по эквивалентности ε задает разбиение этого множества.

Покажем , что разбиение множества S(А) задает на этом множестве А отношение эквивалентности. Зададим бинарное отношение ρ по следующему правилу: для любых элементов а, b  А (а ρ b ↔ а и b принадлежат одному классу разбиения). Докажем, что ρ – эквивалентность. Для этого проверим следующие свойства:

1. рефлексивность

Свойство рефлексивности выполняется, т. к. для любого элемента а А найдется класс разбиения. Если бы такой класс не нашелся, то объединение классов разбиения не равнялось бы множеству А.

2. симметричность

Свойство симметричности выполняется, т. к. для любых двух элементов а, b А из того что а, b принадлежат классу разбиения А_х следует, что и b, а А_х.

3. транзитивность

Возьмем произвольные элементы а, b, с А, такие что а, b А_х и b, с А_у. Классы разбиения не пересекаются, т. е. А_х А_у = Ø. Следовательно А_х = А_у. А это значит, что а, в, с принадлежат одному классу разбиения. Свойство транзитивности выполняется.

Т. к. все три свойства выполняются, то ρ является отношением эквивалентности.

Терема доказана.

Отношение порядка

Опр. Отношение ρ на множестве А называется отношением порядка на множестве А, если оно транзитивно и антисимметрично.

Пример. Отношение ≥ на множестве Z является отношением порядка.

Опр. Отношение порядка ρ на множестве А называется отношением нестрогого порядка на множестве А, если оно рефлексивно.

Пример. Отношение делимости на множестве N является отношением нестрогого порядка.

Опр. Отношение порядка ρ на множестве А называется отношением строгого порядка, если оно антирефлексивно.

Пример. Отношение > на множестве R является отношением строгого порядка.

Опр. Отношение порядка ρ на множестве А называется отношением линейного порядка, если для любых х, у А либо х = у, либо х ρ у, либо у ρ х.

Пример. Отношение < на множестве Z является отношением линейного порядка.

Отношение порядка, не являющегося линейным, называется частичным порядком.

Пример. Пусть Р(N) множество всех подмножеств множества N. Отношение включения на множестве Р(N) – отношение частичного порядка.

Опр. Множество А на котором введено отношение порядка ρ называется упорядоченным. Если порядок линейный, то пара (А, ρ) называется линейно упорядоченным множеством. Если порядок частичный, то пара (А, ρ) называется частично упорядоченным множеством.