Выберите свойства которыми обладает отношение эквивалентности

Отношение эквивалентности

в означает, что а эквивалентно в.

В соответствии с определением для отношения эквивалентности выполняются свойства:

а – рефлексивности;

а – симметричности;

с а

с – транзитивности.

Примеры отношений эквивалентности – равенство, подобие треугольников.

Используя отношение эквивалентности можно проводить разбиение множества на классы эквивалентности.

Класс эквивалентности, порожденный элементом – множество всех элементов из , вступающих с в отношение эквивалентности.Класс эквивалентности определяется так:

, для подбираются элементы, находящиеся в соответствии с элементомх.

Отношение эквивалентности имеет большое практическое применение, позволяющее разбивать множества на классы эквивалентности. Класс эквивалентности можно получить, если для выбранного элемента х из множества Х можно подобрать элементы , находящиеся сх в одном классе эквивалентности

.

Фактор-множества множества по отношению эквивалентностиφ – множество всех различных классов эквивалентности, обозначаемое А / φ.

Индекс разбиения, порожденный отношением φ – это мощность фактор-множества А / φ.

Пример 2.11.

а) Отношение равенства на любом множестве является отношением эквивалентности.

Равенство – это минимальное отношение эквивалентности в том смысле, что при удаление любой пары из (то есть любой единицы на диагонали матрицы) оно перестает быть рефлексивным и, следовательно, уже не является эквивалентностью.

б) Утверждения видаили, состоящие из формул, соединенных знаком равенства, задают бинарное отношение на множестве формул, описывающих суперпозиции элементарных функций. Это отношение обычно называется отношением равносильности и определяется следующим образом: формулы равносильны, если они задают одну и ту же функцию. Равносильность, хотя и обозначается знаком =, отличается от отношения равенства , так как оно может выполняться для различных формул. Отношениедля формул – это совпадение формул по написанию. Оно называетсяграфическим равенством.

в) Рассмотрим множество треугольников на плоскости, считая, что треугольник задан, если заданы координаты его вершин. Два треугольника называются конгруэнтными (равными), если они при наложении совпадают, то есть могут быть переведены друг в друга путем некоторого перемещения. Конгруэнтность является отношением эквивалентности на множестве треугольников.

г) Отношение «иметь один и тот же остаток от деления на 9» является эквивалентностью на . Это отношение выполняетсядля пар (12, 21), (17, 36) и не выполняется для пар (11, 13), (19, 29).

Пусть на множествезадано отношение эквивалентности . Осуществим следующее построение. Выберем элемент и образуем класс (подмножество), состоящий изи всех элементов, эквивалентных; затем выберем элементи образуем класс, состоящий изи всех элементов, эквивалентных, и т.д. Получится система классов(возможно, бесконечная) такая, что любой элемент из входит хотя бы в один класс, то есть. Эта система классов обладает следующими свойствами:

она образует разбиение, то есть классы попарно не пересекаются;

любые два элемента из одного класса эквивалентны;

любые два элемента из разных классов неэквивалентны.

Все эти свойства вытекают из рефлексивности, симметричности и транзитивности . Действительно, если бы классы, например и, пересекались, то они имели бы общий элемент, эквивалентныйи, но тогда из-за транзитивности было бы , что противоречит построению. Аналогично доказываются другие два свойства.

Построенное разбиение, то есть система классов, называется системой классов эквивалентности по отношению . Мощность этой системы называется индексом разбиения. С другой стороны, любое разбиение на классы определяет некоторое отношение эквивалентности, а именно, отношение «входить в один и тот же класс данного разбиения».

а) Все классы эквивалентности по отношению равенства состоят из одного элемента.

б) Формулы, описывающие одну и ту же элементарную функцию, находятся в одном классе эквивалентности по отношению равносильности. В этом примере счётны само множество формул, множество классов эквивалентности (то есть индекс разбиения) и каждый класс эквивалентности.

в) Разбиение по отношению «иметь общий остаток от деления на 7» имеет конечный индекс 7 и состоит из 7 счетных классов: 0, 7, 14, …; 2, 9, 16, …; …; 6, 13, 20, …

1.11 Отношение эквивалентности

Отношение эквивалентности представляет собой строгое матема­тическое определение таких обыденных понятий как «одинаковость» или «неразличимость».

Обозначается X

Y. Отношение эквивалентности А в множестве М означает, что упорядоченная пара (X, Y) принадлежит множеству А Ì М´М.

Отношение эквивалентности обладает свойствами:

· Рефлексивности: X

· Симметричности: если X

Y, то Y

· Транзитивности: если X

Y и Y

Z, то X

Важнейшее значение эквивалентности состоит в том, что это отношение определяет признак, который допускает разбиение множества М на непересекающиеся подмножества, называемые Клас­Сами эквивалентности. И наоборот: всякое разбиение множества М на непересекающиеся подмножества определяет между элементами этого множества некоторое отношение эквивалентности.

Например: Отношение «проживать в одном доме», заданное в множестве жителей города, является эквивалентностью и разбивает это множество на непересекающиеся подмножества людей, являющихся соседями по дому.

Все элементы, принадлежащие некоторому классу МI разбиения <М1, М2. МN> множества М на классы эквивалентности, связаны отношением эквивалентности. Любой из этих элементов определяет данный класс и может служить его Представителем или Эталоном.

Произвольное отношение эквивалентности определяет на некотором множестве обобщенную форму равенства. Классы эквивалентности состоят из всех тех элементов, которые неразличимы с точки зрения данного отношения эквивалентности. При этом каждый класс определяется его представителем (эталоном) и отождествляется с некоторым общим свойством или совокупностью свойств входящих в него элементов.

Предельным случаем отношения эквивалентности является Тождественное равенство. Очевидно, что единственный элемент, тождественно равный какому-либо данному элементу, есть этот самый элемент. Следовательно, в данном случае имеем самое полное разбиение, при котором классы эквивалентности содержат только по одному элементу исходного множества.

Рассмотрим матрицу отношения эквивалентности.

Элементы, принадлежащие некоторому классу эквивалентности, попарно эквивалентны между собой, а их сечения совпадают. Сле­довательно, столбцы матрицы отношения эквивалентности для элемен­тов одного класса одинаковы и содержат «1» во всех строках, которые соответствуют этим элементам. Так как классы эквивалентности не пересекаются, то в столбцах различных классов не будет единиц в одинаковых строках. Если расположить элементы множества так, чтобы в каждом классе эквивалентности принадлежащие ему элементы стояли рядом, то единичные элементы матрицы образуют непересекаю­щиеся квадраты, диагонали которых располагаются на главной диагонали матрицы.

Например: Пусть множество М разбито на классы эквивалент­ности следующим образом:

Признаки, по которым элементы множества разбиваются на классы, могут быть самыми разнообразными, но все же такой признак не вполне произволен.

Отношение эквивалентности

Следующие отношения не являются отношениями эквивалентности:

• Отношения порядка, так как они не являются симметричными.
• Отношение быть знакомым на множестве людей, так как оно не транзитивное.

Классы эквивалентности

• [math]M = M_1 \cup M_2 \cup \ldots \cup M_n \cup \ldots[/math]
• [math]M_i \cap M_j = \varnothing[/math] при [math]i \neq j[/math] .

Примерами разбиений являются:

• Разбиение многоугольников на группы по числу вершин.
• Разбиение треугольников по свойствам углов (остроугольные, прямоугольные, тупоугольные).
• Разбиение учащихся школы по классам.

• любые два элемента одного класса находятся в отношении [math]\thicksim[/math]
• любые два элемента разных классов не находятся в отношении [math]\thicksim[/math]

Семейство всех классов эквивалентности множества образует множество, называемое фактор-множеством, или факторизацией множества [math]M[/math] по отношению [math]\thicksim[/math] , и обозначаемое [math]M/^<\thicksim>[/math] .

Примеры

• Равенство — классический пример отношения эквивалентности на любом множестве, в т. ч. вещественных чисел
• Равенство по модулю: [math] a \equiv b

• отношение подобия [math] («\thicksim «) [/math]
• отношение параллельности [math]\colon

Выберите свойства которыми обладает отношение эквивалентности

Арифметику остатков лучше всего вводить с помощью отношения эквивалентности. Поскольку такие отношения будут играть важную роль как в этой главе, так и далее, стоит подробно разобрать это базисное понятие.

Пусть X — конечное или бесконечное множество. Отношением на X называется правило, по которому «сравниваются» его элементы. Это неформальное определение, но его вполне достаточно для наших целей. Заметим, что для определения отношения мы должны четко задать само множество; другими словами, нам должно быть ясно, какие элементы нужно сравнивать.

Рассмотрим несколько примеров. На множестве целых чисел есть много простых отношений, вроде «равно», «не равно», «меньше, чем», «меньше или равно». На множестве цветных мячей у нас есть отношение «тот же цвет». Последний пример, ввиду своей конкретности, хорош для запоминания в качестве модельного случая. Кстати, мы предполагаем, что каждый мяч из множества окрашен только в один цвет, пестрые мячи мы не рассматриваем.

Отношение эквивалентности — это отношение весьма специфичного вида. Возвращаясь к общим определениям, предположим, что X — множество, в котором было определено отношение. Удобно зафиксировать какой-нибудь символ для обозначения эквивалентности, обычно употребляют значок «

». С этого момента «

» будет отношением эквивалентности,

если для всех выполнены следующие свойства:

Первое свойство называется рефлексивностью. Оно говорит, что когда мы имеем отношение эквивалентности, любой элемент эквивалентен сам себе. Это свойство верно для равенства целых чисел: любое целое число равно самому себе. Но оно не выполнено для отношения Поэтому на множестве не является отношением эквивалентности.

Второе свойство называется симметричностью. Отношение на множестве целых чисел не симметрично. Действительно, в то время как неравенство ложно. С другой стороны, отношение на рефлексивно, но не симметрично.

Третье — свойство транзитивности. На множестве целых чисел отношения «равно», «меньше, чем», «меньше или равно», — транзитивны. А вот «не равно» этим свойством не обладает. Действительно, и но из этих неравенств не следует Добавим, что симметрично, но не рефлексивно.

Мы предусмотрительно привели примеры отношений, которые не удовлетворяют этим свойствам, потому что это единственный путь к пониманию их действительного смысла. Именно владение примерами и контрпримерами обеспечивает успех в усвоении новых понятий. В примерах отношения эквивалентности нет недостатка. Равенство целых чисел, очевидно, удовлетворяет всем свойствам, выписанным выше. Отношение «тот же цвет» на множестве цветных мячей — еще один простой и, пожалуй, самый яркий пример. Среди примеров отношения эквивалентности на множестве многоугольников находятся такие отношения, как «одинаковое число сторон» и «одна и та же площадь».

Отношение эквивалентности используют для классификации элементов данного множества, группируя их в подмножества по принципу схожести свойств. Естественное разбиение множества, индуцированное отношением эквивалентности, называется разбиением на классы эквивалентности. Пусть на множестве X задано отношение эквивалентности и х — элемент этого множества. Классом эквивалентности элемента х называется подмножество в X, состоящее из всех элементов, эквивалентных х относительно Обозначив класс эквивалентности элемента х символом х, можно записать:

Приведем простой пример. Обозначим символом М множество цветных мячей с отношением эквивалентности «тот же цвет». Класс эквивалентности красного мяча в М состоит из всех красных мячей, содержащихся в М.

Одно из свойств классов эквивалентности настолько важно, что мы назовем его основным принципом классов эквивалентности. Принцип гласит, что любой элемент класса эквивалентности — хороший представитель всего класса. Иначе говоря, зная один элемент из класса эквивалентности, можно немедленно восстановить этот класс полностью. Этот факт бросается в глаза, когда мы имеем дело с множеством М цветных мячей и отношением «тот же цвет». Предположим, Вам говорят, что в картонной коробке находятся все элементы одного класса эквивалентности множества М. Увидев один элемент из этого множества (допустим, это синий мяч), Вы немедленно заключаете, что в коробке лежит класс эквивалентности всех синих мячей М. Проще и быть не может!

Вернемся к абстрактному множеству X с отношением эквивалентности Основной принцип говорит, что если у — элемент из класса эквивалентности х, то классы эквивалентности х и у совпадают. То же самое можно выразить короче:

Докажем это непосредственно из определяющих свойств отношения эквивалентности. Если то, по определению класса эквивалентности, Ввиду симметричности, Но если то и Тогда свойство транзитивности влечет Мы доказали включение: . Похожее рассуждение доказывает обратное включение: Вероятно, это все может показаться несколько педантичным. Но основной принцип — такой источник неразберихи и ошибок, что нам не стоит жалеть усилий на прояснение его точного смысла. Кроме того, полезно осознать, что он непосредственно следует из определения отношения эквивалентности. Кстати о педантичности: вы поняли, что свойство вытекает из рефлексивности?

Основной принцип приводит к важнейшему свойству отношения эквивалентности. Как и раньше, пусть X — множество с отношением эквивалентности тогда

(1) X — объединение своих классов эквивалентности относительно и

(2) два разных класса эквивалентности не могут иметь общего элемента.

Первое утверждение следует из часто упоминаемого факта: класс эквивалентности элемента содержит сам этот элемент. Для доказательства второго предположим, что элементы Так как то по основному принципу Аналогично Так что у. Заметим, что свойства (1) и (2) означают, что множество X разбито на непересекающиеся подмножества, классы эквивалентности. Другими словами, мы имеем дело с разбиением множества

Множество, составленное из классов эквивалентности множества X относительно отношения эквивалентности имеет специальное название: фактормножество X по отношению Отметим, что элементы фактормножества — это подмножества в Поэтому фактормножество не является подмножеством в X, будьте внимательны!

Закончим этот параграф примером, в котором проявляется наконец истинная природа дробей. Из чего состоит дробь? Когда Вы на нее смотрите, то видите два числа, одно из которых (знаменатель) должно быть ненулевым. Конечно, Вы ее, вероятно, воспринимаете как частное. Но если на Вас надавить, Вы можете попытаться выбрать более легкий выход и сказать, что дробь в действительности — пара чисел, одно из которых не равно нулю. Однако, такое определение некорректно.

В математике две пары равны, если они имеют одинаковые первый и второй элементы. Так, пары (2,4) и (1,2) неравны. Но дроби 2/4 и 1/2 равны; так что дроби — не пары чисел.

Что же такое дроби? Это элементы фактормножества! Рассмотрим множество пар целых На стандартном жаргоне Две пары и целых чисел можно теперь называть эквивалентными, если Легко проверить, что это отношение эквивалентности, а дробь — класс эквивалентности множества относительно этого отношения. Следовательно, означает не пару а бесконечное множество всех пар из эквивалентных Итак, множество рациональных чисел — это фактормножество множества по только что определенному отношению эквивалентности.

Представьте себе на минуту, что Вы до сих пор ничего о дробях не слышали и Вам придется исходить из описания, сделанного выше. Если Вам теперь скажут, что нужно вычислять с дробями, Вы почувствуете, что имеете вескую причину для паники: Вы же только что выучили, что дробь — это бесконечное множество. Мысль о прибавлении к одному бесконечному множеству другого бесконечного множества внушает легкое беспокойство. Именно в этот момент приходит на помощь основной принцип. Вам не нужно заботиться о бремени всего бесконечного множества; нужно знать только один элемент из него. Этот элемент расскажет Вам обо всем, что

необходимо знать о целом классе эквивалентности. Более того, Вас устроит любой элемент класса.

Итак, Вы можете оперировать с 1/2 как обычно, так же, как если бы это была пара чисел. Вы вспоминаете, что дробь — это класс эквивалентности, только когда (в процессе вычислений) оказывается, что дробь можно сократить. В этот момент вы заменяете одного представителя класса эквивалентности на другой для упрощения вычислений.

Зачем мы сделали такое длинное отступление о дробях? В следующем параграфе определятся отношение эквивалентности на множестве а фактормножество этого отношения играет абсолютно фундаментальную роль в этой книге. Как и в случай дробей, классы эквивалентности будут бесконечны, а нам предстоит делать вычисления с ними. Но теперь Вы знаете, что нет причин для волнения.