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. Он показывает, что данное отношение не обладает ни свой­ством симметричности, ни свойством антисимметричности.

Рис.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).

Рис.101

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

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

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

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

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

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

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

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

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

Упражнения

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

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

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

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

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

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

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

а) Отношение «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.На множествеХ= {2,4,6,8, 12} заданы отношения «больше» и «кратно». В чём их сходство и различие?

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

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

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

Лекция 22. Отношения эквивалентности и порядка на множестве

План:

1. Отношение эквивалентности. Связь отношения эквивалентности с разбиением множества на классы.

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

3. Основные выводы