Мегаобучалка Главная | О нас | Обратная связь


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



2015-12-07 3041 Обсуждений (0)
Отношение эквивалентности. Классы эквивалентности и их свойства. Разбиения множеств. Связь эквивалентности с разбиением (теоремы с доказательством) 0.00 из 5.00 0 оценок




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

1.

2. х,у

3. ,y,z , х

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

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

 

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

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

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

Совокупность множеств А12,…,Аn называется разбиением множества А, если выполняются два условия: А1vA2v…vAn=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. .

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

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

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

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

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

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



2015-12-07 3041 Обсуждений (0)
Отношение эквивалентности. Классы эквивалентности и их свойства. Разбиения множеств. Связь эквивалентности с разбиением (теоремы с доказательством) 0.00 из 5.00 0 оценок









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

Обсуждений еще не было, будьте первым... ↓↓↓

Отправить сообщение

Популярное:



©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (3041)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.007 сек.)