Некоторого отношения эквивалентности
Теорема 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={1}, A2={2}, A3={3}.
Решение: По правилу (**) R = {(1,1), (2,2), (3,3)}.
2) C1= {1, 2}, C2= {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. Линейное упорядоченное множество называется вполне упорядоченным, если любое его непустое подмножество содержит наименьший элемент.
Пример. < ℕ, £ > - вполне упорядоченное множество.