Отношения эквивалентности и порядка

Лекция 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.

Например, множество натуральных чисел можно упорядочить и с помощью отношения «меньше», и с помощью отношения «кратно» - оба они являются отношениями порядка. Но отношение «меньше», в отличие от отношения «кратно», обладает еще и свойством связанности. Значит, отношение «меньше» упорядочивает множество на­туральных чисел линейно.

Не следует думать, что все отношения делятся на отношения экви­валентности и отношения порядка. Существует огромное число от­ношений, не являющихся ни отношениями эквивалентности, ни отно­шениями порядка.

Дата добавления: 2014-01-06