Связанные определения
Множество всех классов эквивалентности обозначается .
Примеры отношений эквивалентности
Более сложный пример, но совершенно жизненно важный:
Когда врач выписывает вам лекарство, он, фактически в рецепте указывает класс эквивалентных лекарств, он не может указать совершенно конкретный экземпляр упаковки таблеток или ампул. Т.е. всевозможные лекарства разбиты на классы отношением эквивалентности. Если бы не этот факт, современная медицина просто не была бы возможна.
Таким образом, всевозможные рецепты салатов и коктейлей, ГОСТы и классификаторы также определяют жизненно важные отношения эквивалентности. Отношения эквивалентности заполняют всю нашу жизнь, а не являются абстрактной забавой математиков.
Факторизация отображений
Множество классов эквивалентности, отвечающее отношению эквивалентности , обозначается символом и называется фактор-множеством относительно . При этом сюръективное отображение
называется естественным отображением (или канонической проекцией ) на фактор-множество .
Пусть , - множества, - отображение, тогда бинарное отношение определённое правилом
является отношением эквивалентности на . При этом отображение индуцирует отображение , определяемое правилом
или, что то же самое,
.При этом получается факторизация отображения на сюръективное отображение и инъективное отображение .
Факторизация отображения широко применяется в гуманитарных науках и в тех областях техники, где нет возможности использовать числовые значения. Факторизация отображения позволяет обходиться без формул там, где формулы применять не удается. Приведем пример, который будет понятен любому и не потребует разбираться в сложной математической символике.
Расписание занятий в школе – это типичный пример факторизации. В данном случае – множество всех учащихся школы, - множество всех учебных предметов, разнесенных по дням недели с уточнением времени проведения занятий. Классами эквивалентности являются классы (группы учащихся). Отображение – расписание занятий, отображаемое в дневниках учащихся. Отображение - расписание занятий по классам, вывешиваемое в вестибюле школы. Здесь же имеется и отображение – списки классов. Этот пример очень наглядно демонстрирует практические выгоды факторизации: невозможно представить себе расписание занятий, как таблицу, в которой отражены все ученики школы в персональном порядке. Факторизация позволила отобразить нужную учащимся информацию в удобном для применения компактном виде в ситуации, где формулы применить не удается.
Однако этим выгоды факторизации не ограничены. Факторизация позволила провести разделение труда между участниками деятельности: завуч составляет расписание, а учащиеся записывают его себе в дневники. Аналогичным образом, факторизация выписки рецептов позволила провести разделение труда между медиком, ставящим диагноз и выписывающим рецепт, и аптекарем, обеспечивающим эквивалентность выписанных лекарств. Апофеозом факторизации является конвейер, реализующий максимальное разделение труда за счет стандартизации деталей.
Но и этим выгоды факторизации не ограничены. Факторизация позволила обеспечить модульность современной техники, что дает ей небывалую гибкость функций. Вы можете сохранить старую сим-карту и купить к ней совершенно новый телефон, или в свой старый компьютер вставить новую видеопамять. Все это - гибкость, модульность, в основе которой лежит факторизация.
Литература
- А. И. Кострикин , Введение в алгебру. М .: Наука, 1977, 47-51.
- А. И. Мальцев , Алгебраические системы, М .: Наука, 1970, 23-30.
- В. В. Иванов , Математический анализ. НГУ, 2009.
См. также
- Отношение толерантности - ослабленная форма эквивалентности.
- Эквиваленция - логическая операция.
Wikimedia Foundation . 2010 .
- Госпитальная пневмония
- Mitel
Смотреть что такое "Отношение эквивалентности" в других словарях:
отношение эквивалентности - — Тематики электросвязь, основные понятия EN equivalence relation … Справочник технического переводчика
Отношение типа равенства - отношение эквивалентности, понятие логики и математики, выражающее факт наличия одних и тех же признаков (свойств) у различных объектов. Относительно таких общих признаков эти различные объекты неразличимы (тождественны, равны,… …
Отношение толерантности - У этого термина существуют и другие значения, см. Толерантность. Отношением толерантности (или просто толерантностью) на множестве называется бинарное отношение, удовлетворяющее свойствам рефлексивности и симметричности, но не обязательно… … Википедия
Отношение (математика) - У этого термина существуют и другие значения, см. Отношение. Отношение математическая структура, которая формально определяет свойства различных объектов и их взаимосвязи. Отношения обычно классифицируются по количеству связываемых объектов … Википедия
ОТНОШЕНИЕ - в логике то, что в отличие от свойства характеризует не отдельный предмет, а пару, тройку и т.д. предметов. Традиционная логика не рассматривала О.; в современной логике О. пропозициональная функция от двух или большего числа переменных. Бинарным … Философская энциклопедия
Отношение предпочтения - в теории потребления это формальное описание способности потребителя сравнивать (упорядочивать по желательности) разные наборы товаров (потребительские наборы). Чтобы описать отношение предпочтения, не обязательно измерять желательность… … Википедия
Отношение (философ.) - Отношение, философская категория, выражающая характер расположения элементов определённой системы и их взаимозависимости; эмоционально волевая установка личности на что либо, т. е. выражение её позиции; мысленное сопоставление различных объектов… … Большая советская энциклопедия
отношение - ОТНОШЕНИЕ множество упорядоченных п ок индивидов (где п > 1), т.е. двоек, троек и т.д. Число п называется «местностью», или «арностью», О. и, соответственно, говорят о n местном (п арном) О. Так, например, двуместное О. называют… … Энциклопедия эпистемологии и философии науки
Отношение - I Отношение философская категория, выражающая характер расположения элементов определённой системы и их взаимозависимости; эмоционально волевая установка личности на что либо, т. е. выражение её позиции; мысленное сопоставление различных… … Большая советская энциклопедия
Класс эквивалентности - Отношение эквивалентности () на множестве X это бинарное отношение, для которого выполнены следующие условия: Рефлексивность: для любого a в X, Симметричность: если, то, Транзитивность: если … Википедия
Книги
- Принятие финансовых решений в условиях сравнительной неопределенности: Монография , Баюк О.А.. В монографии разработана и теоретически обоснована новая логическая стратегия принятия решений при выборе между несравнимыми объектами, устанавливающая особое отношение предпочтения и…
Лекция 22. Отношения эквивалентности и порядка на множестве
1. Отношение эквивалентности. Связь отношения эквивалентности с разбиением множества на классы.
2. Отношение порядка. Строгое и нестрогое отношения порядка, отношение линейного порядка. Упорядоченность множеств.
3. Основные выводы
Рассмотрим на множестве дробей X = {1/2, 1/3, 1/4, 2/4, 2/6, 3/6} отношение равенства. Это отношение:
Рефлексивно, так как всякая дробь равна сама себе;
Симметрично, так как из того, что дробь m /n равна дроби p /q , следует, что дробь p /q равна дроби m /n ;
Транзитивно, так как из того, что дробь m /n равна дроби p /q и дробь p /q равна дроби r /s , следует, что дробь m /n равна дроби r /s .
Про отношение равенства дробей говорят, что оно является отношением эквивалентности .
Определение. Отношение R на множестве X называется отношением эквивалентности, если оно одновременно обладает свойствами рефлексивности, симметричности и транзитивности.
Примерами отношений эквивалентности могут служить отношения равенства геометрических фигур, отношение параллельности прямых (при условии, что совпадающие прямые считаются параллельными).
Почему в математике выделили этот вид отношений? Рассмотрим отношение равенства дробей, заданное на множестве X = {1/2, 1/3, 1/4, 2/4, 2/6, 3/6} (Рис.106). Видим, что множество разбилось на три подмножества: {1/2, 2/4, 3/6}, {1/3, 2/6}, {1/4}. Эти подмножества не пересекаются, а их объединение совпадает с множеством Х, т.е. имеем разбиение множества X на классы. Это не случайно.
Вообще, если на множестве X задано отношение эквивалентности, то оно порождает разбиение этого множества на попарно непересекающиеся подмножества (классы эквивалентности).
Так, мы установили, что отношению равенства на множестве дробей {1/2, 1/3, 1/4, 2/4, 2/6, 3/6} соответствует разбиение этого множества на классы эквивалентности, каждый из которых состоит из равных между собой дробей.
Верно и обратное утверждение: если какое-либо отношение, заданное на множестве X, порождает разбиение этого множества на классы, то оно является отношением эквивалентности.
Рассмотрим, например, на множестве X = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} отношение «иметь один и тот же остаток при делении на 3». Оно порождает разбиение множества X на классы: в один попадут все числа, при делении которых на 3 получается в остатке 0 (это числа 3, 6, 9), во второй - числа, при делении которых на 3 в остатке получается 1 (это числа 1, 4, 7, 10), и в третий - все числа, при делении которых на 3 в остатке получается 2 (это числа 2, 5, 8). Действительно, полученные подмножества не пересекаются и их объединение совпадает с множеством X. Следовательно, отношение «иметь один и тот же остаток при делении на 3», заданное на множестве X, является отношением эквивалентности. Заметим, что утверждение о взаимосвязи отношения эквивалентности и разбиения множества на классы нуждается в доказательстве. Мы его опускаем. Скажем только, что если отношение эквивалентности имеет название, то соответствующее название дается и классам. Например, если на множестве отрезков задается отношение равенства (а оно является отношением эквивалентности), то множество отрезков разбивается на классы равных отрезков (см. рис. 99). Отношению подобия соответствует разбиение множества треугольников на классы подобных треугольников.
Итак, имея отношение эквивалентности на некотором множестве, мы можем разбить это множество на классы. Но можно поступить и наоборот: сначала разбить множество на классы, а затем определить отношение эквивалентности, считая, что два элемента эквивалентны тогда и только тогда, когда они принадлежат одному классу рассматриваемого разбиения.
Принцип разбиения множества на классы при помощи некоторого отношения эквивалентности является важным принципом математики. Почему?
Во-первых , эквивалентный - это значит равносильный, взаимозаменяемый. Поэтому элементы одного класса эквивалентности взаимозаменяемы. Так, дроби, оказавшиеся в одном классе эквивалентности {1/2, 2/4, 3/6} неразличимы с точки зрения отношения равенства, и дробь 3/6 может быть заменена другой, например 1/2. И эта замена не изменит результата вычислений.
Во-вторых , поскольку в классе эквивалентности оказываются элементы, неразличимые с точки зрения некоторого отношения, то считают, что класс эквивалентности определяется любым своим представителем, т.е. произвольным элементом этого класса. Так, любой класс равных дробей можно задать, указав любую дробь, принадлежащую этому классу. Определение класса эквивалентности по одному представителю позволяет вместо всех элементов множества изучать совокупность отдельных представителей из классов эквивалентности. Например, отношение эквивалентности «иметь одинаковое число вершин», заданное на множестве многоугольников, порождает разбиение этого множества на классы треугольников, четырехугольников, пятиугольников и т.д. Свойства, присущие некоторому классу, рассматриваются на одном его представителе.
В-третьих , разбиение множества на классы с помощью отношения эквивалентности используется для введения новых понятий. Например, понятие «пучок прямых» можно определить как то общее, что имеют параллельные между собой прямые.
Вообще любое понятие, которым оперирует человек, представляет собой некоторый класс эквивалентности. «Стол», «дом», «книга» - все эти понятия являются обобщенными представлениями о множестве конкретных предметов, имеющих одинаковое назначение.
Другим важным видом отношений являются отношения порядка.
Определение. Отношение R на множестве X называется отношением порядка, если оно одновременно обладает свойствами антисимметричности и транзитивности .
Примерами отношений порядка могут служить: отношение «меньше» на множестве натуральных чисел; отношение «короче» на множестве отрезков, поскольку они антисимметричны и транзитивны.
Если отношение порядка обладает еще свойством связанности, то говорят, что оно является отношением линейного порядка.
Например, отношение «меньше» на множестве натуральных чисел является отношением линейного порядка, так как обладает свойствами антисимметричности, транзитивности и связанности.
Определение. Множество X называется упорядоченным, если на нем задано отношение порядка.
Так, множество N натуральных чисел можно упорядочить, если задать на нем отношение «меньше».
Если отношение порядка, заданное на множестве X, обладает свойством связанности, то говорят, что оно линейно упорядочивает множество X.
Например, множество натуральных чисел можно упорядочить и с помощью отношения «меньше», и с помощью отношения «кратно» - оба они являются отношениями порядка. Но отношение «меньше», в отличие от отношения «кратно», обладает еще и свойством связанности. Значит, отношение «меньше» упорядочивает множество натуральных чисел линейно.
Не следует думать, что все отношения делятся на отношения эквивалентности и отношения порядка. Существует огромное число отношений, не являющихся ни отношениями эквивалентности, ни отношениями порядка.
Во многих вычислительных задачах берутся большие множества и разбиваются таким образом, чтобы все интересующие нас ситуации можно было исследовать на нескольких правильно выбранных примерах.
Определение 1: Пусть A ¹ Æ и {A i },i= совокупность подмножеств таких, что A= . Тогда совокупность этих подмножеств называется покрытием множества A.
Например, {A, B}- покрытие AÈB; {A, AÈB, B, C}-покрытие AÈBÈC.
Замечание: В общем случае покрытие может быть и бесконечным. однако с точки зрения изучения конкретных свойств такая ситуация не вызывает энтузиазма.
Определение 2: Разбиением непустого множества А называется такое его покрытие , что если i¹ j, то A i ÇA j =Æ.
Например, {A, A’} – разбиение U .
{AÇB, AÇB’, A’ÇB, A’ÇB’} – разбиение U ,
{A\B, AÇB, B\A} – разбиение AÈB.
Организовать разбиение непустого множества можно при помощи отношений, которые ведут себя подобно отношениям равенства на множестве чисел или множеств.
Определение 3: Бинарное отношение на множестве называется отношением эквивалентности , если оно рефлексивно, симметрично и транзитивно.
Примеры :
1. На множестве всех треугольников: {(x, y)| x и y имеют одинаковую площадь}
2. На множестве всех программ: {(a, b)| a, b вычисляют одну и ту же функцию на конкретной машине}
Определение 4: Пусть R – отношение эквивалентности на множестве А и xÎA. Классом эквивалентности порожденным элементом х называется множество {y| xR y}=[x] R .
Определение 5: Любой элемент класса эквивалентности называется представителем этого класса. Полной системой представителей называется множество представителей, по одному из каждого класса.
Пример 3 :
N – натуральные числа, s – фиксированный элемент. На Z определено отношение: r s = {(x, y)| x-y=ns, nÎZ }. Отношение сравнения по модулю s (запись: xºy(mod s)).
Нетрудно проверить, что отношение сравнения по модулю s, есть отношение эквивалентности на множестве Z.
Пусть, например, s=10. Тогда:
= {11,21,-9,10 976 631,.... }
= {66,226,-24,... }
На самом деле есть всего 10 классов эквивалентности по этому отношению, а числа 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 образуют полную систему представителей . Классы эквивалентности по этому отношению эквивалентности называют классами вычетов по модулю s.
Определение 6: Фактор-множеством множества А по отношению эквивалентности R называется множество всех классов эквивалентности по этому отношению и обозначается A/R.
Множество классов вычетов по модулю s обозначают Z s .
Имеет место
Теорема (о разбиении): Пусть R - отношение эквивалентности на непустом множестве А. Тогда фактор-множество A/R является разбиением множества А.
Доказательство:
"xÎA(xÎ[x] R). Надо доказать, что каждый элемент множества А принадлежит в точности одному классу. То есть, докажем, что если классы имеют хотя бы один общий элемент, то они совпадают. Пусть cÎ[a] и cÎ[b]. Пусть xÎ[a], но тогда x R a, a R c, c R b Þ x R b(транзитивность R). Значит, [a] Ì [b]. (где рефлексивность? а она есть!) Аналогично [b] Ì [a].
Что и требовалось доказать.
Имеет место и обратное утверждение. Пусть S- разбиение множества А и R s – бинарное отношение на A, такое что: R={(x,y)ïx и y принадлежат одному элементу разбиения }, тогда R , будем называть– отношением, определяемым разбиением S.
Теорема (обратная): Отношение R на А, определяемое разбиением S, является отношением эквивалентности на А, причем A/R s =S.(самостоятельно)
Упражнения:
1. Пусть А- конечное множество. Какие отношения эквивалентности дают наибольшее и наименьшее число классов эквивалентности.
2. Если {A 1 , A 2 , ..., A n }- разбиение А и А конечно, то .
Отношение порядка.
Из понятия равенства (например, чисел) возникает математическое понятие эквивалентности. А из понятия неравенства возникает другой тип отношений, которые называются отношениями порядка.
Определение 1: Частичным порядком на множестве А называется бинарное отношение, которое рефлексивно, антисимметрично и транзитивно.
Частичный порядок - это обобщение отношения £ на R. Можно ввести понятие строгого порядка , соответствующего отношению < на R. Отношение строгого порядка - только транзитивно(оно еще и антирефлексивно).
Если задан £, то можно определить <: a
Множество, на котором задано отношение порядка, будем обозначать
(X, £) (или (X, <), если порядок строгий).
Определение 2: Множество, на котором задано отношение порядка, называется частично упорядоченным.
Пример: A - множество. (P (A),Í ), легко проверить, что отношение Í является отношением порядка на P (A).
Определение 3: Отношение порядка R на А называется полным (линейным) порядком , если " x, yÎA (xR y Ú yR x). Множество (A, R) называется линейно упорядоченным.
Примеры :
1. отношение £ на R является отношением полного порядка. Таким образом (R, £) - линейно упорядочено.
2. а вот (P (A),Í ) не является линейно упорядоченным
3. x£y Û y x на множестве N не является полным порядком
Определение 4: пусть (A, £) – частично упорядоченное множество. Элемент аÎА называетсянаименьшим /наибольшим/ в А, если " xÎA (a£ x) /x £ a /. Элемент bÎА называется минимальным /максимальным/ если " xÎA (x£ a Þ x=a) /a £ x Þ a=x /.
Задача: Доказать, что для линейно упорядоченного множества понятия наибольшего (наименьшего) и максимального (минимального) элементов совпадают. Привести пример частично упорядоченного множества, где они не совпадают.
Композиция отношений
Пусть заданы множества A, B и C и отношения S между A и B (то есть SÌA´B) и R между B и C (RÌB´C). Определим новое отношение между A и C следующим образом:
Определение 1: Множество всех пар (x, y), таких, что существует zÎB такое, что (x, z)Î S и (z, y)Î R называется композицией отношений S и R . Обозначается: R o S . Таким образом, R o S Ì A ´ C .
R oS = {(x, y)| $zÎB((x,z)ÎSÙ(z,y)ÎR)} или x R o Sy Û $zÎB(xSzÙzRy).
Пример 1 : Пусть A={1, 2, 3}, B={1, 2, 3, 4, 5, 6}, C={3, 6, 9, 12}, s ={(1,2), (2,4), (3,6)}, r={(1,3), (2,6), (3,9), (4,12)}. Тогда r o s={(1,6), (2,12)}.
Проиллюстрируем ситуацию на картинке:
Пример 2 : Пусть s и r - отношения на N такие, что
S = {(x,x+1)ïxÎN } и r = {(x 2 ,x)ïxÎN }. Тогда D r = {x 2 ïxÎN }={1,4,9,16,25,...}, а D s = N.
D r o s ={xïxÎN Ù x+1=y 2 }={3,8,15,24,...}.
В случае, когда отношение задано на множестве, оно может быть скомбинировано с самим собой:
sos = s 2 = {(x,x+2)½xÎN } и ror = r 2 = {(x 4 ,x)½xÎN }.
Используя это обозначение, можно определить энную степень отношения:
, где nÎN
, n>1.
Например, для отношений из примера 2 имеем:
, 
Хотелось бы дополнить аналогию с умножением. Для этого введем следующее естественное определение:
Определение 2: Бинарные отношения называются равными , если они равны как подмножества, то есть R=S, если"x,y((x,y)ÎRÛ(x,y)ÎS).
Понятно, что отношения должны быть определены на одних и тех же множествах.
Теорема (свойства композиции отношений): Для любых бинарных отношений R, S, T имеют место равенства:
1. (RoS)oT = Ro(SoT)
2. (RoS) -1 = S -1 o R -1
Доказательство:
1) Для любых x и y имеем:
x(RoS)oTy º $z(xTzÙ(zRoSy)) º $z$t(xTzÙ(zStÙtRy)) º $z$t((xTzÙzSt)ÙtRy) º $t(($z(xTzÙzSt))ÙtRy) º $t((xSoTt)ÙtRy) º xRo(SoT)y.
2) x(RoS) -1 y º yRoSx º $z(ySzÙzRx) º $z(xR -1 zÙzS -1 y) º xS -1 oR -1 y.
Что и требовалось доказать.
Замечание: если R - отношение на множестве A, то ясно, что I A oR=RoI A =R. То есть I A ведет себя как единица при умножении чисел. Однако полной аналогии провести нельзя. Поскольку, например, коммутативность, в общем случае места не имеет, так как RoS может быть определено, а SoR нет. Также как и не всегда имеет смысл равенство R -1 oR=RoR -1 = I A .
Замыкание отношений
Понятие замыкания является фундаментальным математическим понятием и используется в большинстве разделов математики. Проиллюстрируем это понятие на общем примере: возьмем объект x 0 и процесс P, который, будучи примененный последовательно, порождает некоторое множество и, значит, определяет последовательность x 1 , x 2 , ..., x n , ... так, что x 1 ÎP(x 0), x 2 ÎP(x 1),..., x n ÎP(x n -1),... 
Определение 1: множество, содержащее все элементы всех последовательностей, которые могут быть получены при помощи процесса P и начинающиеся с x 0 , называется замыканием процесса P относительно x 0 .
Ясно, что результат будет заключаться в нахождении Р n (x 0) при некотором n. Это n мы заранее не знаем, оно зависит от самого процесса. Более того, если мы возьмем элемент y из этого замыкания и будем применять к нему процесс р, то не получим ничего нового. То есть множество таким путем расширено быть не может - оно замкнуто!
Пример : Возьмем квадрат S, обозначенный ABCD и рассмотрим процесс r, заключающийся в повороте квадрата по часовой стрелке на 90°:
| |
| |
| |
| |
| |
Пусть отношение A задано на некотором множестве. Тогда:
Определение 2: Транзитивным замыканием отношения A на данном множестве называется отношение A + :
Таким образом, из не транзитивного отношения A на некотором множестве можно построить транзитивное A + .
Примеры:
1. r - отношение на N
: r={(x, y)| y=x+1}, тогда r + ={(x, y)| x 2. s на Q
: s={(x, y)| x 3. t наQ
: t={(x, y)| x×y=1}, тогда r + ={(x, x)| x¹0} 4. Пусть L - множество станций лондонского метро; L={a, b, c} последовательные станции. N={(x, y)| y следует за x}.Значит (a, b), (b, c) ÎN; кроме того (a, a), (b, b), (c, c), (a, c) Î N 2 . Значит, N + =L´L Вообще говоря, транзитивное замыкание не является рефлексивным (пример 2). Пусть A - отношение на X. Положим A 0 =I X . Определение 3:
Рефлексивным замыканием А*
отношения A называют отношение Примеры:
1. r*={(x, y)| x£y} Пусть %%R%% — отношение эквивалентности
на множестве %%M%% и %%a%% — некоторый элемент из %%M%%. Рассмотрим множество всех элементов из %%M%%, находящихся в отношении %%R%% к элементу %%a%%. Классом эквивалентности
%%M_a%% называется множество всех элементов %%M%%, находящихся в отношении %%R%% к элементу %%a%%, то есть множество $$
M_a = \{x \in M: x~R~a\}.
$$ Пусть %%M%% — множество всех жителей России и %%R%% — отношение эквивалентности «проживать в одном городе». Найти классы эквивалентных элементов %%M_a%% для %%a \in M%%. Класс элементов, эквивалентных элементу %%a%%, имеет вид:
$$
M_a = \{x \in M: x \text{ проживает в одном городе с человеком } a\}
$$ В зависимости от элемента %%a%% получаем несколько классов эквивалентности. Например, класс эквивалентности жителей Москвы или Санкт-Петербурга. Пусть %%R%% — отношение эквивалентности на множестве %%M%% и %%M_a, M_b, \dotsc, M_z, \dotsc%% — все классы эквивалентности для отношения %%R%%. Тогда эти классы имеют следующие свойства. Для любого элемента %%a \in M%% выполняется условие
$$
a \in M_a
$$ Действительно, по определению, класс %%M_a = \{x \in M: x~R~a\}%%. Тогда для элемента %%a%% должно выполняться условие %%a \in M_a \leftrightarrow a~R~a%%, которое выполняется в связи с тем, что отношение %%R%% рефлексивно по определению отношения эквивалентности. Следовательно, %%a \in M_a%%. Как следствие
этого свойства можно сказать, что всякий класс %%M_a%% является непустым множеством. Пусть %%M_a%% и %%M_b%% классы эквивалентности для отношения %%R%%. Классы %%M_a%% и %%M_b%% равны тогда и только тогда, когда элемент %%a%% находится в отношении %%R%% к элементу %%b%%.
$$
M_a = M_b \leftrightarrow a~R~b.
$$ Пусть %%M_a%% и %%M_b%% классы эквивалентности для отношения %%R%%. Тогда классы %%M_a%% и %%M_b%% не имеют общих элементов.
$$
M_a \neq M_b \rightarrow M_a \cap M_b = \varnothing
$$ Объединение всех классов эквивалентности множества %%M%% равно множеству %%M%%.
$$
\bigcup_{a\in M}{M_a} = M.
$$ Совокупностью подмножеств %%M_i%%, где %%i \in I%% (множеству индексов), множества %%M%% называется разбиением
множества %%M%% если выполняются следующие условия: Теорема.
Пусть %%R%% — отношение эквивалентности на множестве %%M%%. Тогда совокупность классов эквивалентности множества %%M%% образует его разбиение. Действительно, если в качестве подмножеств %%M_i%% взять классы эквивалентности %%M_a%%, то все три условия выполняются: Все условия определения разбиения выполнены. Следовательно классы эквивалентности есть разбиение множества %%M%%. Пусть дано множество %%M = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 0 \}%%, тогда разбиением этого множества могут быть следующие совокупности множеств: Но следующие совокупности не являются разбиением: Совокупность множеств %%C_i%% не является разбиением, т.к. оно не удовлетворяет условию 3 разбиения множеств: множества %%C_1%% и %%C_3%% имеют общий элемент %%3%%. Совокупность множеств %%D_i%% не является разбиением, т.к. оно не удовлетворяет условию 1 разбиения множеств: множество %%D_4%% пусто. Совокупность множеств %%E_i%% не является разбиением, т.к. оно не удовлетворяет условию 2 разбиения множеств: объединение множеств %%E_1, E_2%% и %%E_3%% не образует множество %%M%%. Аннотация:
Описывается много новых понятий, таких как отношение эквивалентности, отношение частичного порядка, изоморфные частичные множества. Доказываются несколько теорем по данной теме с подробными объяснениями, графиками и примерами. Задается большое количество примеров частичных порядков. Описываются несколько конструкций, позволяющих строить одни упорядоченные множества из других. Для лекции характерно множество задач для самостоятельного решения
Напомним, что бинарным отношением
на множестве называется
подмножество
; вместо Бинарное отношение
на множестве
называется отношением эквивалентности
,
если выполнены следующие свойства: Имеет место
следующее очевидное, но часто используемое
утверждение: Теорема 11
.
(а)
Если множество разбито в объединение
непересекающихся
подмножеств, то отношение
" лежать в одном подмножестве"
является отношением эквивалентности. (б)
Всякое отношение эквивалентности
получается описанным способом
из некоторого разбиения. Доказательство
.
Первое утверждение совсем очевидно; мы приведем доказательство
второго, чтобы было видно, где используются все пункты
определения эквивалентности. Итак, пусть - отношение
эквивалентности. Для каждого элемента рассмотрим его класс эквивалентности
- множество
всех , для которых верно . Докажем, что для двух различных , такие
множества
либо
не пересекаются, либо совпадают. Пусть они пересекаются, то есть
имеют общий элемент . Тогда и , откуда ( симметричность
) и
( транзитивность
), а также ( симметричность
). Поэтому для любого
из следует ( транзитивность
) и
наоборот. Осталось заметить, что в силу рефлексивности каждый элемент
принадлежит задаваемому им классу, то есть действительно
все множество разбито на непересекающиеся классы. 78. Покажите, что требования симметричности и транзитивности можно
заменить одним:
(при сохранении требования рефлексивности). 79. Сколько различных отношений эквивалентности существует на множестве 80. На множестве задано два отношения эквивалентности,
обозначаемые и , имеющие и классов
эквивалентности соответственно.
Будет ли их пересечение
отношением эквивалентности? Сколько у него может быть классов?
Что можно сказать про объединение отношений
? 81. (Теорема Рамсея)
Множество всех - элементных подмножеств
бесконечного множества
разбито на классов
(, -
натуральные числа). Докажите, что найдется бесконечное множество
, все - элементные подмножества
которого
принадлежат одному классу. (При это очевидно: если бесконечное множество
разбито
на конечное число классов
, то один из классов бесконечен. При
и утверждение можно сформулировать так:
из бесконечного множества
людей можно выбрать либо
бесконечно много попарно знакомых, либо бесконечно много
попарно незнакомых. Конечный вариант этого утверждения - о том,
что среди любых шести людей есть либо три попарно знакомых,
либо три попарно незнакомых, - известная задача для школьников.) Множество классов эквивалентности называют фактор -
множеством
множества
по отношению эквивалентности .
(Если отношение
согласовано с дополнительными структурами
на , получаются фактор - группы, фактор - кольца и т.д) Отношения эквивалентности нам не раз еще встретятся, но сейчас
наша основная тема - отношения порядка. Бинарное отношение
на множестве называется отношением
частичного порядка
,
если выполнены такие свойства: (Следуя традиции, мы используем символ (а не букву) как знак
отношения порядка.) Множество с заданным на нем отношением частичного
порядка называют частично упорядоченным
. Говорят, что два элемента частично упорядоченного
множества
сравнимы
,
если или . Заметим,
что определение
частичного порядка не требует, чтобы любые два
элемента множества
были сравнимы. Добавив это требование, мы получим
определение
линейного порядка
(линейно упорядоченного
множества
). Приведем несколько примеров частичных порядков:
. То есть 
.
Классы эквивалентных элементов и их свойства
Пример
Свойства классов эквивалентности
Свойство 1
Свойство 2
Свойство 3
Свойство 4
Разбиение множества
Примеры
Отношения эквивалентности и порядка
часто пишут .
?
при всех . Этот порядок не
будет
линейным.
