Некоторого отношения эквивалентности
Теорема 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. Линейное упорядоченное множество называется вполне упорядоченным, если любое его непустое подмножество содержит наименьший элемент. Пример. < ℕ, £ > - вполне упорядоченное множество.
Популярное: Как выбрать специалиста по управлению гостиницей: Понятно, что управление гостиницей невозможно без специальных знаний. Соответственно, важна квалификация... Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние... Как распознать напряжение: Говоря о мышечном напряжении, мы в первую очередь имеем в виду мускулы, прикрепленные к костям ... ©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (344)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |