Аннотация: Описывается много новых понятий, таких как отношение эквивалентности, отношение частичного порядка, изоморфные частичные множества. Доказываются несколько теорем по данной теме с подробными объяснениями, графиками и примерами. Задается большое количество примеров частичных порядков. Описываются несколько конструкций, позволяющих строить одни упорядоченные множества из других. Для лекции характерно множество задач для самостоятельного решения
Отношения эквивалентности и порядка
Напомним, что бинарным отношением на множестве называется подмножество ; вместо часто пишут .
Бинарное отношение на множестве называется отношением эквивалентности , если выполнены следующие свойства:
Имеет место следующее очевидное, но часто используемое утверждение:
Теорема 11 . (а) Если множество разбито в объединение непересекающихся подмножеств, то отношение " лежать в одном подмножестве" является отношением эквивалентности.
(б) Всякое отношение эквивалентности получается описанным способом из некоторого разбиения.
Доказательство . Первое утверждение совсем очевидно; мы приведем доказательство второго, чтобы было видно, где используются все пункты определения эквивалентности. Итак, пусть - отношение эквивалентности. Для каждого элемента рассмотрим его класс эквивалентности - множество всех , для которых верно .
Докажем, что для двух различных , такие множества либо не пересекаются, либо совпадают. Пусть они пересекаются, то есть имеют общий элемент . Тогда и , откуда ( симметричность ) и ( транзитивность ), а также ( симметричность ). Поэтому для любого из следует ( транзитивность ) и наоборот.
Осталось заметить, что в силу рефлексивности каждый элемент принадлежит задаваемому им классу, то есть действительно все множество разбито на непересекающиеся классы.
78. Покажите, что требования симметричности и транзитивности можно заменить одним: (при сохранении требования рефлексивности).
79. Сколько различных отношений эквивалентности существует на множестве ?
80. На множестве задано два отношения эквивалентности, обозначаемые и , имеющие и классов эквивалентности соответственно. Будет ли их пересечение отношением эквивалентности? Сколько у него может быть классов? Что можно сказать про объединение отношений ?
81. (Теорема Рамсея) Множество всех - элементных подмножеств бесконечного множества разбито на классов (, - натуральные числа). Докажите, что найдется бесконечное множество , все - элементные подмножества которого принадлежат одному классу.
(При это очевидно: если бесконечное множество разбито на конечное число классов , то один из классов бесконечен. При и утверждение можно сформулировать так: из бесконечного множества людей можно выбрать либо бесконечно много попарно знакомых, либо бесконечно много попарно незнакомых. Конечный вариант этого утверждения - о том, что среди любых шести людей есть либо три попарно знакомых, либо три попарно незнакомых, - известная задача для школьников.)
Множество классов эквивалентности называют фактор - множеством множества по отношению эквивалентности . (Если отношение согласовано с дополнительными структурами на , получаются фактор - группы, фактор - кольца и т.д)
Отношения эквивалентности нам не раз еще встретятся, но сейчас наша основная тема - отношения порядка.
Бинарное отношение на множестве называется отношением частичного порядка , если выполнены такие свойства:
(Следуя традиции, мы используем символ (а не букву) как знак отношения порядка.) Множество с заданным на нем отношением частичного порядка называют частично упорядоченным .
Говорят, что два элемента частично упорядоченного множества сравнимы , если или . Заметим, что определение частичного порядка не требует, чтобы любые два элемента множества были сравнимы. Добавив это требование, мы получим определение линейного порядка (линейно упорядоченного множества ).
Приведем несколько примеров частичных порядков:
- Числовые множества с обычным отношением порядка (здесь порядок будет линейным).
- На множестве всех пар действительных чисел можно ввести частичный порядок , считая, что , если и . Этот порядок уже не будет линейным: пары и не сравнимы.
- На множестве функций с действительными аргументами и значениями можно ввести частичный порядок , считая, что , если при всех . Этот порядок не будет линейным.
- На множестве целых положительных чисел можно определить порядок, считая, что , если делит . Этот порядок тоже не будет линейным.
- Отношение " любой простой делитель числа является также и делителем числа " не будет отношением порядка на множестве целых положительных чисел (оно рефлексивно и транзитивно, но не антисимметрично).
- Пусть - произвольное множество. Тогда на множестве всех подмножеств множества отношение включения будет частичным порядком.
- На буквах русского алфавита традиция определяет некоторый порядок (). Этот порядок линеен - про любые две буквы можно сказать, какая из них раньше (при необходимости заглянув в словарь).
- На словах русского алфавита определен лексикографический порядок (как в словаре). Формально определить его можно так: если слово является началом слова , то (например, ). Если ни одно из слов не является началом другого, посмотрим на первую по порядку букву, в которой слова отличаются: то слово, где эта буква меньше в алфавитном порядке, и будет меньше. Этот порядок также линеен (иначе что бы делали составители словарей?).
- Отношение равенства () также является отношением частичного порядка , для которого никакие два различных элемента не сравнимы.
- Приведем теперь бытовой пример. Пусть есть множество картонных коробок. Введем на нем порядок, считая, что , если коробка целиком помещается внутрь коробки (или если и - одна и та же коробка). В зависимости от набора коробок этот порядок может быть или не быть линейным.
Отношение эквивалентности – это отношение, обладающее свойствами рефлексивности, симметричности и транзитивности. Обозначается знаком ~, записьа ~ в означает, что а эквивалентно в .
В соответствии с определением для отношения эквивалентности выполняются свойства:
Примеры отношений эквивалентности – равенство, подобие треугольников .
Используя отношение эквивалентности можно проводить разбиение множества на классы эквивалентности.
Класс эквивалентности , порожденный элементом – множество всех элементов из , вступающих с в отношение эквивалентности. Класс эквивалентности определяется так:
,
для
подбираются элементы
,
находящиеся в соответствии с элементомх
.
Отношение
эквивалентности имеет большое практическое
применение, позволяющее разбивать
множества на классы эквивалентности.
Класс эквивалентности можно получить,
если для выбранного элемента х
из множества Х
можно подобрать элементы
,
находящиеся сх
в одном классе эквивалентности
Фактор-множества множества по отношению эквивалентности φ – множество всех различных классов эквивалентности, обозначаемое А / φ .
Индекс разбиения , порожденный отношением φ – это мощность фактор-множества А / φ .
Пример 2 .11.
а)
Отношение
равенства
на любом множестве является отношением
эквивалентности.
Равенство
– это минимальное отношение эквивалентности
в том смысле, что при удаление любой
пары из
(то
есть любой единицы на диагонали матрицы
)
оно перестает быть рефлексивным и,
следовательно, уже не является
эквивалентностью.
б)
Утверждения
вида
или
,
состоящие из формул, соединенных знаком
равенства, задают бинарное отношение
на множестве формул, описывающих
суперпозиции элементарных функций. Это
отношение обычно называется отношением
равносильности и определяется следующим
образом: формулы равносильны, если они
задают одну и ту же функцию. Равносильность,
хотя и обозначается знаком =, отличается
от отношения равенства
,
так как оно может выполняться для
различных формул. Отношение
для формул – это совпадение формул по
написанию. Оно называетсяграфическим
равенством
.
в) Рассмотрим множество треугольников на плоскости, считая, что треугольник задан, если заданы координаты его вершин. Два треугольника называются конгруэнтными (равными ) , если они при наложении совпадают, то есть могут быть переведены друг в друга путем некоторого перемещения . Конгруэнтность является отношением эквивалентности на множестве треугольников.
г)
Отношение
«иметь
один и тот же остаток от деления на
9»
является эквивалентностью на
.
Это отношение выполняетсядля
пар (12, 21), (17, 36) и не выполняется для пар
(11, 13), (19, 29).
Пусть
на множествезадано отношение эквивалентности
.
Осуществим следующее построение. Выберем
элемент
и образуем класс (подмножество),
состоящий из;
затем выберем элемент
и образуем класс,
состоящий изи всех элементов, эквивалентных,
и т.д. Получится система классов
(возможно, бесконечная) такая, что любой
элемент из
входит хотя бы в один класс, то есть
.
Эта система классов обладает следующими
свойствами:
она образует разбиение , то есть классы попарно не пересекаются ;
любые два элемента из одного класса эквивалентны ;
любые два элемента из разных классов неэквивалентны .
Все
эти свойства вытекают из рефлексивности,
симметричности и транзитивности
.
Действительно, если бы классы, например
и,
пересекались, то они имели бы общий
элемент,
эквивалентныйи,
но тогда из-за транзитивности
было бы
,
что противоречит построению.
Аналогично доказываются другие два
свойства.
Построенное разбиение, то есть система классов, называется системой классов эквивалентности по отношению . Мощность этой системы называется индексом разбиения. С другой стороны, любое разбиение на классы определяет некоторое отношение эквивалентности, а именно, отношение «входить в один и тот же класс данного разбиения ».
Пример. 2.12.
а)
Все
классы эквивалентности по отношению
равенства
состоят из одного элемента.
б) Формулы, описывающие одну и ту же элементарную функцию, находятся в одном классе эквивалентности по отношению равносильности. В этом примере счётны само множество формул, множество классов эквивалентности (то есть индекс разбиения) и каждый класс эквивалентности.
в)
Разбиение
по отношению «иметь
общий остаток от деления на
7» имеет конечный индекс 7 и состоит из
7 счетных классов: 0, 7, 14, …; 2, 9, 16, …; …;
6, 13, 20, …
I. Разбиение на классы. Отношение эквивалентности
Определение 2.1. Назовем взаимозаменяемыми те и только те объекты некоторого данного множества М, которые обладают одним и тем же набором формальных признаков, существенных в данной ситуации.
Обозначим через М х -множество всех объектов, взаимозаменяемых с объектом х. Очевидно, что х М х и объединение всех М х (при всевозможных х из М) совпадает совсем множеством М:
Предположим, что. Это значит, что существует некоторый элемент z, такой, что он одновременно принадлежит и и. Значит x взаимозаменяем с z и z взаимозаменяем с у. Следовательно, х взаимозаменяем с у, а значит и с любым элементом из. Таким образом. Аналогично показывается и обратное включение. Таким образом, встречающиеся в объединении (2.1) множества либо не пресекаются, либо целиком совпадают.
Определение 2.2. Систему непустых подмножеств {M 1 , M 2 ,….} множества М мы будем называть разбиением этого множества, если
Сам множества при этом называются классами разбиения.
Определение 2.3. Отношение с на множестве М называется эквивалентностью (или отношением эквивалентности), если существует такое разбиение {M 1 , M 2 ,….} множества М такое, что (х, у) выполняется тогда и только тогда, когда х и у принадлежат к некоторому общему классу M i данного разбиения.
Пусть {M 1 , M 2 ,….} разбиение множества М. Определим, исходя из этого разбиения, отношение с на М: (х, у),если х и у принадлежат к некоторому общему классу M i данного разбиения. Очевидно, что отношение с является эквивалентностью. Назовем с отношением эквивалентности, соответствующим данному разбиению.
Определение 2.4. Если в каждом подмножестве M i выбрать содержащийся в нем элемент х i , то этот элемент будем называть эталоном для всякого элемента у, входящего в тоже множество M i . По определению, положим выполненным отношение с* «быть эталоном» (х i , у)
Легко видеть, что эквивалентность с, соответствующая данному разбиению, может быть определена и так: (z, у) если z и у имеют общий эталон (х i , z) и (х i , у).
Пример 2.1: Рассмотрим в качестве М множество целых неотрицательных чисел и возьмем его разбиение на множество М 0 четных чисел и множество М 1 - нечетных. Соответствующее отношение эквивалентности на множестве целых чисел обозначается так:
и читается: n сравнимо с m по модулю 2. В качестве эталонов естественно выбрать 0 - для четных чисел и 1 - для нечетных. Аналогично, разбивая то же множество М на k подмножеств M 0 , M 1 ,… M k-1 , где M j состоит из всех чисел, дающих при делении на k в остатке j, мы придем к отношению эквивалентности:
которое выполняется, если n и m имеют одинаковые остатки при делении на k.
В качестве эталона в каждом M j естественно выбрать соответствующий остаток j.
II. Фактор-множество
Пусть - отношение эквивалентности. Тогда по теореме, существует разбиение {M 1 , M 2 ,….} множества М на классы эквивалентных друг другу элементов - так называемые классы эквивалентности.
Определение 2.5. Множество классов эквивалентности по отношению обозначают М/ и читают фактор-множество множества М по отношению.
Пусть ц: M > S - сюрьективное отображение множества М на некоторое множество S.
Для всякого ц: M > S - сюрьективного отображения существует такое отношение эквивалентности на множестве М, что М/ и S могут быть поставлены во взаимно однозначное соответствие.
III. Свойства эквивалентности
Определение 2.6. Отношение с на множестве М называется эквивалентностью (отношением эквивалентности), если оно рефлексивно, симметрично и транзитивно.
Теорема 2.1: Если отношение с на множестве М рефлексивно, симметрично и транзитивно, существует такое разбиение {M 1 , M 2 ,….} множества М такое, что (х, у) выполняется тогда и только тогда, когда х и у принадлежат к некоторому общему классу M i данного разбиения.
Обратно: Если задано разбиение {M 1 , M 2 ,….} и бинарное отношение с задано как «принадлежать к общему классу разбиения», то с рефлексивно, симметрично и транзитивно.
Доказательство:
Рассмотрим рефлексивное, симметричное и транзитивное отношение с на М. Пусть для любого состоит из всех таких z, для которых (x, z) с
Лемма 2.1: Для любых x и y либо либо
Из леммы и рефлексивности отношения с следует, что множества вида образуют разбиение множества М. (Это разбиение естественно назвать разбиением, соответствующим исходному отношению). Пусть теперь (x, y) с. Это значит, что y. Но и х в силу (x, х) с. Следовательно, оба элемента входят в. Итак, если (x, y) с, то х и у входят в общий класс разбиения. Наоборот, пусть uи v. Покажем, что (u, v) с, Действительно, имеем (x, u) с и (x, v) с. Отсюда по симметричности (u, x) с. По транзитивности из (u, x) с и (x, v) с следует (u, v) с. Первая часть теоремы доказана.
Пусть дано разбиение {M 1 , M 2 ,….} множества М. Т.к. объединение всех классов разбиения совпадает с М, то любой хвходит в некоторый класс. Отсюда следует, что (x, х) с, т.е. с - рефлексивно. Если x и y входят в некоторый класс, то y и x входят в тот же класс. Это означает, что из (x, y) с вытекает (y, x) с, т.е. отношение симметрично. Пусть теперь выполнено (x, y) с и (y, z) с. Это означает, что x и y входят в некоторый класс, а y и z входят в некоторый класс. Классы имеют общий элемент у, а, следовательно, совпадают. Значит x и z входят в класс, т.е. выполняется (x, z) с и отношение транзитивно. Теорема доказана.
IV. Операции над эквивалентностями.
Определим здесь некоторые теоретико-множественные операции над эквивалентностями и приведем без доказательств их важные свойства.
Вспомним, что отношение - это пара (), где М - множество элементов, вступающих в отношение, а - множество пар, для которых отношение выполнено.
Определение 2.7. Пересечением отношений (с 1 , М) и (с 2 , М) назовем отношение, определенное пересечением соответствующих подмножеств. (x, y) с 1 с 2 тогда и только тогда, когда одновременно (x, y) с 1 и (x, y) с 2 .
Теорема 2.2: Пересечение с 1 с 2 эквивалентностей с 1 с 2 само является отношением эквивалентности.
Определение 2.8. Объединением отношений (с 1 , М) и (с 2 , М) назовем отношение, определенное объединением соответствующих подмножеств. (x, y) с 1 с 2 тогда и только тогда, когда (x, y) с 1 или (x, y) с 2 .
Теорема 2.3: Для того, чтобы объединение с 1 с 2 эквивалентностей с 1 с 2 само по себе было отношением эквивалентности необходимо и достаточно, чтобы
с 1 с 2 =с 1 с 2
Определение 2.9. Прямой суммой отношений (с 1 , М 1) и (с 2 , М 2) называется отношение). Прямая сумма обозначается (с 1 , М 1) (с 2 , М 2).
Таким образом, если (с 1 , М 1) (с 2 , М 2)= (), то M=.
Теорема 2.4: Если, а отношения - эквивалентности, то прямая сумма отношений (с 1 , М 1) (с 2 , М 2)= (), также является эквивалентностью.
V. Типы отношений
Введем еще несколько важных типов отношений. Примеры будут приведены в третьей главе.
Определение 2.10. Отношение с на множестве М называется толерантностью, если оно рефлексивно и симметрично.
Определение 2.11. Отношение с на множестве М называется отношением строгого порядка если оно антирефлексивно и транзитивно.
Определение 2.12. Отношение строгого порядка с называется совершенным строгим порядком, если для всякой пары элементов x и y из М верно либо (х, у), либо (у, х)
Определение 2.13. Отношение с на множестве М называется отношением нестрогого порядка если оно может быть представлено в виде:
где строгий порядок на М, а Е -диагональное отношение.
Классы эквивалентных элементов и их свойства
Пусть %%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%%. Тогда эти классы имеют следующие свойства.
Свойство 1
Для любого элемента %%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%% является непустым множеством.
Свойство 2
Пусть %%M_a%% и %%M_b%% классы эквивалентности для отношения %%R%%. Классы %%M_a%% и %%M_b%% равны тогда и только тогда, когда элемент %%a%% находится в отношении %%R%% к элементу %%b%%. $$ M_a = M_b \leftrightarrow a~R~b. $$
Свойство 3
Пусть %%M_a%% и %%M_b%% классы эквивалентности для отношения %%R%%. Тогда классы %%M_a%% и %%M_b%% не имеют общих элементов. $$ M_a \neq M_b \rightarrow M_a \cap M_b = \varnothing $$
Свойство 4
Объединение всех классов эквивалентности множества %%M%% равно множеству %%M%%. $$ \bigcup_{a\in M}{M_a} = M. $$
Разбиение множества
Совокупностью подмножеств %%M_i%%, где %%i \in I%% (множеству индексов), множества %%M%% называется разбиением множества %%M%% если выполняются следующие условия:
- Каждое из подмножеств %%M_i%% непусто.
- Объединение всех подмножеств %%M_i%% равно множеству %%M%%.
- Два различных подмножества %%M_i%% и %%M_j%%, где %%i \neq j%%, не имеют общих элементов.
Теорема. Пусть %%R%% — отношение эквивалентности на множестве %%M%%. Тогда совокупность классов эквивалентности множества %%M%% образует его разбиение.
Действительно, если в качестве подмножеств %%M_i%% взять классы эквивалентности %%M_a%%, то все три условия выполняются:
- Каждый класс эквивалентности является непустым множеством, согласно свойству 1 .
- Объединение всех классов эквивалентности есть множество %%M%%, согласно свойству 4 .
- Два различных класса эквивалентности не имеют общих элементов, согласно свойству 3 .
Все условия определения разбиения выполнены. Следовательно классы эквивалентности есть разбиение множества %%M%%.
Примеры
Пусть дано множество %%M = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 0 \}%%, тогда разбиением этого множества могут быть следующие совокупности множеств:
- %%A_1 = \{1, 2, 3\}, A_2 = \{4, 5, 6, 7\}, A_3 = \{8, 9, 0 \}%%.
- %%B_1 = \{0, 7, 2\}, B_2 = \{1, 3, 5 \}, B_3 = \{4, 6, 8, 9\}%%.
Но следующие совокупности не являются разбиением:
- %%C_1 = \{1, 2, 3\}, C_2 = \{4, 5, 6, 7\}, C_3 = \{8, 9, 0, 3\}%%.
- %%D_1 = \{0, 7, 2\}, D_2 = \{1, 3, 5 \}, D_3 = \{4, 6, 8, 9\}, D_4 = \varnothing%%.
- %%E_1 = \{0, 1, 2\}, E_2 = \{3, 4, 5\}, E_3 = \{6, 7, 8\}%%.
Совокупность множеств %%C_i%% не является разбиением, т.к. оно не удовлетворяет условию 3 разбиения множеств: множества %%C_1%% и %%C_3%% имеют общий элемент %%3%%.
Совокупность множеств %%D_i%% не является разбиением, т.к. оно не удовлетворяет условию 1 разбиения множеств: множество %%D_4%% пусто.
Совокупность множеств %%E_i%% не является разбиением, т.к. оно не удовлетворяет условию 2 разбиения множеств: объединение множеств %%E_1, E_2%% и %%E_3%% не образует множество %%M%%.