Бурбаки - Книга 1. Теория множеств (947355), страница 29
Текст из файла (страница 29)
Показать, что отображение 0 — ь0 есть бнекцкя из((б( э( ) 13 П (Х ) — конечное семейство множеств. для каждой 3) пУсть ( д1<1с„— частн Н множества индексов (1, и) пусть Рн — — Ц Х! н !2н = П Х!. !ЕН !Ен — ож ство частей множества (1, и), имеющее Л злеменПусть и» вЂ” ми е тоз; показать, что и+ 1 00н Прн Р»< —, Н бй» Н Гй» э. Определение соотношении эквивалентности Пусть К)х, у ! — соотношение, х и у — различные буквы. Мы говорим, что соотношение К является симметрическим или симметричным (по буквам х и у или относительно букв х и у), если К!х, у(=)1К(у, х~. Если дело обстоит так, то, заменяя х и у двумя буквами х', у', отличными друг от друга и от всех букв, встречающихся в К, а затем заменяя х' и у' соответственно буквами у и х.
нетрудно видеть, что К!у, х!=)1К(х, у~; следовательно К(х, у~ и К)у, х! эквивалентны. Пусть х — буква, не встречающаяся в К. Мы говорим, что соотношение К тракзитивко (по буквам х и у или относительно букв х и у), если (К(х, у1 и К)у, г1)~К(х, г!.
Примеры. Соотношение х=у симметрично и транзитивно. Соотношение Х1=У транзитивно, но не симметрично. Соотношение Х П У =8 симметрично, но не транзитивно. Если К!х, у! одновременно и симметрично, и транзитивно, то мы говорим, что К(х, у~ есть соотношение эквивалентности(по буквам х и у или относительно букв х и. у). В этом случае иногда применяется запись х= у(шоб.
К) как синоним с К)х, у(; эта запись читается так: „х эквивалентно у ио модулю К (или ио К или согласно К)". Если К вЂ” соотношение эквивалентностг. то К(х, у)=р =Р(К(х, х! и К!у, у)). ибо К!х, у! влечет К!у, х~, а (К!х, у1 и К(у, х!) влечет (К)х, х! н К!у, у!) в силу определений. Пусть К(х, у! — соотношение. Мы говорим, что созтношение К рефлексивно в Е (по буквам х и у), если соотношение К)х, х! эквивалентно х ~ Е. Если нет никакой неясности насчет Е, мы говорим просто, допуская вольность речи, что К рефлексивно. Соотношением экэизалекткости з Е называется соотношение эквивалентности, рефлексивное в Е. Если К(х, у1 есть соотношение эквивалентности в Е, то К!х, у1=;=ь((х, у)~Е Х Е); следовательно, К обладает графиком (по буквам х и у).
Обратно, предположим, что соотношение эквивалентности К)х, у! обладает графиком 01 заметим, что соотношение К!х, х! эквивалентно соотношению (Лу)К(х, у); в самом деле, первое влечет последнее (гл. 1, э 4, п'2, схема 35), а с другой стороны, так как К)х, у( влечет К(х, х(, то Ду)К(х, у! влечет (Зу)К!х, х~, а следовательно, и К)х, х(. Итак, мы видим, что К!х, х~ эквивалентно харт,О. а потому К есть соотношение эквивалентности в рг, Г, Эквивалентностью на множестве Е называется соответствие, у которого областью прибытия и областью отправления является Е и у которого график Р таков, что соотношение (х, у) ~ Р есть соотношение эквивалентности в Е, Примеры. 1) Соотношение х=у есть соотношение эквивалентности, не обладающее графиком, так как первая проекция этого графика была бы множеством всех объектов.
в $6. СООТНОШЕНИЯ ЭКВИВАЛЕНТНОСТИ 127 12! ГЛ. Н. ТЕОРИЯ МНОЖЕСТВ 2) Соотношение „х=у и х~Е" есть соотношение эквивалентности в Е, графиком которого служит диагональ в Е Х Е. 3) Соотношение „существует биекция множества Х на множество !'" есть соотношение эквивалентности, не обладающее, графиком (см. гл. Ш. $ 3). 4) Соотношенне,х ~ Е и у ~ Е" есть соотношение эквивалентности в Е, график которого есть Е Х Е. 5) Предположим, что А ~ Е.
Соотношение (хЕŠ— А и у=х) или (х~А и у~А) есть соотношение эквивалентности в Е. 6) ' Соотношение „х Е Х и у ~ Х и х — у делится на 4" есть соотношение эквивалентности в Х., Пгедложение 1. Для того чтобы соответствие Г между Х и Х было эквивалентностью ка Х, необходимо и достаточно, чтобы выполнялись следующие условии: а) Х есть область -1 определению соответствия Г; б) Г=1'! в) Г Г=Г.
Пусть à — соответствие между Х и Х и С вЂ” его график. Если à — эквивалентность на Х, то (х, х)~0 для всякого х~Х; следовательно, Х есть область определения для Г. Соотношение (х, у)~С' -1 -1 эквивалентно (у. х) ~С, а следовательно, и (х, у) ~ С, так что С =С вЂ” 1 и потому Г=Г. Соотношения (х, у)ЕС и(у, г)~С влекут (х, г) ~0, а это доказывает, что С О С ~ С; с другой стороны, соотношение (х, у)~0 влечет (х.
х)~С. а следовательно, и (х, у)~ОаС, так что С 1=. С ь С; таким образом, С = С о С и, следовательно, Г=Г Г. Обратно. предположим, что условия а), б), в) выполнены. Соотношение (х, у) ~ С симметрично ввиду б) и транзитивно ввиду в); следовательно, это соотношение эквивалентности, и. наконец, из а) вытекает, что это соотношение эквивалентности в Х. 2. Классы эквиваленкгности; фактормножество Пусть 7 — функция, Š— ее область определения, Р— ее график. Соотношение „х~Е и у~Е и 7'(х)=7'(у)" есть соотношение эквивалентности в'Е; мы скажем, что это соотношение есть соотношение эквивалентности, ассоциированное с 7'.
Оно эквивалентно соотно-, шению (3г)((х, г)Е Р и (у, г) ~ Р), т. е. соотношению (1г)((х, г)~ Р— ! -1 и (г, у)~ Р); его график, стало быть, есть Р о Р. Теперь мы покажем, что всякое соотношение эквивалентности К в множестве Е есть соотношение эквивалентности такого же типа. В самом деле, пусть С есть график для К. Для всякого х ~ Е (непустое) множество С (х) с= Е называется классом эквивалентности элемента х по соотношению К (или длк, или относительно соотношения К); иными словами, это множество таких у ~ Е, что К(х, у1. Всякое множество, представимое в виде С(х) для какого-нибудь х ~ Е, называется классом эквивалентности (по К).
Элемент класса эквивалентности называется также представителем этого класса. Множество классов эквивалентности по К (т. е. множество объектов вида С(х) для х~ Е) нааывается фактормкожеством множества Е по К и обозначается через Е/К; отображение х-+ С (х) (х ~ Е), у которого областью определения служит множество Е, а областью прибытия — множество Е/К, называется каноническим отображением множества Е на фактормножество Е/К.
Теперь можно сформулировать следующий критерий: С55. Пусть К вЂ” соотношение эквивалентности в множестве Е, а р — каноническое отображение множества Е ка фактормкожество Е/К. Тогда К 1 х, у ~ (4 (р (х) = р (у) ) В самом деле (при предыдущих обозначениях). пусть х и у— такие элементы из Е, что (х, у) Е С. Отсюда сразу же следует х~Е и у~Е; покажем, что С(х)=0(у). Так как у~С(х), то (предложение 1) С(у) ~(СоС)(х)=С(х). С другой стороны, (у, х)~0, откуда С(х)1=С(у) и, следовательно, 0(х)=С(у), т. е. р(х) = р(у).
Обратно, если С(х)='0(у), то у ~С(у)=0(х), откуда (х, у) ~С. а это доказывает критерий. Иссечение, ассоциированное с каноническим отображением р множества Е на фактормножество Е/К ($3, п'8, определение 11) называется кратко иссечекием множества Е (для соотношения К) Примеры.
1) Пусть К вЂ” соотношение эквивалентности „х ~ Е и у Е Е и х = у' в множестве Е; тогда класс эквивалентности для х ~ Е есть множество (х) и каноническое отображение х — ь (х) множества Е на фактормножество Е/К биективно. 2) Пусть Е и Р— два множества и К вЂ” соотношение эквивалентности в Е)!',Р, связанное с отображением рг, из множества Е )( Р на множество Е, Классы эквивалентности для К суть множества вида 1х) Х Р, где х ~ Е; отображение х-ь(х];х, Р есть биекция множества Е на фактормножество (Е )!', Р)/К. Пусть К вЂ” соотношение эквивалентности в множестве Е. Фактор- множество Е/К есть часть множества 4а(Е), а тождественное отображение фактормножества Е/К есть разбиение множества Е($4, п'7); в самом деле, если Π— график соотношения К, то х~С(х) для всякого х ~ Е, а если два класса эквивалентности С (х) н С (у) имеют общий элемент г. то имеют место К)х, В1 и К~к, у1, а следовательно, и К(х, у(, а потому С(х)=С(у).
Кроме того, соот- 128 ГЛ. Н ТЕОРИЯ МНОЖЕСТВ ношение ДХ) (Х ~ Е/К и х ~ Х и у ~ Х) 9 Н. Вурбкни является эквивалентным К»х, у». Обратно, пусть (Х,),к! — разбиение множества Е; нетрудно видеть, что соотношение (31)(! ~! и х~ Х, и у ~Х,) есть соотношение эквивалентности К в Е; классы эквивалентности по К суть не что иное, как множества Х, и!ого разбиения, и отображение ! — ь Х, есть биекция множества ! на фактормножество Е/К.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
