XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 11
Текст из файла (страница 11)
Таким образом, любое отношение эквивалентности однозначно определяет некоторое разбиение. Теперь пусть (В;);ет — некоторое разбиение множества А. Рассмотрим отношение р, такое, что х р у имеет место тогда и только тогда, когда х и у принадлежат одному и тому же элементу В; данного разбиения: х р у вт (Зт Е 1)(х Е Вт) Л (у Е В;). Очевидно, что введенное отношение рефлексивно и симметрично.
Если для любых х, у и х имеет место х р у и у р х, то х, у и я в силу определения отношения р принадлежат одному и тому же элементу В; разбиения. Следовательно, х р г и отношение р транэитивно. Таким образом, р — эквивалентность на А. 1ь Теорема 1.4 позволяет отождествлять отношения эквивалентности и разбиения: любая эквивалентность определяет единственное разбиение и наоборот. Множество всех классов эквиваяентности по данному отношению эквивалентности р на множестве А называют фантпор-мноэтсестпвом множества А по отношению р и обозначают А/р.
Пример 1.14. а. На множестве целых чисел У определим опэношение равенстпва по модулю х, где й Е г1. Положим" х =биэв ь) У, если и только если х — У делитсЯ на й. 'традиционное обоэиачеиие: ти = и (шест й). 2. МНОЖЕОТВА И ОТНОШЕНИЯ Легко проверяется, что это отношение эквивалентности. Действительно, рефлексивность следует из того, что для любого т Е Е т — т = 0 и делится на Й; симметричность — из того, что если т — и делится на Й, то и и — т делится на Й. Для доказательства транзитивности заметим, что если т — и делится на Й, и — р делится на Й, то и их сумма (т — и) + (и — р) = т — р делится на Й.
Другими словами, для любых целых т, п, р из т=(мьвь)п и ))=(пзовь)р следует т=(пить)р что дОказыВает транзитивность отношения =( в ьр Равенство чисел т и и по модулю Й означает, что при делении на Й зти числа дают одинаковые остатки. Действительно, для каждого х Е Е имеем х =т Й+г, где г — остаток от деления х на Й. Следовательно, х — г = т Й, т.е. х=(ь,ьвь) г. Таким образом, каждое число попадает в тот же класс эквивалентности по отношению =( вц, что и остаток от деления его на Й. Поскольку всего различных остатков может быть ровно Й:~, О, 1, ..., Й вЂ” 1, получаем ровно Й попарно различных классов эквивалентности по данному отношению: [0] —, „), [1] — <, ), ..., [Й вЂ” 1]=( „ь) > где класс [г]=(, ь) сОстОит иэ Всех целых чисел, дающих при делении на Й остаток г.
Отметим, что мы установили взаимно однозначное соответствие между фактор-множеством Е/ =(мьв ь) и множеством Еы состоящим из чисел О, 1, ..., Й-1. Второе множество дает нам как бы „наглядный образ" построенного фактор-множества.
Нельзя считать, что фактор- множество Е/=(в,ьвь) равно множеству (О, 1, ..., Й вЂ” Ц. Нет, укаэанное фактор-множество состоит из Й элементов, каждый из которых есть не число, а множество всех целых чисел, при делении на Й дающих фиксированный остаток. Но каждому такому классу эквивалентности однозначно сопоставляется це. лое число от 0 до Й вЂ” 1, и, наоборот, каждому целому числу от 0 до Й вЂ” 1 соответствует единственный класс эквивалентности по отношению =( в яр Заметим, что в математике часто используется прием сопоставления фактор-множеству такого 1.7. Отвонюние экаиэаеентноств находящегося с ним во взаимно однозначном соответствии множества, которое легко представить и описать. б.
На множестве Ж действительных чисел зададим отношение а=~юоб1) Ь, полагая, что числа о и Ь равны по модулю 1 тогда и только тогда, когда число а — Ь является целым. Из определения следует, что каждое число по модулю 1 равно своей дробной части'. Так как отношение =~ бц определено через равенство, то легко понять, что все свойства отношения эквивалентности для него выполюпотся. Каждый класс эквивалентности будет содержать числа с равными дробными частями. Это значит, что каждый класс эквивалентности по данному отношению однозначно определяет некоторое число из полуинтервала [О, 1) и, наоборот, каждому числу у Е [О, 1) однозначно сопоставляется класс эквивалентности, состоящий из всех действительных чисел, дробная часть которых равна у.
Таким образом, фактор- множество й/ =< об П и полуинтервал [О, 1) на числовой прямой находятся во взаимно однозначном соответствии. Этот полуинтервзл можно рассматривать как представление определенного вьппе фактор-множества. ф Установим теперь связь между понятиями эквивалентности и отображения. Заметим, что для любого отношения эквивалентности р на множестве А можно определить отображение Ур: А -+ А(р, положив ~р(х) = [х]р, т.е. сопоставив каждому х Е А содержащий его класс эквивалентности. Это огнобразсекие сюръектпиено, так как каждый элемент множества А принадлежит некоторому классу эквивалентности, т.е.
для каждого [х)р Е А[р справедливо [х)р — — ~р(х). Отображение ур, определенное таким образом, называют иамомпчесмоб сюръевииеб множества А. 'Под дробной частью (а> чиска а нонимаетск число вэ нолуевтерэака [О, 1), такое, что е = н+ (о> длк некоторого целого н. Поэтому дробной частью отрицательного чисеа — и, где а > О, будет число 1 — (а>. ьак, дробной частью -1,23 будет ве 0,23, а 0,77 = 1 — 0,23.
1. МНОЖЕСТВА И ОТНОШЕНИЯ Покажем, что любое отображение однозначно определяет некоторое отношение эквивалентности. Теорема 1.5. Пусть /: А -1  — произвольное отображение. Отношение ру на множестве А, для которого х ру у, если и только если /(х) = /(у), является отношением эквивалентности, причем существует биекция фактор-множества А/ру на множество /(А).
~ Рефлексивность, симметричность и транзитивность отношения ру следуют непосредственно из его определения, т.е. ров эквивалентность. Зададим отображение <р фактор-множества А/ру в множество /(А) следующим образом: р(]х]р ) =/(х). Из способа задания отношения р следует, что отображение определено корректно, т.е. каждому классу эквивалентности поставлен в соответствие единственный элемент р Е /(А). Докажем, что 1о — биекция, для чего убедимся в том, что зто инъекция и сюръекция одновременно. Пусть классы эквивалентности ]х]р и Цр не совпадают. В силу теоремы 1.4 зто означает, что они не пересекаются, т.е. х не эквивалентно р. Из определения отношения ру следует, что /(х) ф /(у). Таким образом, ~р — инъекция. Если элемент п Е /(А), то найдется такой элемент х Е А, что и = /(х) = у(]х]р ), т.е. у— сюръекция фактор-множества А/ру на множество /(А).
Итак, ~р — биекция. ° Следовательно, в силу доказанных теорем 1.4 и 1.5 существует связь между тремя понятиями — отображением множества, отношением эквивалентности на множестве и разбиением множества. Но неверно, что существует взаимно однозначное соответствие между отображениями и отношениями эквивалентности'. Два разных отображения могут определять одно и то же разбиение отображаемого множества, тем самым задавая на нем одно и то же отношение эквивалентности.
Так, 'Заметим, что теорема 1.5 этого и ие утверждает. 75 1.8. Упорлдочвтяые мвожества например, любое биективное отображение у: А ~ В задает на А одно и то же разбиение — тривиальное разбиение на однозлементные множества. 1.8..тпорядоченные множества. Теорема о неподвижной точке Множество вместе с заданным на нем отпношением порядка называют упорядоченным множеством.
Отношение порядка будем, как правило, обозначать < (или значками 4, С и т.п., похожими на <). При этом следует понимать, что даже на некотором множестве Я С К рассматриваться может любое отношение порядка, а не только естаестеенный числовой порядок. Множество М с заданным на нем отношением порядка < будем записывать как пару (М, <).
Записывая х < у, мы будем говорить, что элемент х не больше элемента у. Каждому отношению порядка < на множестве М можно сопоставить следующие отношения. 1. Отношение, которое будем обозначать <, получается из исходного отношения порядка < выбрасыванием всех элементов диагонали 1йьт, т.е. х < у для любых х, у Е М тогда и только тогда, когда х < у и х ~у. Записывая х < у, мы будем говорить, что элемент х строго меньше элемента у. Из определения следует, что отношение < есть иррефлексивное, аншисимметлричное и тпранзитаивное бинарное отношение на множестве М, т.е. оно является отпношением стпрогого порядка.
2. Двойсптвенный порядок. Это бинарное отношение на множестве М, называемое также и отпношением, двойстпвенным к ошношению порядка <, определяется как бинарное оптношение на мнохсеставе М, обратпное к отношению ~(. Его обозначают >. Тогда для любых х, у условие х > у Равносильно тому, что у < х. Можно без труда доказать, что отношение > тоже является отношением порядка. Записывая х > у, мы будем говорить, что элемент х не меньше элемента у. Отношение строгого порядка, ассоциированное 76 1. МНОЖЕСТВА И ОТНОШЕНИЯ с >, договоримся обозначать >, говоря при этом, что элемент х строго больше элемента у, если х > у и х ф у. 3. Отношение доминирования. Для двух элементов х и у, по определению, х <3 у тогда и только тогда, когда х строго меньше у и не существует такого элемента е, что х < е < у. Отношение ~ называют отношением доминировани,я (или просто доминированием), ассоциированным с отношением порядка <.
Если имеет место х 1 у, то говорят, что элемент у доминирует над элементом х. Из определения следует, что отношение доминирования иррефлексивно, антисимметрично, но не транзитивно. Оно может быть и пусто. Например, легко видеть, что пустым будет отношение доминирования, если исходный порядок является плотным бинарным отношением на соответствующем мнозеестве. Пример 1.1б.
а. Рассмотрим множество действительных чисел с естественным числовым порядком. Пусть а < с. Известно, что для любых а и с найдется такое Ь, что а < Ь < с, т.е. это отношение порядка на множестве действительных чисел является плотным. Поэтому отношение доминирования будет пустым. По той же причине будет пустым отношение доминирования, ассоциированное с естественным числовым порядком на множестве рациональных чисел.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
