Отношение эквивалентности.

Определение. Бинарное отношение называется отношением эквивалентности, если оно обладает свойствами рефлексивности, симметричности и транзитивности.

Определение. Пусть – отношение эквивалентности, заданное на множестве и . Тогда называется классом эквивалентности, порожденным элементом .

Теорема. Пусть – отношение эквивалентности, заданное на множестве и . Тогда для класса эквивалентности выполняются:

1. ;

2. ;

3. .

4. 

Доказательство.

1. Так как бинарное отношение рефлексивно, то , следовательно, .

2. Так как , то , тогда и (симметричность), следовательно (транзитивность) , т.е. , и значит . Аналогично, нетрудно показать, что , т.е. . На основании метода встречных включений заключаем, что .

3. На основании 2. достаточно показать, что если , то . Предположим, что , тогда существует элемент и . Но тогда из 1. и 2. и и значит . Получили противоречие с тем, что .

4. Из 1. следует, что , обратное включение следует из определения класса эквивалентности. Следовательно,

Теорема. Пусть – отношение эквивалентности, заданное на множестве . Различные классы эквивалентности образуют разбиение множества .

Доказательство. Непосредственно следует из 3. и 4. доказанной теоремы.

Теорема. Всякое разбиение множества порождает на нем отношение эквивалентности.

Доказательство. Пусть – отношение, заданное на множестве такое, что . Следовательно, для выполняются свойства рефлексивности, симметричности и транзитивности, т.е. это отношение, является отношением эквивалентности.

Определение. Пусть – отношение эквивалентности, заданное на множестве . Множество всех классов эквивалентности называется фактор множеством множества по отношению эквивалентности .

Обозначается: .

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

(Лекция 4.)

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

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

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

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

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

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

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

Определение. Пусть – отношение порядка на множестве . Элемент называется наименьшим (наибольшим) в , если .

Определение. Пусть – отношение порядка на множестве . Элемент называется минимальным (максимальным), если из всегда следует, что .

Упорядоченное множество может иметь несколько минимальных и максимальных элементов.

Определение. Линейно упорядоченное множество называется вполне упорядоченным, если каждое непустое подмножество множества имеет наименьший элемент.