Свойства классов эквивалентности

1. Ø.

В самом деле, , .

2. Класс эквивалентности порождается любым своим элементом, т.е. .

В самом деле, пусть , тогда если , то , при этом , следовательно, . Это значит, что . С другой стороны, если , то . Так как , то . Из того, что и , следует , значит .

3. Различные классы эквивалентности друг с другом не пересекаются, т.е. , то Ø.

Доказательство от противного: пусть и Ø. Последнее означает, что , следовательно, т.е. или значит .

Совокупность множеств , , …, называется разбиением множества А, если выполняются два условия:

1. ;

2. = Ø, , .

Например, разбиением множества натуральных чисел является набор из множества четных и множества нечетных натуральных чисел; разбиением множества студентов ВУЗа является множество студенческих групп.

Между разбиением множества и эквивалентностью, заданной на этом множестве существует связь, которая устанавливается следующими теоремами.

Теорема 1. Всякое отношение эквивалентности на множестве А определяет разбиение множества А, причем среди элементов разбиения нет пустых.

Требуемое разбиение обеспечивается алгоритмом:

1. Пусть , Ø.

2. Возьмем , построим его класс эквивалентности .

3. Удалим класс Х из множества: .

4. Добавим класс Х в разбиение: .

5. Если Ø, то разбиение построено, в противном случае переходим к шагу №2.

Теорема 2. Всякое разбиение на множестве А, не содержащее пустых элементов,определяет отношение эквивалентности на этом множестве (без доказательства).

Рассмотрим отношение эквивалентности R на множестве А. Множество классов эквивалентности называется фактормножеством множества А по эквивалентности R:

.

Например, фактормножеством множества студентов ВУЗа по отношению «учиться в одной студенческой группе» является множество студенческих групп.