Лекция 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. Бинарное отношение на множестве X называется рефлексивным, если для любого элемента aX выполняется условие a:
- (aX) a* a.
Если отношение представлено с помощью графа, то рефлексивность этого отношения означает, что в каждой вершине графа обязательно имеется петля.
Для отношения, заданного с помощью булевой матрицы его рефлексивность равносильна тому, что по главной диагонали этой матрицы (идущей из ее левого верхнего угла в правый нижний) стоят только символы 1.
2. Бинарное отношение на X называется антирефлексивным, если ни для одного aX не выполняется условие a * a:
Обозначим через I x отношение на множестве X, состоящее из пар вида (a, a), где a X:
I x = {(a, a)| a X}.
Отношение Ix обычно называют диагональю множества X или отношением тождества на X.
Очевидно, что отношение на множестве X рефлексивно, если диагональ I x является подмножеством множества:
Отношение антирефлексивно, если диагональ I x и отношение б не имеют ни одного общего элемента:
- 3. Бинарное отношение на множестве X называется симметричным, если из a * b следует b * a:
- (a, bX)(a* b b*a).
Примерами симметричных отношений являются:
отношение перпендикулярности на множестве прямых;
отношение касания на множестве окружностей;
отношение "быть похожим" на множестве людей;
отношение "иметь одинаковый пол" на множестве животных.
Отношение "x брат y" на множестве всех людей не является симметричным. В то же время отношение "x брат y" на множестве мужчин симметричным является.
В графе симметричного отношения для каждой дуги из вершины x в вершину y имеется дуга из y в x. Поэтому симметричные отношения можно представлять графами с неориентированными ребрами. При этом каждая пара ориентированных ребер xy и yx заменяется одним неориентированным ребром.
На рисунке 8 представлено отношение
б= {(a, b), (b, a), (b, c), (c, b), (d, c)}
с помощью ориентированного и неориентированного графов.
Рис. 8.
Матрица симметричного отношения симметрична относительно главной диагонали.
Теорема: Объединение и пересечение любого семейства симметричных отношений снова являются симметричными отношениями.
Определение. Бинарное отношение на множестве X называется антисимметричным, если для любых различных элементов a и b условия a * b и b * a не выполняются одновременно:
(a, bX) (a * b & b* a a = b).
Например, отношение "делится" на множестве натуральных чисел является антисимметричным, так как из a b и b a следует, что a = b. Однако на множестве целых чисел отношение "делится" антисимметричным не является, так как (-2) 2 и 2 (-2), но -22.
Отношения "выше", "тяжелее", "старше" антисимметричны на множестве людей. Отношение "быть сестрой" на множестве всех людей антисимметричным не является.
В графе антисимметричного отношения две различные вершины могут быть соединены не более чем одной дугой.
Определение 3.5. Бинарное отношение a на множестве X называется транзитивным, если для любых трех элементов a, b, c X из a*b и b*c следует a*c:
(a, b, c X) (a* b & b* c a*c).
Примерами транзитивных отношений служат:
отношение "делится" на множестве действительных чисел;
отношение "больше" на множестве действительных чисел;
отношение "старше" на множестве людей игрушек;
отношение "иметь одинаковый цвет" на множестве детских игрушек;
д) отношение "быть потомком" на множестве людей.
Феодальное отношение "быть вассалом" не является транзитивным. Это в частности подчеркивается в некоторых учебниках истории: "вассал моего вассала не мой вассал".
Отношение "быть похожим" на множестве людей не обладает свойством транзитивности.
Для произвольного отношения можно найти минимальное транзитивное отношение такое, что аb. Таким отношением является транзитивное замыкание отношения.
Пример 3.1. Транзитивным замыканием бинарного отношения на множестве людей "быть ребенком" является отношение "быть потомком".
Справедлива теорема.
Теорема 3.2. Для любого отношения транзитивное замыкание равно пересечению всех транзитивных отношений, включающих в качестве подмножества.
Определение 3.6. Бинарное отношение на множестве X называется связным, если для любых двух различных элементов a и b имеет место a*b, либо b*a:
(a, b, c X)(ab a*b b*a).
Примером связного отношения является отношение "больше" на множестве действительных чисел. Отношение "делится" на множестве целых чисел связным не является.
4. Инвариантность отношений
В этом параграфе мы перечислим некоторые случаи, когда те или иные свойства отношений сохраняются при выполнении над ними операций .
Теорема 4.4. Чтобы произведение симметричных отношений было симметрично, необходимо и достаточно, чтобы отношения и коммутировали.
Отношение эквивалентности
Важным видом бинарного отношения является отношение эквивалентности.
Определение 1. Бинарное отношение на множестве X называется отношением эквивалентности на X, если рефлексивно, симметрично и транзитивно.
Отношение эквивалентности часто обозначают символами ~,.
Примерами отношения эквивалентности служат:
отношение тождества I X = {(a, a)|aX} на непустом множестве X;
отношение параллельности на множестве прямых плоскости;
отношение подобия на множестве фигур плоскости;
отношение равносильности на множестве уравнений;
отношение "иметь одинаковые остатки при делении на фиксированное натуральное число m" на множестве целых чисел. Это отношение в математике называют отношением сравнимости по модулю m и обозначают ab (mod m);
отношение "принадлежать одному виду" на множестве животных;
отношение "быть родственниками" на множестве людей;
отношение "быть одного роста" на множестве людей;
отношение "жить в одном доме" на множестве людей.
Отношения "жить на одной улице", "быть похожими" на множестве людей отношениями эквивалентности не являются, так как не обладают свойством транзитивности.
Из перечисленных выше свойств бинарных отношений следует, что пересечение отношений эквивалентности является отношением эквивалентности.
Классы эквивалентности
С отношением эквивалентности тесно связано разбиение множества на классы.
Определение 1. Система непустых подмножеств
{M 1 , M 2 , …}
множества M называется разбиением этого множества, если
Сами множества M 1 , M 2 , … называются при этом классами данного разбиения.
Примерами разбиений служат:
разложение всех многоугольников на группы по числу вершин - треугольники, четырехугольники, пятиугольники и т. д.;
разбиение всех треугольников по свойствам углов (остроугольные, прямоугольные, тупоугольные);
разбиение всех треугольников по свойствам сторон (разносторонние, равнобедренные, равносторонние);
разбиение всех треугольников на классы подобных треугольников;
разбиение множества всех учащихся данной школы по классам.
Широкое применение отношений эквивалентности в современной науке связано с тем, что всякое отношение эквивалентности осуществляет разбиение множества, в котором оно определено, на классы, обычно принимаемые за новые объекты. Другими словами с помощью отношений эквивалентности порождаются новые объекты, понятия.
Так, например, отношение сонаправленности лучей разбивает множество всех лучей плоскости или пространства на классы сонаправленных лучей. Каждый из этих классов лучей называется направлением. Таким образом, интуитивное понятие направления получает точное математическое описание как класс разбиения множества лучей с помощью отношения эквивалентности.
О подобных фигурах обычно говорят, что они имеют одинаковую форму. Но что такое форма геометрической фигуры? Интуитивно ясно, что это то общее, что объединяет подобные фигуры. С помощью отношения эквивалентности удается это интуитивное понятие перевести в точное математическое. Отношение подобия, являясь отношением эквивалентности, разбивает множество фигур на классы подобных фигур. Каждый такой класс можно назвать формой. Тогда выражение "две одинаковые фигуры имеют одинаковую форму" имеет следующий точный смысл "две подобные фигуры принадлежат одной форме".
Отношения эквивалентности встречаются всюду, где осуществляются разбиения множеств на классы. Мы часто пользуемся ими, не замечая этого.
Приведем элементарный пример. Когда дети играют со множеством разноцветных игрушек (например, с блоками Дьенеша) и решают задачу разложить игрушки по цветам, то они пользуются отношением "иметь один цвет". Полученные в результате классы одноцветных фигур воспринимаются детьми как новые понятия: красные, желтые, синие и т. д.
Аналогично в результате решения задачи разложения блоков по форме дети получают классы, каждый из которых воспринимается как форма: прямоугольные, круглые, треугольные и т. д.
Связи между отношениями эквивалентности, определенными на множестве M, и разбиениями множества M на классы описываются в следующих двух теоремах.
Теорема 1 Всякое разбиение непустого множества M на классы определяет (индуцирует) на этом множестве отношение эквивалентности такое, что:
всякие два элемента одного класса находятся в отношении;
всякие два элемента различных классов не находятся в отношении. Доказательство. Пусть имеется некоторое разбиение непустого множества M. Определим бинарное отношение следующим образом: xay(K)(xK&yK).
То есть два элемента x и y aиз множества M связаны отношением в том и только в том случае, если в разбиении найдется такой класс K, которому одновременно принадлежат элементы x и y.
Так определенное отношение, очевидно, рефлексивно и симметрично. Докажем транзитивность отношения. Пусть x*y и x*z. Тогда по определению в существуют классы K 1 и K 2 такие, что x, yK 1 и y, zK 2 . Так как различные классы в разбиении не имеют общих элементов, то K 1 = K 2 , то есть x, z K 1 . Поэтому x*z, что и требовалось доказать.
Теорема 2. Всякое отношение эквивалентности в непустом множестве M порождает разбиение этого множества на классы эквивалентности такое, что всякие два элемента одного класса находятся в отношении;
всякие два элемента различных классов не находятся в отношении.
Доказательство. Пусть б - некоторое отношение эквивалентности на множестве M. Каждому элементу x из поставим в соответствие подмножество [x] множества M, состоящее из всех элементов y, находящихся в отношении с элементом x:
Система подмножеств [x], образует разбиение множества M. Действительно, во-первых, каждое подмножество [x]O, так как в силу рефлексивности отношения x[x].
Во-вторых, два различных подмножества [x] и [y] не имеют общих элементов. Рассуждая от противного, допустим существование элемента z такого, что z[x] и z[y]. Тогда zax и zay. Поэтому для любого элемента a[x] из a* x, z*x и z*y в силу симметричности и транзитивности отношения вытекает a*y, то есть a[y]. Следовательно, [x] [y]. Аналогично получаем, что [y][x]. Полученные два включения влекут равенство [x] = [y], противоречащее предположению о несовпадении подмножеств [x] и [y]. Таким образом, [x]y] = O.
В-третьих, объединение всех подмножеств [x] совпадает со множеством M, ибо для любого элемента xM выполняется условие x[x].
Итак, система подмножеств [x], образует разбиение множества M. Несложно показать, что построенное разбиение удовлетворяет условиям теоремы. Разбиение множества M, обладающее свойствами, указанными в теореме, называется фактор-множеством множества M по отношению и обозначается M/б.
Свойства отношений:
1) рефлексивность;
2)симметричность;
3)транзитивность.
4)связанность.
Отношение 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 и yRz xRz.
Граф транзитивного отношения с каждой парой стрелок, идущих от х к 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 и т.д.).
Рассмотрим несколько примеров. На множестве Х={1, 2, 4, 8, 12} задано отношение «число х кратно числу 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 на множестве Х называется отношением строгого порядка , если оно одновременно обладает свойствами антисимметричности и транзитивности. Например, отношение «х< y ».
Если же отношение обладает свойствами рефлексивности, антисимметричности и транзитивности, то такое оно будет являться отношением нестрогого порядка . Например, отношение «х y ».
Примерами отношения порядка могут служить: отношение «меньше» на множестве натуральных чисел, отношение «короче» на множестве отрезков. Если отношение порядка обладает еще и свойством связанности, то говорят, что оно является отношением линейного порядка . Например, отношение «меньше» на множестве натуральных чисел.
Множество Х называется упорядоченным, если на нем задано отношение порядка.
Например, множество Х= {2, 8, 12, 32 } можно упорядочить при помощи отношения «меньше» (рис. 41), а можно это сделать при помощи отношения «кратно» (рис. 42). Но, являясь отношением порядка, отношения «меньше» и «кратно» упорядочивают множество натуральных чисел по-разному. Отношение «меньше» позволяет сравнивать два любых числа из множества Х , а отношение «кратно» таким свойством не обладает. Так, пара чисел 8 и 12 отношением «кратно» не связана: нельзя сказать, что 8 кратно 12 либо 12 кратно 8.
Не следует думать, что все отношения делятся на отношения эквивалентности и отношения порядка. Существует огромное число отношений, не являющихся ни отношениями эквивалентности, ни отношениями порядка.
Лекция 3.
п.3. Отношения на множествах. Свойства бинарных отношений.
3.1. Бинарные отношения .
Когда говорят о родстве двух людей, например, Сергей и Анна, то подразумевают, что есть некая семья, к членам которой они относятся. Упорядоченная пара (Сергей, Анна) отличается от других упорядоченных пар людей тем, что между Сергеем и Анной есть некое родство (кузина, отец и т. д.).
В математике среди всех упорядоченных пар прямого произведения двух множеств A и B (A ´B ) тоже выделяются «особые» пары в связи с тем, что между их компонентами есть некоторые «родственные» отношения, которых нет у других. В качестве примера рассмотрим множество S студентов какого-нибудь университета и множество K читаемых там курсов. В прямом произведении S ´K можно выделить большое подмножество упорядоченных пар (s , k ), обладающих свойством: студент s слушает курс k . Построенное подмножество отражает отношение «… слушает …», естественно возникающее между множествами студентов и курсов.
Для строгого математического описания любых связей между элементами двух множеств введем понятие бинарного отношения.
Определение 3.1. Бинарным (или двухместным ) отношением r между множествами A и B называется произвольное подмножество A ´B , т. е.
В частности, если A= B (то есть rÍA 2), то говорят, что r есть отношение на множестве A.
Элементы a и b называются компонентами (или координатами ) отношения r.
Замечание. Договоримся, что для обозначения отношений между элементами множеств использовать греческий алфавит : r, t, j, s, w и т. д.
Определение 3.2. Областью определения D r={a | $ b , что a rb } (левая часть). Областью значений бинарного отношения r называется множество R r={b | $ a , что a rb } (правая часть).
Пример 3. 1. Пусть даны два множества A ={1; 3; 5; 7} и B ={2; 4; 6}. Отношение зададим следующим образом t={(x ; y )ÎA ´B | x+ y =9}. Это отношение будет состоять из следующих пар (3; 6), (5; 4) и (7; 2), которые можно записать в виде t={(3; 6), (5; 4), (7;2)}. В данном примере D t={3; 5; 7} и R t= B ={2; 4; 6}.
Пример 3. 2. Отношение равенства на множестве действительных чисел есть множество r={(x ; y ) | x и y – действительные числа и x равно y }. Для этого отношения существует специальное обозначение «=». Область определения совпадает с областью значений и является множеством действительных чисел, D r= R r.
Пример 3. 3. Пусть A – множество товаров в магазине, а B – множество действительных чисел. Тогда j={(x ; y )ÎA ´B | y – цена x } – отношение множеств A и B .
Если обратить внимание на пример 3.1., то можно заметить, что данное отношение было задано сначала в виде t={(x ; y )ÎA ´B | x+ y =9}, а потом записано в виде t={(3; 6), (5;4), (7;2)}. Это говорит о том, что отношения на множествах (или одном множестве) можно задавать различными способами. Рассмотрим способы задания бинарных отношений.
Способы задания отношений:
1) с помощью подходящего предиката;
2) множество упорядоченных пар;
3) в графической форме: пусть A и B – два конечных множества и r – бинарное отношение между ними. Элементы этих множеств изображаем точками на плоскости. Для каждой упорядоченной пары отношения r рисуют стрелку, соединяющую точки, представляющие компоненты пары. Такой объект называется ориентированным графом или орграфом , точки же, изображающие элементы множеств, принято называть вершинами графа .
4) в виде матрицы: пусть A ={a 1, a 2, …, an } и B ={b 1, b 2, …, bm }, r – отношение на A ´B . Матричным представлением r называется матрица M =[mij ] размера n ´m , определенная соотношениями
.
Кстати, матричное представление является представлением отношения в компьютере.
Пример 3. 4. Пусть даны два множества A ={1; 3; 5; 7}и B ={2; 4; 6}. Отношение задано следующим образом t={(x ; y ) | x+ y =9}. Задать данное отношение как множество упорядоченных пар, орграфом, в виде матрицы.
Решение. 1) t={(3; 6), (5; 4), (7; 2)} - есть задание отношения как множества упорядоченных пар;
2) соответствующий ориентированный граф показан на рисунке.
https://pandia.ru/text/78/250/images/image004_92.gif" width="125" height="117">. ,
Пример 3. 5 . Еще в качестве примера можно рассмотреть предложенную Дж. фон Нейманом (1903 – 1957) блок-схему ЭВМ последовательного действия, которая состоит из множества устройств M :
,
где a – устройство ввода, b – арифметическое устройство (процессор), c – устройство управления, d – запоминающее устройство, e – устройство вывода.
Рассмотрим информационный обмен между устройствами mi и mj , которые находятся в отношении r, если из устройства mi поступает информация в устройство mj .
Это бинарное отношение можно задать перечислением всех его 14 упорядоченных пар элементов:
Соответствующий орграф, задающий это бинарное отношение, представлен на рисунке:
Матричное представление этого бинарного отношения имеет вид:
. ,
Для бинарных отношений обычным образом определены теоретико-множественные операции: объединение, пересечение и т. д.
Введем обобщенное понятие отношения.
Определение 3.3. n-местное (n -арное ) отношение r – это подмножество прямого произведения n множеств, то есть множество упорядоченных наборов (кортежей )
rÍA 1´…´An ={(a 1, …, an )| a 1ÎA 1Ù … Ùan ÎAn }
Многоместные отношения удобно задавать с помощью реляционных таблиц . Такое задание соответствует перечислению множества n -к отношения r. Реляционные таблицы широко используются в компьютерной практике в реляционных базах данных . Заметим, что реляционные таблицы нашли применение в повседневной практике. Всевозможные производственные, финансовые, научные и другие отчеты часто имеют форму реляционных таблиц.
Слово «реляционная » происходит от латинского слова relation , которое в переводе на русский язык означает «отношение». Поэтому в литературе для обозначения отношения используют букву R (латинскую) или r (греческую).
Определение 3.4. Пусть rÍA ´B есть отношение на A ´B. Тогда отношение r-1 называется обратным отношением к данному отношению r на A ´B , которое определяется следующим образом:
r-1={(b , a ) | (a , b )Îr}.
Определение 3.5. Пусть r ÍA ´B есть отношение на A ´B, а s ÍB ´C – отношение на B ´C. Композицией отношений s и r называется отношение t ÍA ´C ,которое определяется следующим образом:
t=s◦r= {(a , c )| $ b Î B, что (a , b )Îr и (b , c )Îs}.
Пример 3. 6 . Пусть , и C ={, !, d, à}. И пусть отношение r на A ´B и отношение s на B ´C заданы в виде:
r={(1, x ), (1, y ), (3, x )};
s={(x ,), (x , !), (y , d), (y , à)}.
Найти r-1 и s◦r, r◦s.
Решение. 1) По определению r-1={(x , 1), (y , 1), (x , 3)};
2) Используя определение композиции двух отношений, получаем
s◦r={(1,), (1, !), (1, d), (1, à), (3,), (3, !)},
поскольку из (1, x )Îr и (x ,)Îs следует (1,)Îs◦r;
из (1, x )Îr и (x , !)Îs следует (1, !)Îs◦r;
из (1, y )Îr и (y , d)Îs следует (1, d)Îs◦r;
из (3, x )Îr и (x , !)Îs следует (3, !)Îs◦r.
Теорема 3.1. Для любых бинарных отношений выполняются следующие свойства:
2) 
;
3) 
- ассоциативность композиции.
Доказательство. Свойство 1 очевидно.
Докажем свойство 2. Для доказательства второго свойства покажем, что множества, записанные в левой и правой частях равенства, состоят из одних и тех же элементов. Пусть (a ; b ) Î (s◦r)-1 Û (b ; a ) Î s◦r Û $ c такое, что (b ; c ) Î r и (c ; a ) Î s Û $ c такое, что (c ; b ) Î r-1 и (a ; c ) Î s-1 Û (a ; b ) Î r -1◦s -1.
Свойство 3 доказать самостоятельно.
3.2. Свойства бинарных отношений .
Рассмотрим специальные свойства бинарных отношений на множестве A .
Свойства бинарных отношений.
1. Отношение r на A ´A называется рефлексивным , если (a ,a ) принадлежит r для всех a из A .
2. Отношение r называется антирефлексивным , если из (a ,b )Îr следует a ¹b .
3. Отношение r симметрично , если для a и b , принадлежащих A , из (a ,b )Îr следует, что (b ,a )Îr.
4. Отношение r называется антисимметричным , если для a и b из A , из принадлежности (a ,b ) и (b ,a ) отношению r следует, что a =b .
5. Отношение r транзитивно , если для a , b и c из A из того, что (a ,b )Îr и (b ,c )Îr, следует, что (a ,c )Îr.
Пример 3. 7. Пусть A ={1; 2; 3; 4; 5; 6}. На этом множестве задано отношение rÍA 2, которое имеет вид: r={(1, 1), (2, 2), (3, 3), (4; 4), (5; 5), (6; 6), (1; 2), (1; 4), (2; 1), (2;4), (3;5), (5; 3), (4; 1), (4; 2)}. Какими свойствами обладает данное отношение?
Решение. 1) Это отношение рефлексивно, так как для каждого a ÎA , (a ; a )Îr.
2) Отношение не является антирефлексивным, так как не выполняется условие этого свойства. Например, (2, 2)Îr, но отсюда не следует, что 2¹2.
3) Рассмотрим все возможные случаи, показав, что отношение r является симметричным:
(a , b )Îr | (b , a ) | (b , a )Îr? |
|
4) Данное отношение не является антисимметричным, поскольку (1, 2)Îr и (2,1)Îr, но отсюда не следует, что 1=2.
5) Можно показать, что отношение r транзитивно, используя метод прямого перебора.
(a , b )Îr | (b , c )Îr | (a , c ) | (a , c )Îr? |
|
Как по матрице представления
определить свойства бинарного отношения
1. Рефлексивность: на главной диагонали стоят все единицы, звездочками обозначены нули или единицы.
.
2. Антирефлексивность: на главной диагонали все нули.
3. Симметричность: если .
4. Антисимметричность: все элементы вне главной диагонали равны нулю; на главной диагонали тоже могут быть нули.
.
Операция «*» выполняется по следующему правилу: 
, где , .
5. Транзитивность: если . Операция «◦» выполняется по обычному правилу умножения, при этом надо учитывать: .
3.3 Отношение эквивалентности. Отношение частичного порядка.
Отношение эквивалентности является формализацией такой ситуации, когда говорят о сходстве (одинаковости) двух элементов множества.
Определение 3.6. Отношение r на A есть отношение эквивалентности , если оно рефлексивно, симметрично и транзитивно. Отношение эквивалентности a rb часто обозначается: a ~ b .
Пример 3. 8 . Отношение равенства на множестве целых чисел есть отношение эквивалентности.
Пример 3. 9 . Отношение «одного роста» есть отношение эквивалентности на множестве людей X .
Пример 3. 1 0 . Пусть ¢ - множество целых чисел. Назовем два числа x и y из ¢ сравнимыми по модулю m (m Î¥) и запишем , если равны остатки этих чисел от деления их на m , т. е. разность (x -y ) делится на m .
Отношение «сравнимых по модулю m целых чисел» есть отношение эквивалентности на множестве целых числе ¢. В самом деле:
это отношение рефлексивно, т. к. для "x ΢ имеем x -x =0, и, следовательно, оно делится на m ;
это отношение симметрично, т. к. если (x -y ) делится на m , то и (y -x ) тоже делится на m ;
это отношение транзитивно, т. к. если (x
-y
) делится на m
, то для некоторого целого t
1 имеем https://pandia.ru/text/78/250/images/image025_23.gif" width="73" height="24 src=">, отсюда 
, т. е. (x
-z
) делится на m
.
Определение 3.7. Отношение r на A есть отношение частичного порядка , если оно рефлексивно, антисимметрично и транзитивно и обозначается символом °.
Частичный порядок важен в тех ситуациях, когда мы хотим как-то охарактеризовать старшинство. Иными словами, решить при каких условиях считать, что один элемент множества превосходит другой.
Пример 3. 11 . Отношение x £y на множестве действительных чисел есть отношение частичного порядка. ,
Пример 3. 1 2 . Во множестве подмножеств некоторого универсального множества U отношение A ÍB есть отношение частичного порядка.
Пример 3. 1 3 . Схема организации подчинения в учреждении есть отношение частичного порядка на множестве должностей.
Прообразом отношения частичного порядка является интуитивное понятие отношения предпочтения (предшествования). Отношение предпочтения выделяет класс задач, которые можно объединить, как задача о проблеме выбора наилучшего объекта .
Формулировка задачи: пусть имеется совокупность объектов A и требуется сравнить их по предпочтительности, т. е. задать отношение предпочтения на множестве A и определить наилучшие объекты.
Отношение предпочтения P , которое можно определить как «aPb , a , b ÎA Û объект a не менее предпочтителен, чем объект b » является по смыслу рефлексивным и антисимметричным (каждый объект не хуже самого себя, и, если объект a не хуже b и b не хуже a , то они одинаковы по предпочтительности). Естественно считать, что отношение P транзитивно (хотя в случае, когда, например, предпочтения обсуждаются группой лиц с противоположными интересами, это свойство может быть нарушено), т. е. P – отношение частичного порядка.
Один из возможных способов решения задачи сравнения объектов по предпочтительности – ранжирование , т. е. упорядочение объектов в соответствии с убыванием их предпочтительности или равноценности. В результате ранжирования мы выделяем «наилучшие» или «наихудшие» с точки зрения отношения предпочтения объекты.
Области применения задачи о проблеме выбора наилучшего объекта: теория принятия решений, прикладная математика, техника, экономика, социология, психология.
Элементы множества, как правило, находятся в каком-либо отношении друг относительно друга. Эти отношения можно задать в виде неполных предложений -- предикатов, например, «меньше, чем...», «больше, чем...», «эквивалентно», «конгруэнтно» и т. п.
Тот факт, что некоторый элемент находится в каком-либо отношении к элементу того же множества x j , математически записывают как XiRxj, где R -- символ отношения.
Отношение из двух элементов множества X называют бинарным. Бинарные отношения множеств X и Y представляют собой некоторое множество упорядоченных пар (х, у), образованных декартовым произведением X х Y. В общем случае можно говорить не только о множестве упорядоченных пар, но и о множестве упорядоченных троек, четверок элементов и т. д., т. е. о парных отношениях, получаемых в результате декартова произведения , где п -- размерность n -строчек.
Рассмотрим основные виды отношений -- отношения эквивалентности, порядка и доминирования.
Некоторые элементы множеств можно считать эквивалентными в том случае, когда любой из этих элементов при определенных условиях можно заменить другим, т. е. данные элементы находятся вот-ношении эквивалентности. Примерами отношений эквивалентности являются отношения параллельности на множестве прямых какой-либо плоскости; подобия на множестве треугольников; принадлежности к одной функциональной группе микросхем или к одному классу типоразмеров и т. д.
Термин «отношение эквивалентности» будем применять при выполнении следующих условий:
1) каждый элемент эквивалентен самому себе;
2) высказывание, что два элемента являются эквивалентными, не требует уточнения того, какой из элементов рассматривается первым, а какой вторым;
3) два элемента, эквивалентные третьему, эквивалентны между собой.
Введем для обозначения эквивалентности символ ~, тогда рассмотренные условия можно записать следующим образом:
1) х ~ х (рефлективность);
2) х ~ уу ~ х (симметричность);
3) х ~ у и у ~ z х ~ z (транзитивность).
Следовательно, отношение R называют отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.
Пусть некоторому элементу х X эквивалентно некоторое подмножество элементов А X, тогда это подмножество образует класс эквивалентности, эквивалентный х. Очевидно, что все элементы одного и того же класса эквивалентности эквивалентны между собой (свойство транзитивности). Тогда всякий элемент хХ может находиться в одном и только одном классе эквивалентности, т. е. в этом случае множество X разбивается на некоторое непересекающееся подмножество классов эквивалентности , где J -- некоторое множество индексов.
Таким образом, каждому отношению эквивалентности на множестве X соответствует некоторое разбиение множества X на классы.
Часто сталкиваются с отношениями, которые определяют некоторый порядок расположения элементов множества. Например, в процессе автоматизированного конструирования требуется вводить множество одних исходных данных раньше или позже, чем множество других. При этом может оказаться, что элементы одного множества больше или меньше элементов другого и т. д. Во всех этих случаях можно расположить элементы множества X или группы элементов в некотором порядке (например, в виде убывающей или возрастающей последовательности), т. е. ввести отношение порядка на множестве X.
Различают отношения строгого порядка, для которых применяют символы и отношения нестрогого порядка, где используют символы. Эти отношения характеризуются следующими свойствами:
для отношения строгого порядка:
х
х<У, а У<х -- взаимоисключаются (несимметричность);
x<у и у
для отношения нестрогого порядка:
х X -- истинно (рефлексивность);
ху и ух х = у -- (антисимметричность);
х у и у z xу z -- (транзитивность).
Множество X называют упорядоченным, если любые два элемента х и у этого множества сравнимы, т. е. если для них выполняется одно из условий: х < у, х = у, у < х.
Упорядоченное множество называют кортежем. В общем случае кортеж -- это последовательность элементов, т. е. совокупность элементов, в которой каждый элемент занимает вполне определенное место. Элементы упорядоченного множества называются компонентами кортежа. Примерами кортежа может служить упорядоченная последовательность чисел арифметической или геометрической прогрессий, последовательность технологических операций при изготовлении какого-либо радиоэлектронного изделия, упорядоченная последовательность установочных позиций печатной платы для закрепления конструктивных элементов.
Во всех этих множествах место каждого элемента вполне определено и не может произвольно изменяться.
При обработке конструкторской информации на ЭВМ часто используют отношения доминирования. Говорят, что хX доминирует над уX, т. е. х>>у, если элемент х в чем-либо превосходит (имеет приоритет) элемент у того же множества. Например, под х можно понимать один из списков данных, который должен поступить на обработку первым. При анализе нескольких конструкций РЭА какой-либо из них должен быть отдан приоритет, так как эта конструкция обладает лучшими, с нашей точки зрения, свойствами, чем другие, т. е. конструкция х доминирует над конструкцией у.
Свойство транзитивности при этом не имеет места. Действительно, если, например, конструкцию х по каким-либо одним параметрам предпочли конструкции у, а конструкцию у по каким-либо другим параметрам предпочли конструкции z, то отсюда еще не следует, что конструкции х должно быть отдано предпочтение по сравнению с конструкцией г.
Отображение множеств. Одним из основных понятий теории множеств является понятие отображения. Если заданы два непустых множества X и Y, то закон, согласно которому каждому элементу xX ставится в соответствие элемента, называют однозначным отображением X в Y или функцией, определенной на X и принимающей значение на Y.
На практике приходится иметь дело и с многозначными отображениями множества X на множестве Y, которые определяют закон, согласно которому каждому элементу хX ставится в соответствие некоторое подмножество , называемое образом элементов. Возможны случаи, когда Гх = 0.
Пусть задано некоторое подмножество АX. Для любого хА образом х является подмножество . Совокупность всех элементов Y, являющихся образами для всех х в А, назовем образом множества А и будем обозначать ГА. В этом случае
Loading...