Некоторого отношения эквивалентности

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

Доказательство. Пусть A≠Æ и на А задано некоторое разбиение на классы. Зададим на множестве А бинарное отношение R по следующему правилу:

(а,в) Î R Û элементы а и в находятся в одном классе (**).

Покажем, что бинарное отношение R является отношением эквивалентности:

1) Покажем, что R рефлексивно. Пусть а Î А. Так какэлемент а находится в одном классе с самим собой, то по правилу (**) (а,а)Î R Þ R рефлексивно.

2) Покажем, что R симметрично. Пусть (а,в)Î R . Тогда по правилу (**) а и в находятся в одном классе Þ в и а находятся в одном классе. Отсюда по правилу (**) получаем, что (в,а)Î R Þ R симметрично.

3) Покажем, что R транзитивно. Пусть (а,в) Î R и (в,с)Î R. Тогда по правилу (**) а и в находятся в одном классе и в и с находятся в одном классе Þ а и с находятся в одном классе и по правилу (**) (а,с)Î R Þ R транзитивно.

Из 1)-3) Þ R - отношение эквивалентности. Теорема доказана.

Пример. Найти отношения эквивалентности, соответствующие разбиениям множества А={1,2,3} из примера 1 предыдущего вопроса.

1) А₁={1}, A₂={2}, A₃={3}.

Решение: По правилу (**) R = {(1,1), (2,2), (3,3)}.

2) C₁= {1, 2}, C₂= {3}.

Решение: По правилу (**) R ={(1,1), (2,2), (1,2), (2,1), (3,3)}.

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

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

Пример. £, ³, <, >, =.

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

Пример. £, ³, =.

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

Пример. <, >.

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

Пример. £, ³, =.

Замечание. Из свойств антирефлексивности и транзитивности следует свойство антисимметричночности.

По этому определение 31 равносильно определению 31’.

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

Пример. 1) Отношение делимости на множестве ℕ рефлексивно, антисимметрично, транзитивно. Следовательно, отношение делимости на множестве ℕ является отношением нестрогого порядка, а также отношением предпорядка.

2) Отношение делимости на множестве ℤ не антисимметрично, рефлексивно, транзитивно Þ отношение делимости на множестве ℤ – отношение предпорядка, но не является отношением порядка.

Определение 33. Бинарное отношение R на множестве А называется связанным (связным), если " а, в Î А, а в, выполняется одно и только одно из условий: либо (а,в) Î R, либо (в,а)Î R.

Пример. 1) Отношение < на множестве ℕ – связное.

2) Отношение Í на множестве P(U) не является связным.

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

Определение 35. Непустое множество А с заданным на нем отношением порядка R называется упорядоченным множеством и обозначается <А,R>.

Определение 36. Упорядоченное множество <А,R> называется линейно-упорядоченным, если R - отношение линейного порядка. Если R - отношение частичного порядка, то упорядоченное множество <А,R> называется частично-упорядоченным.

Определение 37. Пусть <А,R> - упорядоченное множество. Элемент аÎ А называется минимальным (максимальным) элементом множества А, если " x Î А:

из (х,а) Î R Þ x=a (из (а,х) Î R Þ x=a).

Во множестве может быть несколько минимальных и несколько максимальных элементов.

Пример. Пусть А={2, 3, 4, 6, 8, 12, 24} - множество всех натуральных делителей числа 24, отличных от 1. Покажем, что 2 - минимальный элемент множества А. Действительно, из того, что элемент х из А делит 2 Þ х=2. Аналогично проверяется, что 3 - минимальный элемент множества А.

Определение 38. Пусть <А,R> - упорядоченное множество. Элемент аÎ А называется наименьшим (наибольшим) элементом множества А, если "xÎА: (а,х)ÎR ( (х,а) Î R ).

Если во множестве есть наименьший элемент, то он единственен.

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

Пример. < ℕ, £ > - вполне упорядоченное множество.