Отношение эквивалентности. Классы эквивалентности и их свойства. Разбиения множеств. Связь эквивалентности с разбиением (теоремы с доказательством)

Рефлексивное, симметричное и транзитивное отношение, заданное на множестве А, называется отношением эквивалентности на множестве А, т.е:

1.

2. х,у

3. ,y,z , х

Классом эквивалентности [х], порожденным элементом х А, называется подмножество множества А, состоящее из тех и только тех элементов у, которые состоят в отношении эквивалентности с х, т.е. [х]={y: x=y, y }. Множество классов эквивалентности А\R называется фактор-множеством множества А по эквивалентности R: A\R={[x]:x A}.

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

1. . В самом деле х => х [x]

2. Класс эквивалентности порождается любым своим элементом, т.е. х у => [x]=[y]

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

Совокупность множеств А₁,А₂,…,А_n называется разбиением множества А, если выполняются два условия: А₁vA₂v…vA_n=A и = , i j, j=1..n.

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

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

Доказательство. Разбиение с непустыми элементами может быть построение по отношению к эквивалентности следующим образом:

1. Выбрать произвольный элемент а A

2. Построить класс эквивалентности [a]

3. A:=A\[a]; A:=A {[a]}

4. Если А непусто, перейти к шагу 1

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

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

Отношение порядка. Строгий и нестрогий порядок. Частичный и полный порядок. Упорядоченные множества.

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

1. .

2. .

Если ≺ - рефлексивно, то ≺ - нестрогий порядок.

Если ≺ - антирефлексивно, то ≺ - строгий порядок.

Если ≺ - связно, то ≺ - полный (линейный) порядок.

Если ≺ - несвязно, то ≺ - частичный порядок.

Например: Отношение на множестве чисел – строгий полный порядок, отношение - нестрогий полный порядок. Отношение с – строгий частичный порядок на булеане . Схема организации подчинения – отношения строгого частичного порядка на множестве должностей.

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