Лекция 5. Отношения на множестве © Гусева И.Н., кафедра СМиРЯ, КГУ, 2010. - презентация

1 Лекция 5. Отношения на множестве © Гусева И.Н., кафедра СМиРЯ, КГУ, 2010

2 ОТНОШЕНИЯ НА МНОЖЕСТВЕ В математике изучают не только связи между элементами двух множеств, т. е. соответствия, но и связи между элементами одного множества. Называют их отношениями. Отношения многообразны. Между понятиями это отношения рода и вида, части и целого; между предложениями отношения следования и равносильности; между числами «больше», «меньше», «равно», «больше на...», «меньше на...», «следует» и др. Если рассматривают отношения между двумя элементами, то их называют бинпарными; отношения между тремя элементами тернпарными; отношения между п элементами n-парными. Все названные выше отношения являются бинпарными. Примером тернарного отношения может служить отношение между точками прямой «точка х лежит между точками у и z».

3 Изучение отношений между объектами важно для познания как самих объектов, так и для познания реального мира в целом. В нашем курсе мы будем рассматривать в основном бинарные отношения, но чтобы увидеть общность методических подходов к изучению в начальном курсе математики конкретных отношений, понять важнейшие математические идеи, связанные с отношениями, учителю надо знать, какова математическая сущность любого отношения, какими свойствами они могут обладать, какие основные виды отношений изучает математика.

4 Понятие отношения на множестве Чтобы определить общее понятие бинарного отношёния на множестве, поступим так же, как и в случае с соответствиями, т.е. рассмотрим сначала конкретный пример. Пусть на множестве Х = {2, 4,6, 8} задано отношение «меньше». Это означает, что для любых двух чисел из множества Х можно сказать, какое из них меньше: 2 < 4, 2 < 6, 2 < 8, 4 < 8, 6 < 8. Полученные неравенства можно записать иначе, в виде упорядоченных пар: (2, 4), (2, 6), (2, 8), (4, 6), (4, 8), (6, 8). Но все пары есть элементы декартова произведения Х×Х, поэтому об отношении «меньше», заданном на множестве Х, можно сказать, что оно является подмножеством множества Х×Х. Вообще бинарные отношения на множестве Х определяют следующим способом: Определение. Бинарным отношением на множестве Х называется всякое подмножество декартова произведения Х х Х.

5 Так как в дальнейшем мы будем рассматривать только бинарные Отношения, то слово «бинарные», как правило, будем опускать. (условимся отношения обозначать буквами R, S, Т, Р и др. Если R- отношения на множестве Х, то, согласно определению, Rє Х×Х. С другой стороны, если задано некоторое подмножество множества Х×Х, то оно определяет на множестве Х некоторое отношение R. Утверждение о том, что элементы х и у находятся в отношении R, можно записывать так: (х, у) єR или x-ray. Последняя запись читается: «Элемент х находится в отношении R с элементом у». Отношения задают так же, как соответствия. Отношение можно задать, перечислив пары элементов множества Х, находящиеся в этом отношении. Формы представления таких пар могут быть различными они аналогичны формам задания соответствий. Отличия касаются задания отношений при помощи графа.

6 Построим, например, граф отношений «меньше», заданного на множестве Х = {2, 4, 6, 8}. Для этого элементы множества Х изобразим точками (их называют вершинами графа), а отношение «меньше» стрелкой. На том же множестве Х можно рассмотреть другое отношение «кратно». Граф этого отношения будет в каждой вершине иметь петлю (стрелку, начало и конец которой совпадают), так как каждое число кратно самому себе.

7 Отношение можно задать при помощи предложения с двумя переменными. Так, например заданы рассмотренные выше отношения «меньше» и «кратно», причем использована краткая форма предложений «число х меньше числа у» и «число х кратно числу у». Некоторые такие предложения можно записывать, используя символы. Например, отношения «меньше» и «кратно» можно было задать в таком виде: «х у». Отношение «х больше у на 3» можно записать в виде равенства х = у + 3 (или ху = 3).

8 Понятием отношения, обратного данному, часто пользуются при начальном обучении математике. Например, чтобы предупредить ошибку в выборе действия, с помощью которого решается задача: «У Пети 7 карандашей, что на 2 меньше, чем у Бори. Сколько карандашей у Бори?» ее переформулируют: «У Пети 7 карандашей, а у Бори на 2 больше. Сколько карандашей у Бори?» Видим, что переформулировка свелась к замене отношения «меньше на 2» обратным ему отношением «больше на 2».

9 Свойства отношений Мы установили, что бинарное отношение на множестве Х представляет собой множество упорядоченных пар элементов, принадлежащих декартову произведению ХхХ. Это математическая сущность всякого отношения. Но, как и любые другие понятия, отношения обладают свойствами. Их удалось выделить, изучая различные конкретные отношения. Свойств достаточно много, в нашем курсе мы будем изучать только некоторые.

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

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

12 Если отношение R рефлексивно на множестве Х, то в каждой вершине графа данного отношения имеется петля. Справедливо и обратное утверждение: граф, каждая вершина которого имеет петлю, задает отношения, обладающие свойством рефлексивности. Примеры рефлексивных отношений: Отношение «кратно» на множестве натуральных чисел (каждое натуральное число кратно самому себе); отношение подобия треугольников (каждый треугольник подобен самому себе). Существуют отношения, которые свойством рефлексивности не обладают. Таким, например, является отношение перпендикулярности на множестве отрезков: нет ни одного отрезка, о котором можно сказать, что он перпендикулярен самому себе. Поэтому на графе отношения перпендикулярности (рис. 99) нет ни одной петли. Не обладает свойством рефлексивности и отношение «длиннее» для отрезков.

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

14 Определение. Отношение R на множестве Х называется симметричным, если выполняется условие: из того, что элемент х находится в отношении R с элементом у, следует, что и элемент у находится в отношении R с элементом х.

15 Граф симметричного отношения обладает особенностью: вместе с каждой стрелкой, идущей от х к у, граф содержит и стрелку, идущую от у к х. Справедливо и обратное утверждение. Граф, содержащий вместе с каждой стрелкой, идущей от х к у, и стрелку, идущую от у к х, является графом симметричного отношения. В дополнение к рассмотренным двум примерам симметричных отношений присоединим ещё такие: - отношение параллельности на множестве прямых (если прямая х параллельна прямой у, то и прямая у параллельна прямой х); - отношение подобия треугольников (если треугольник F подобен треугольнику Р, то треугольник Р подобен треугольнику F).

16 Существуют отношения, которые свойством симметричности не обладают. Таким, например, является отношение «длиннее» на множестве отрезков. Действительно, если отрезок х длиннее отрезка у, то отрезок у не может быть длиннее отрезка х. Про отношения «длиннее» говорят, что оно обладает свойством анти симметричности или просто антисимметрично. Определение. Отношение R на множестве Х называется антисимметричным,, если для различных элементов х и у из множества Х выполнено условие: из того, что х находится в отношении R с элементом у, следует, что элемент у в отношении R с элементом х не находится.

17 Граф антисимметричного отношения обладает особенностью: если две вершины графа соединены стрелкой, то эта стрелка только одна. Справедливо и обратное утверждение: граф, вершины которого соединены только одной стрелкой, есть граф антисимметричного отношения. Кроме отношения «длиннее» на множестве отрезков свойством анти симметричности, например, обладают: - отношение «больше» для чисел (если х больше у, то у не может быть больше х); - отношение «больше на 2» для чисел (если х больше у на 2, то у не может быть больше на 2 числа х).

18 Существуют отношения, не обладающие ни свойством симметричности, ни свойством анти симметричности. Рассмотрим, например, отношение «быть сестрой» на множестве детей одной семьи. Пусть в семье трое детей: Катя, Маша и Толя. Тогда граф Т отношения «быть сестрой» будет таким, как на рисунке. Он показывает, что данное отношение не обладает ни свойством симметричности, ни свойством анти симметричности. Обратим внимание еще раз на одну особенность графа отношение «длиннее» (рис. 99). На нем можно заметить: если стрелки про- от е к а и от а к с, то есть стрелка от е к с; если стрелки приведены от е к b и от b к с, то есть стрелка нот е к с и т.д. Эта особенность графа отражает важное свойство отношения «длиннее»: Первый отрезок длиннее второго, а второй длиннее третьего, то первый - длиннее третьего. Говорят, что это отношение обладает свойством транзитивности или просто транзитивно.

19 Определение. Отношение R на множестве Х называется транзитивным, если выполняется условие: из nого, что элемент х находится в отношении R с элементом у и элемент у находится в отношении R с элементом z, следует, что элемент х находится в отношении R с элементом z. Граф транзитивного отношения с каждой парой стрелок, идущих от х к у и у к х, содержит стрелку, идущую от х к z. Справедливо и обратное утверждение. Кроме отношения «длиннее» на множестве отрезков свойством транзитивности обладает отношение равенства: если отрезок х равен отрезку у и отрезок у равен отрезку х, то отрезок х равен отрезку х. Это свойство отражено и на графе отношения равенства

20 Существуют отношения, которые свойством транзитивности не обладают. Таким отношением является, например, отношение перпендикулярности: если отрезок а перпендикулярен отрезку b, а отрезок b перпендикулярен отрезку c, то отрезки а и c не перпендикулярны!

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

22 Ре ш е н и е. Отношение R антисимметрично, так как вершины графа соединяются только одной стрелкой. Отношение R транзитивно, так как с парой стрелок, идущих от b к а и от а к с, на графе есть стрелка, идущая от b к с. Отношение R связанно, так как любые две вершины соединены стрелкой. Отношение R свойством рефлексивности не обладает, так как на графе есть вершины, в которых петли нет. Задача 1. Сформулировать свойства отношения R, заданного при помощи графа

23 Ре ш е н и е. «Больше в 2 раза» это краткая форма отношения «число х больше числа у в 2 раза». Это отношение антисимметрично, так как выполняется условие: из того, что число х больше числа у в 2 раза, следует, что число у не больше числа х в 2 раза. Данное отношение не обладает свойством рефлексивности, потому что ни про одно число нельзя сказать, что оно больше самого себя в 2 раза. Заданное отношение не транзитивно, так как из того, что число х больше числа у на 2, а число у больше числа на 2, следует, что число х не может быть больше числа на 2. Отношение на множестве натуральных чисел свойством связанности не обладает, так как существуют пары таких чисел х и у что ни х не больше числа у в два раза, ни число у не больше х в 2 раза. Это числа 7 и 3, 5 и 8 и др. Задача 2. Сформулировать свойства отношения «больше в 2 раза», заданного на множестве натуральных чисел.

24 Отношения эквивалентности и порядка Определение. Отношение R на множестве Х называется отношением эквивалентности, если оно одновременно обладает свойствами рефлексивности, симметричности и транзитивности.

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

26 Верно и обратное утверждение: если какое-либо отношение, заданное на множестве Х, порождает разбиение этого множества на классы, то оно является отношением эквивалентности. Рассмотрим, например, на множестве Х = {1, 2, 3,4, 5,6, 7, 8, 9, 10} отношение «иметь один и тот же остаток при делении на 3». Оно порождает разбиение множества Х на классы: в один попадут все числа, при делении которых на 3 получается в остатке 0 (это числа 3, 6, 9), во второй - числа, при делении которых на 3 в остатке получается 1 (это 1, 4, 7, 10), и в третий все числа, при делении которых на 3 в остатке получается 2 (это числа 2, 5, 8). Действительно, полученные подмножества не пересекаются и их объединение совпадает с множеством Х. Следовательно, отношение «иметь один и тот же остаток при делении на 3», заданное на множестве Х, является отношением эквивалентности.

27 Заметим, что утверждение о взаимосвязи отношения эквивалентности и разбиения множества на классы нуждается в доказательстве. Мы его опускаем. Скажем только, что если отношение эквивалентности имеет название, то соответствующее название дается классам. Например, если на множестве отрезков задается отношение равенства (а оно является отношением эквивалентности), то множество отрезков разбивается на классы равных отрезков. Отношению подобия соответствует разбиение множества треугольников на классы подобных треугольников. Итак, имея отношение эквивалентности на некотором множестве, мы можем разбить это множество на классы. Но можно поступить и наоборот: сначала разбить множество на классы, а затем определить отношение эквивалентности, считая, что два элемента эквивалентны тогда и только тогда, когда они принадлежат одному классу рассматриваемого разбиения. Принцип разбиения множества на классы при помощи некоторого отношения эквивалентности является важным принципом математики. Почему?

28 Во-первых эквивалентный - это значит равносильный взаимозаменяемый, поэтому элементы одного класса эквивалентности взаимозаменяемы. Так, дроби, оказавшиеся в одном классе эквивалентности, неразличимы с точки зрения отношения равен и дробь 3/6 может быть заменена другой, например 1/2. И эта замена не изменит результата вычислений. Во-вторых, поскольку в классе эквивалентности оказываются элементы, неразличимые с точки зрения некоторого отношения, то считают, что класс эквивалентности определяется любым своим представителем, т. е. произвольным элементом этого класса. Так, любой класс равных дробей можно задать, указав любую дробь, принадлежащую этому классу. Определение класса эквивалентности по одному представителю позволяет вместо всех элементов множества изучать совокупность отдельных представителей из классов эквивалентности. Например, отношение эквивалентности «Иметь одинаковое число вершин», заданное на множестве многоугольников, порождает разбиение этого множества на классы треугольников, четырехугольников, пятиугольников и т.д. Свойства, присущие некоторому классу, рассматриваются на одном его представителе.

29 В-третьих, разбиение множества на классы с помощью отношения эквивалентности используется для введения новых понятий. Например, понятие «пучок прямых» можно определить как то общее, что имеют параллельные между собой прямые. Вообще любое понятие которым оперирует человек, представляет собой некоторый класс эквивалентности «стол», «дом», «книга» все эти понятия являются обобщенными представлениями о множестве конкретных предметов, имеющих одинаковое назначение. Другим важным видом отношений являются отношения порядка. Определение. Отношение R на множестве Х называется отношением порядка, если оно одновременно обладает свойствами анти симметричности и транзитивности.

30 Примерами отношений порядка могут служить: отношение «меньше» на множестве натуральных чисел; отношение «короче» на множестве отрезков, поскольку они антисимметричны и транзитивны. Если отношение порядка обладает еще свойством связанности, то говорят, что оно является отношением линейного порядка Например, отношение «меньше» на множестве натуральных чисел является отношением линейного порядка, так как обладает свойствами симметричности, транзитивности и связанности. Определение. Множество Х называется упорядоченным, если на нем задано отношение порядка.

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

32 Лекция закончена, уважаемый СТУДЕНТ, можете переходить к практическому занятию 5