Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







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





Рассмотрим на множестве дробей 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.

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

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

 

Упражнения

1.На множестве X пря­моугольников (рис. 107) задано отношение «иметь равные площади». По­стройте граф отношения и докажите, что оно являет­ся отношением эквивалентности. Какие классы эквивалентности порождает это отношение на множестве X"?

Рис. 107

2.Объясните, почему отношение равенства отрезков является от­ношением эквивалентности, а отношение «короче» не является.

3.X - множество прямых плоскости. Какое из следующих отношений является отношением эквивалентности на этом множестве: а) «х параллельна у»; б) «х перпендикулярна у»; в) «х пересекает у»?

4.На множестве X = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} задано отношение «иметь один и тот же остаток при делении на 4». Является ли оно от­ношением эквивалентности?

5.Можно ли разбить множество Х= {7-3; 22, 5 · 2; 60 : 6; 1+ 3; 0 : 4; 0 ·10; 4:(10-10)} на классы при помощи отношения «иметь равные значения»?

6.На множестве X = {213, 37, 21, 87, 82} задано отношение Р - «иметь в записи одинаковые цифры». Является ли Р отношением эквивалентности?

7.На множестве целых чисел от 0 до 999 задано отношение К - «иметь в записи одно и то же число цифр». Покажите, что К - отношение эквивалентности. На сколько классов эквивалентности разби­вается данное множество при помощи отношения К? Назовите наименьший и наибольший элементы каждого класса.

8.Сколько классов эквивалентности порождает на множестве на­туральных чисел отношение «оканчиваться одной и той же циф­рой»? Назовите по одному представителю каждого класса.

9.X - множество отрезков. Какие из следующих отношений яв­ляются отношениями порядка на этом множестве: а) «х равно у»; б) «х длиннее у»; в) «х длиннее у в 3 раза»?

10.Упорядочивают ли множество натуральных чисел отношения: а) «больше в 2 раза»; б) «больше на 2»; в) «непосредственно следовать за»; г) «х - делитель у»?

11.Отношение Т- «иметь одно и то же число делителей» задано на множестве X = {1, 2, 4, 6, 7, 8, 10, 11}. Является ли Т отношением экви­валентности? Отношением порядка?

12.Выясните, какие из следующих высказываний истинны, а какие ложны; свой ответ обоснуйте:
а) Отношение «х кратно у» на множестве натуральных чисел рефлективно и симметрично.
б) Отношение «х кратно у» на множестве натуральных чисел анти­симметрично и транзитивно.
в) Отношение «х кратно у» на множестве натуральных чисел явля­ется отношением порядка.

13.Между множествами существуют отношения равенства, равномощности, «быть подмножеством». Какие из них являются отноше­ниями эквивалентности, а какие отношениями порядка?

14.Решите задачи для младших школьников и укажите свойства отношений, которые были при этом использованы:
а) Мальчик составил пирамидку из трех колечек: желтого, красно­го и зеленого. В каком порядке он расположил колечки, если желтое больше зеленого, а красное меньше зеленого?
б) Четверо учащихся получили разные оценки за контрольную работу. Игорь получил оценку выше, чем Петр, Петр ниже, чем Максим, но выше, чем Кирилл. Кто получил самую низкую оценку?

50. Основные выводы § 10

Изучив материал данного параграфа, мы познакомились со сле­дующими понятиями:

- бинарное отношение на множестве;

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

- отношение порядка.

Выяснили, что отношения на множестве задают так же, как и соот­ветствия. Узнали, что отношения на множестве могут обладать свой­ствами:

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

- симметричности;

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

- транзитивности;

- связанности.

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

Узнали, что существует тесная взаимосвязь между отношением эк­вивалентности на множестве X и разбиением этого множества на классы.









Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2019 zdamsam.ru Размещенные материалы защищены законодательством РФ.