Отношение равенства на множестве треугольников (7 видео)

Лекция 21. Свойства отношений

1. Свойство рефлексивености

2. Свойство симметричности

3. Свойство транзитивности

Свойства отношений

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

Рассмотрим на множестве отрезков, представленных на рис. 98, отношения перпендикулярности, равенства и «длиннее». Построим графы этих отношений (рис. 99) и будем их сравнивать. Видим, что граф отношения равенства отличается от двух других наличием петель в каждой его вершине. Эти петли — результат того, что отношение равенства отрезков обладает свойством: любой отрезок равен самому себе. Говорят, что отношение равенства обладает свойством рефлексивности или просто, что оно рефлексивно.

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

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

R рефлексивно на Х ↔ х R х для любого х € X.

опр.

Если отношение R рефлексивно на множестве X, то в каждой вершине графа данного отношения имеется петля. Справедливо и обратное утверждение: граф, каждая вершина которого имеет петлю, задает отношения, обладающие свойством рефлексивности.

Примеры рефлексивных отношений:

— отношение «кратно» на множестве натуральных чисел (каждое натуральное число кратно самому себе);

— отношение подобия треугольников (каждый треугольник подобен самому себе).

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

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

— если один отрезок перпендикулярен другому отрезку, то этот «другой» перпендикулярен первому;

— если один отрезок равен другому отрезку, то этот «другой» равен первому.

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

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

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

R симметрично на Х ↔ (х R y →yRx).

опр.

Граф симметричного отношения обладает особенностью: вместе с каждой стрелкой, идущей от х к у, граф содержит и стрелку, идущую от у к x. Справедливо и обратноеутверждение. Граф, содержащий вместе с каждой стрелкой, идущей от x к у, и стрелку, идущую от у к x, является графом симметричного отношения.

В дополнение к рассмотренным двум примерам симметричных отношений присоединим еще такие:

-отношениепараллельности на множестве прямых (если прямая x параллельна прямой у, то и прямая у параллельна прямой х)

-отношение подобия треугольников (если треугольник F подобен треугольнику Р, то треугольник Р подобен треугольнику F).

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

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

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

R симметрично на Х ↔ (х R y _^ x≠y →yRx).

опр.

Граф антисимметричного отношения обладает особенностью: если две вершины графа соединены стрелкой, то эта стрелка только одна. Справедливо и обратное утверждение: граф, вершины которого соединены только одной стрелкой, есть граф антисимметричного отношения.

Кроме отношения «длиннее» на множестве отрезков свойством антисимметричности, например, обладают:

— отношение «больше» для чисел (если х больше у, то у не может
быть больше х);

— отношение «больше на 2» для чисел (если х больше у на 2, то у не может быть больше на 2 числа х),

Существуют отношения, не обладающие ни свойством симметричности, ни свойством антисимметричности. Рассмотрим, например, отношение «быть сестрой» на множестве детей одной семьи. Пусть в семье трое детей: Катя, Маша и Толя. Тогда граф отношения «быть сестрой» будет таким, как на рисунке 100. Он показывает, что данное отношение не обладает ни свойством симметричности, ни свойством антисимметричности.

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

Определение. Отношение R на множестве X называется транзитивным, если выполняется условие; из того, что элемент х находится в отношении R с элементом у и элемент у находится в отношении R с элементом z, следует, что элемент х находится в отношении К с элементом z .

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

R транзитивно на X ↔ (х R y _^ yRz → xRz).

опр.

Граф транзитивного отношения с каждой парой стрелок, идущих от x к у и у к z, содержит стрелку, идущую от х к z. Справедливо и обратное утверждение.

Кроме отношения «длиннее» на множестве отрезков свойством транзитивности обладает отношение равенства: если отрезок х равен отрезку у и отрезок у равен отрезку z, то отрезок х равен отрезку z, Это свойство отражено и на графе отношения равенства (рис. 99)

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

Рассмотрим еще одно свойство отношений, которое называют свойством связанности, а отношение, обладающее им, называют связанным.

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

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

R связано на множестве X ↔ (х ≠ у => хRу v уRх).

опр.

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

На графе связанного отношения любые две вершины соединены стрелкой. Справедливо и обратное утверждение.

Существуют отношения, которые свойством связанности не обладают. Таким отношением, например, является отношение делимости на множестве натуральных чисел: можно назвать такие числа х и у, что ни число х не является делителем числа у, ни число у не является делителем числа х.

Выделенные свойства позволяют анализировать различные отношения с общих позиций — наличия (или отсутствия) у них тех или иных свойств.

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

Задача 1. Сформулировать свойства отношения R, заданного при помощи графа (рис. 101).

Решение. Отношение R-антисимметрично, так как вершины графа соединяются только одной стрелкой.

Отношение R — транзитивно, так как с парой стрелок, идущих от b к а и от а к с, на графе есть стрелка, идущая от b к с.

Отношение R — связанно, так как любые две вершины соединены стрелкой.

Отношение R свойством рефлексивности не обладает, так как на графе есть вершины, в которых петли нет.

Задача 2. Сформулировать свойства отношения «больше в 2 раза», заданного на множестве натуральных чисел.

Решение. «Больше в 2 раза» — это краткая форма отношения «число х больше числа у в 2 раза». Это отношение антисимметрично, так как выполняется условие: из того, что число х больше числа у в 2 раза, следует, что число y не больше числа x 2 раза.

Данное отношение не обладает свойством рефлексивности, потому что ни про одно число нельзя сказать, что оно больше самого себя в 2 раза.

Заданное отношение не транзитивно, так как из того, что число x больше числа у на 2, а число у больше числа z на 2, следует, что число х не может быть больше числа z на 2.

Это отношение на множестве натуральных чисел свойством связанности не обладает, так как существуют пары таких чисел х и у, что ни число х не больше числа у в два раза, ни число у не больше х в 2 раза. Например, это числа 7 и 3, 5 и 8 и др.

Упражнения

1.Докажите, что отношение R, заданное при помощи графа (рис.102), рефлексивно, антисимметрично и транзитивно.

2.Докажите, что отношение Т, заданное при помощи графа (рис.103), симметрично и транзитивно.

3.Сформулируйте условия, при которых отношение свойством рефлексивности не обладает, и докажите, что отношение Т (см. упр. 2) не рефлексивно.

4. Сформулируйте условия, при которых отношение не обладает свойством: а) симметричности; б) антисимметричности; в)транзитивности; г) связанности.

5. Докажите, что отношение Р, граф которого изображен на рисунке 104, не обладает ни свойством симметричности, ни свойством антисимметричности, ни свойством транзитивности.

6.Какими свойствами обладает отношение, граф которого изображен на рисунке 105? Является ли оно рефлексивным? Транзитивным?

7.Какие из следующих утверждений истинны:

а) Отношение «x больше у на 3» антисимметрично на множестве N, так как из того, что х больше у на 3, не следует, что у больше х на 3.

б) Отношение «x больше у на 3» антисимметрично, так как из того, что х больше у на 3, следует, что у не больше х на 3.

в) Отношение «х больше у на 3» антисимметрично, так как из того, что х больше у на 3, следует, что у меньше х на 3.

8. На множестве отрезков задано отношение «короче». Верно ли, что оно антисимметрично
и транзитивно? Рефлексивно ли оно?

9. Какими свойствами обладают следующие отношения, заданные на множестве натуральных чисел:

а) «меньше»; б) «меньше на 2»; в) «меньше в 2 раза»?

10. На множестве X =<а, b, с>задано отношение R = <(а, b), (а, а), (b,b), (с, с), (b, а), (b, с), (с, b)>.Какими свойствами оно обладает?

11. На множестве Х= заданы отношения «больше» и «кратно». В чём их сходство и различие?

12.Установите, какое отношение рассматривается в задаче; какие приемы анализа задачи можно использовать:

а) Школьники сделали к карнавалу 15 шапочек для мальчиков, адля девочек в 2 раза больше. Сколько всего карнавальных шапочек они сделали?

б) Второклассники вырезали для елки 26 звездочек, это в 2 раза меньше, чем снежинок. Сколько всего звездочек и снежинок вырезали второклассники?

Дата добавления: 2016-05-11 ; просмотров: 8383 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

Содержание

Свойства отношений на множестве
Специальные свойства бинарных отношений
Рефлексивные и иррефлексивные бинарные отношения
Симметричные и антисимметричные бинарные отношения
Транзитивность бинарного отношения
Плотное бинарное отношение
Классы бинарных отношений
Связь между классами бинарных отношений
🔍 Видео

Видео:Отношение эквивалентности, отношение порядкаСкачать

Свойства отношений на множестве

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

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

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

Не обладает свойством рефлексивности и отношение «длиннее» для отрезков, «больше на 2» для натуральных чисел и др.

Отношение R на множестве Х называется антирефлексивным, если для любого элемента из множества Х всегда ложно хRх: .

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

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

Граф симметричного отношения обладает следующей особенностью: вместе с каждой стрелкой, идущей от х к y, граф содержит стрелку, идущую от y к х (рис. 35).

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

Существуют отношения, которые не обладают свойством симметричности.

Действительно, если отрезок х длиннее отрезка у, то отрезок у не может быть длиннее отрезка х. Граф этого отношения обладает особенностью: стрелка, соединяющая вершины, направлена только в одну сторону.

Отношение R называют антисимметричным, если для любых элементов х и y из истинности xRy следует ложность yRx: : xRyyRx.

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

Существуют отношения, которые не обладают ни свойством симметричности, ни свойством антисимметричности.

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

Граф транзитивного отношения с каждой парой стрелок, идущих от х к y и от y к z, содержит стрелку, идущую от х к z.

Свойством транзитивности обладает и отношение «длиннее» на множестве отрезков: если отрезок а длиннее отрезка b, отрезок b длиннее отрезка с, то отрезок а длиннее отрезка с. Отношение «равенства» на множестве отрезков также обладает свойством транзитивности: (а=b, b=с)(а=с).

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

Существует еще одно свойство отношений, которое называется свойством связанности, а отношение, обладающее им, называют связанным.

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

Например, свойством связанности обладает отношение «больше» для натуральных чисел: для любых различных чисел х и y можно утверждать, либо x>y, либо y>x.

На графе связанного отношения любые две вершины соединены стрелкой. Справедливо и обратное утверждение.

Существуют отношения, которые не обладают свойством связанности. Таким отношением, например, является отношение делимости на множестве натуральных чисел: можно назвать такие числа х и y, что ни число х не является делителем числа y, ни число y не является делителем числа х (числа 17 и 11, 3 и 10 и т.д.).

Рассмотрим несколько примеров. На множестве Х= задано отношение «число х кратно числу y». Построим граф данного отношения и сформулируем его свойства.

Про отношение равенства дробей говорят, оно является отношением эквивалентности.

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

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

В рассмотренном выше отношении «равенства дробей», множество Х разбилось на три подмножества: <; ; >, <; >, <>. Эти подмножества не пересекаются, а их объединение совпадает с множеством Х, т.е. имеем разбиение множества на классы.

Итак, если на множестве Х задано отношение эквивалентности, то оно порождает разбиение этого множества на попарно непересекающиеся подмножества – классы эквивалентности.

Так, мы установили, что отношению равенства на множестве
Х= <;; ; ; ; > соответствует разбиение этого множества на классы эквивалентности, каждый из которых состоит из равных между собой дробей.

Принцип разбиения множества на классы при помощи некоторого отношения эквивалентности является важным принципом математики. Почему?

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

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

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

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

Возьмем еще пример: множество учащихся класса можно упорядочить по росту или возрасту. Заметим, что это отношение обладает свойствами антисимметричности и транзитивности. Или всем известен порядок следования букв в алфавите. Его обеспечивает отношение «следует».

Отношение R на множестве Х называется отношением строгого порядка, если оно одновременно обладает свойствами антисимметричности и транзитивности. Например, отношение «х Просмотров 155 000 Комментариев 0

Видео:3.3 Отношение эквивалентности | Роман Попков | ИТМОСкачать

Специальные свойства бинарных отношений

Видео:3.2 Бинарные отношения | Роман Попков | ИТМОСкачать

Рефлексивные и иррефлексивные бинарные отношения

В этой лекции дана определенная классификация бинарных отношений на множестве. В основе этой классификации лежат специальные свойства отношений.

Бинарное отношение на множестве называют рефлексивным, если диагональ множества содержится в , т.е. для любого элемента множества .

Если же , то бинарное отношение на множестве называют иррефлексивным.

Указанные свойства бинарных отношений на множестве называют рефлексивностью и иррефлексивностью.

Бинарные отношения равенства и подобия на множестве геометрических фигур рефлексивны: каждый треугольник равен самому себе и подобен самому себе. На самом деле рефлексивны все отношения равенства: равенство чисел, равенство векторов, равенство множеств и т.п. Также рефлексивными являются, например, бинарное отношение нестрогого неравенства на множестве действительных чисел, поскольку для любого числа всегда , и отношение включения множеств, так как для любого множества всегда .

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

Не следует путать иррефлексивное отношение с нерефлексивным, т.е. не являющимся рефлексивным, отношением. Иррефлексивное отношение нерефлексивно, но не всякое нерефлексивное отношение иррефлексивно. Иррефлексивному отношению на не принадлежит ни один элемент диагонали , а нерефлексивное отношение может содержать некоторые (но не все!) элементы диагонали. На рис. 1.7 приведены примеры графиков иррефлексивного и нерефлексивного отношений (пунктиром указаны диагонали множеств).

Видео:Интуитивная топология | теоретикомнож. вопр. | бинарные отношения | отношение эквивалентности | 1Скачать

Симметричные и антисимметричные бинарные отношения

Бинарное отношение на множестве называют:

Соответствующие свойства бинарных отношений на множестве называют симметричностью и антисимметричностью.

График симметричного бинарного отношения на множестве симметричен относительно диагонали (рис. 1.8).

Теорема 1.1. Бинарное отношение на множестве симметрично, если и только если бинарное отношение на множестве , обратное к , совпадает с .

Пусть , то есть . Тогда, в силу симметричности . Следовательно, . Аналогично доказывается включение .

Теперь пусть . Тогда и . Из определения обратного отношения вытекает, что . Следовательно, — симметричное бинарное отношение.

Теорема 1.2. Бинарное отношение на множестве антисимметрично, если и только если .

Действительно, если , то и (т.е. ). Но из выполнения соотношений и ввиду антисимметричности следует, что , то есть .

Обратно, пусть . Предположим, что и , причем . Тогда и , но . Получаем противоречие.

Отметим, что для антисимметричного бинарного отношения на множестве может иметь место равенство .

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

Бинарное отношение на множестве называют транзитивным, если для любых из того, что и , следует . Соответствующее свойство бинарного отношения называют транзитивностью.

Пример 1.12. а. Пусть — некоторое множество населенных пунктов. Зададим на нем бинарное отношение достижимости: из пункта достижим пункт , если есть дорога, по которой можно доехать из в . Это отношение транзитивно, поскольку если из пункта можно доехать до пункта , а из есть дорога до , то из можно проехать в .

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

в. Бинарное отношение неравенства на множестве действительных чисел не транзитивно, так как из того, что и , вовсе не следует, что . Аналогично, если друг , а друг , то — вопреки известной поговорке — это не означает, что друг .

Видео:3.10 Пример - доказательство равенства двух множествСкачать

Транзитивность бинарного отношения

Докажем следующее важное свойство транзитивного бинарного отношения.

Теорема 1.3. Бинарное отношение на множестве транзитивно тогда и только тогда, когда его квадрат содержится в нем, т.е. .

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

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

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

Видео:Проверяем свойства отношенийСкачать

Плотное бинарное отношение

Бинарное отношение на множестве называется плотным, если для любых , отличных друг от друга и таких, что , найдется , отличный и от и от , такой, что и .

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

Если — плотное бинарное отношение на множестве и для некоторых имеет место , то найдется , такой, что и . Отсюда в силу определения композиции отношений следует, что . Значит, из следует , то есть .

Итак, если плотно, то оно содержится в своем квадрате. Напомним, что для транзитивного бинарного отношения . Следовательно, если бинарное отношение одновременно плотно и транзитивно, то .

Видео:9 класс, 2 урок, Множества и операции над нимиСкачать

Классы бинарных отношений

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

Бинарное отношение на некотором множестве называют:

Определенные выше бинарные отношения называют отношениями эквивалентности, толерантности, порядка (частичного порядка), предпорядка (квазипорядка), строгого порядка, строгого предпорядка.

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

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

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

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

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

Если распространить это отношение на множество целых чисел, то оно будет уже только предпорядком, поскольку теряется свойство антисимметричности. Например, 2 делится на –2 и –2 делится на 2, однако .

д. Рассмотрим множество всех подмножеств множества . Покажем, что отношение включения на множестве есть порядок. Это отношение рефлексивно, так как для любого множества справедливо включение . Поскольку для любых двух множеств и из и следует, что , рассматриваемое отношение антисимметрично. Из определения включения вытекает, что если и , то . Следовательно, отношение транзитивно.

е. Отношение строгого неравенства на числовом множестве, равно как и отношение строгого включения множеств, есть отношение строгого порядка.

ж. В качестве примера отношения строгого предпорядка можно привести отношение «строгой достижимости» на некотором множестве населенных пунктов: пункт считаем строго достижимым из отличного от него пункта , если есть дорога (автомобильная, железная и т.п.) из в , причем принимается, что никакой пункт не является строго достижимым из себя самого.

Видео:8 класс, 21 урок, Отношение площадей подобных треугольниковСкачать

Связь между классами бинарных отношений

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

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

Отношение называют рефлексивно-транзитивным замыканием бинарного отношения на соответствующем множестве.

Можно также обозначить 1″ png;base64,iVBORw0KGgoAAAANSUhEUgAAAVQAAAAYBAMAAABXURglAAAALVBMVEVHcEwAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACttl6nAAAADnRSTlMARIEBwBDpaSGhMdCRsStr4IkAAARmSURBVFjD1Zfva1NXGMefm5M0N5FbUu3adbhLLM5Xo9yYLJEN5dJmbnlhuFZsoYPSH1YmlRCnVgUJd2MTX2xlL2TTNyEbTNzGirMWdRMJzHYrMokgQxDExFVprfdv2Lnn5v7MSXsv9M0uJDn3nOec53PO+T7POQH4vz2D2zyZs5ENJ/jOreFvnBfnwW+iG026OObSMCbGrnoZ2L/hqNDr0s4nMk/XNBjyijp48Jib7ZE7JY+onMisOKquqJJM/1F/S3tFXbzdnl/f77ajnRV3qKzhWmSq9qbwcwEgMNWnvTH/Ct5Qw5srnAuRHJsIihCPx4X1UAev6aWQyCw5ZjFJkOqoA889oqJEvqXkQniVUJnpxs86qP7rNUMzIjPiaBWsqN2KR1RolTtYF+GZb/mpuQD+NJ0yBio74vuaOpSGyl71jNoBb3c2azPHai119DdH7b8hOVDZ7RfhzN+S3eyrtABf7mvXULlI1txN5kKUuZuRG4L5oRlGP/ZKZ+HNhumwdy+qPyd6NV+fZUo/w+fzWtvW9F+62S+P+veV6gqV7KiXI1N6zadt6vM6Lu3PCbGxd4oaajtkzRPi3hcZvUis215Ti4FLB40kHry5WwQkWEZ8Q1vpyA7saNPJwfdJ5I0GJ6gyn5t8sHu8PtJt2YrKjsKMviCbVYl3q4dsPCsMVCAhks43Lai+CejRd/ATYv4WWfg+2KtXT8k+I/V9b4wI4Srw2NGpOGxVX8/ld72gJo/yYcmnB3nqlmxB5caBp0gvK+DaBFnV1IO2omExHIX7dW5kETAfwT3q1UfA50h9cSLwWeLoQ0DvqZb/CGasWB/mSg24Z8Y5mpFM1OEyFKioPTrqQDqdMywKJbgjNZoXBaQntGAVuBUKw3QUevCq4t1XUQOrEKzRj7AqJCsmqmyiFiLwpNQgAIyKJ5CYVYvfAvQYqHuFwEtdVRYBHILYsp6klyA53igAhB3dkQGdAuhSGZpMCPd/hvi8nbSOWpRY3YklrDDqTBkS6s2AwUvLi/i8JnivLLtrhlW4BqGPQYue5CwU8vYRScMTgV3FP4njsTltQtMVB+Rprb8Ixf1lm1Q1VJSTuTlKHGaF0ATisbxRRx4Q3wc8iVfmJVymyCW1jFcirJCBp0cCR2iRnZM/Io6231IFlFyBxw4h6f2jcN1PSikjWcXUSbKvrh2laI9XqrCweE+Jwh6lBq2KEj03ShLAauZX2n1n+dIosIdJvBUuLNBuKmHdkRaNww93zDvzbo7050uw8AE5AsZ0ML+i4EMoWH1Xoq0BDlq0JXxALQn4EwdEJOwfHxIo5knxPP7eSVwVD2yhSTBVjVl6Ij7yQ4MJ6Y92YWjJcbAK6o0mtOT28kuywZ4KtW2aiIJTPaBJaBItttf7lAXyS2sCbHJ7/Q8Spc/Qb6EFsp5dZBtX6f1bRNvr7xSTrnWuQG7/e4SkelqlPQvkm4iPoacgGLZPkjah+bUJGE//gNAQvf68WQyUXDny/p/3PxhfD/CoDVFLAAAAAElFTkSuQmCC» style=»vertical-align: middle;» />, и тогда .

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

такие, что для каждого и для каждого .

В итоге получаем последовательность

для всякого , для всякого , такую, что для любого , то есть , что и требовалось доказать.