Какими свойствами обладает отношение
План
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. Он показывает, что данное отношение не обладает ни свойством симметричности, ни свойством антисимметричности.
Рис.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 не больше числа 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. На множестве Х= {2,4,6,8, 12} заданы отношения «больше» и «кратно». В чём их сходство и различие?
12.Установите, какое отношение рассматривается в задаче; какие приемы анализа задачи можно использовать:
а) Школьники сделали к карнавалу 15 шапочек для мальчиков, адля девочек в 2 раза больше. Сколько всего карнавальных шапочек они сделали?
б) Второклассники вырезали для елки 26 звездочек, это в 2 раза меньше, чем снежинок. Сколько всего звездочек и снежинок вырезали второклассники?
Источник
У этого термина существуют и другие значения, см. Отношение.
Отноше́ние — математическая структура, которая формально определяет свойства различных объектов и их взаимосвязи. Распространёнными примерами отношений в математике являются равенство (=), делимость, подобие, параллельность и многие другие.
Понятие отношения как подмножества декартова произведения формализовано в теории множеств и получило широкое распространение в языке математики во всех её ветвях. Теоретико-множественный взгляд на отношение характеризует его с точки зрения объёма — какими комбинациями элементов оно наполнено; содержательный подход рассматривается в математической логике, где отношение — пропозициональная функция, то есть выражение с неопределёнными переменными, подстановка конкретных значений для которых делает его истинным или ложным. Важную роль отношения играют в универсальной алгебре, где базовый объект изучения раздела — множество с произвольным набором операций и отношений. Одно из самых ярких применений техники математических отношений в приложениях — реляционные системы управления базами данных, методологически основанные на формальной алгебре отношений.
Отношения обычно классифицируются по количеству связываемых объектов (арность) и собственным свойствам, таким как симметричность, транзитивность, рефлексивность.
Формальные определения и обозначения[править | править код]
-местным (-арным) отношением , заданным на множествах , называется подмножество декартова произведения этих множеств: . Факт связи -ки элементов отношением обозначается или .
Факт связи объектов и бинарным отношением обычно обозначают с помощью инфиксной записи: . Одноместные (унарные) отношения соответствуют свойствам или атрибутам, как правило, для таких случаев терминология отношений не используется. Иногда используются трёхместные отношения (тернарные), четырёхместные отношения (кватернарные); об отношениях неопределённо высокой арности говорят как о «мультиарных», «многоместных».
Универсальное отношение — это отношение, связывающее все элементы заданных множеств, то есть, совпадающее с декартовым произведением: . Нуль-отношение — отношение, не связывающее никакие элементы, то есть пустое множество: .
Функциональное отношение — отношение, образующее функцию: является функциональным, если из выполнения и следует, что (обеспечивается единственность значения функции).
Общие свойства и виды бинарных отношений[править | править код]
Наиболее распространённые в языке математики отношения — бинарные над одним множеством (), наиболее часто используются обладающие некоторыми общими свойствами[1]:
В зависимости от набора свойств бинарных отношений формируются некоторые широко используемые их виды:
- отношение эквивалентности — всякое рефлексивное, транзитивное и симметричное отношение;
- отношение предпорядка — рефлексивное и транзитивное;
- отношение частичного порядка — рефлексивное, транзитивное и антисимметричное;
- отношение строгого порядка — антирефлексивное, транзитивное, антисимметричное;
- отношение линейного порядка — связное, рефлексивное, антисимметричное.
Важную роль играет отношение равенства — отношение эквивалентности, выполненное только для двух совпадающих элементов.
Могут быть и другие комбинации свойств отношений, например, транзитивно и рефлексивно, но не обладает другими простыми свойствами, отношение делимости на множестве натуральных чисел, обычно обозначаемое символом , оно состоит из пар вида , где делит нацело. Пример тернарного отношения — образование пифагоровой тройки тремя числами, нахождение в отношении пифагоровой четвёрки — пример кватернарного отношения.
Более свободный набор свойств бинарных отношений применяется в теории графов: неориентированный граф может быть определён как множество вершин с симметричным бинарным отношением над ним, а ориентированный граф — как множество вершин с произвольным бинарным отношением над ним.
Алгебры отношений[править | править код]
Все -арные отношения над декартовым произведением образуют булеву алгебру относительно теоретико-множественных операций объединения, пересечения и дополнения.
Реляционная алгебра — замкнутая система операций над отношениями в реляционной модели данных.
Примечания[править | править код]
Литература[править | править код]
- Отношение — статья из Математической энциклопедии. Д. М. Смирнов
- Колмогоров А. Н., Драгалин А. Г. Введение в математическую логику. — М.: Издательство Московского университета, 1982. — 120 с. — 29 500 экз.
Источник
Отношение, заданное на множестве, может обладать рядом свойств, а именно:
2. Рефлексивность
Определение. Отношение R намножестве Х называется рефлексивным, если каждый элемент х множества Х находится в отношении R с самим собой.
Используя символы, это отношение можно записать в таком виде:
R рефлексивно на Х Û(“х Î Х) х R х
Пример. Отношение равенства на множестве отрезков рефлексивно, т.к. каждый отрезок равен себе самому.
Граф рефлексивного отношения во всех вершинах имеет петли.
2. Антирефлексивность
Определение. Отношение R намножестве Х называется антирефлексивным, если ни один элемент х множества Х не находится в отношении R с самим собой.
R антирефлексивно на Х Û(“х Î Х)
Пример. Отношение «прямая х перпендикулярна прямой у» на множестве прямых плоскости антирефлексивно, т.к. ни одна прямая плоскости не перпендикулярна самой себе.
Граф антирефлексивного отношения не содержит ни одной петли.
Заметим, что существуют отношения, не являющиеся ни рефлексивными, ни антирефлексивными. Например, рассмотрим отношение «точка х симметрична точке у» на множестве точек плоскости.
· у
l
х
Точка х симметрична точке х – истинно; точка у симметрична точке у – ложно, следовательно, мы не можем утверждать, что все точки плоскости симметричны сами себе, также мы не можем и утверждать, что ни одна точка плоскости не симметрична сама себе.
3. Симметричность
Определение. Отношение R намножестве Х называется симметричным, если из того, что элемент х находится в отношении R с элементом у, следует, что и элемент у находится в отношении R с элементом х.
R симметричнона Х Û(“х, у Î Х) х R у Þ у R х
Пример. Отношение «прямая х пересекает прямую у на множестве прямых плоскости» симметрично, т.к. если прямая х пересекает прямую у, то и прямая у обязательно будет пересекать прямую х.
Граф симметричного отношения вместе с каждой стрелкой из точки х в точку у должен содержать стрелку, соединяющую те же точки, но в обратном направлении.
4. Асимметричность
Определение. Отношение R намножестве Х называется асимметричным, если ни для каких элементов х, у из множества Х не может случиться, что элемент х находится в отношении R с элементом у и элемент у находится в отношении R с элементом х.
R асимметричнона Х Û(“х, у Î Х) х R у Þ
Пример. Отношение «х < у» асимметрично, т.к. ни для какой пары элементов х, у нельзя сказать, что одновременно х < у и у < х.
Граф асимметричного отношения не имеет петель и если две вершины графа соединены стрелкой, то эта стрелка только одна.
5. Антисимметричность
Определение. Отношение R намножестве Х называется антисимметричным, если из того что х находится в отношении с у, а у находится в отношении с х следует, что х = у.
R антисимметричнона Х Û(“х, у Î Х) х R у Ù у R х Þ х = у
Пример. Отношение «х £ у» антисимметрично, т.к. условия х £ у и у £ х одновременно выполняются только тогда, когда х = у.
Граф антисимметричного отношения имеет петли и если две вершины графа соединены стрелкой, то эта стрелка только одна.
6. Транзитивность
Определение. Отношение R намножестве Х называется транзитивным, если для любых элементов х, у, z из множества Х из того, что х находится в отношении с у, а у находится в отношении с z следует, что х находится в отношении с z.
R транзитивнона Х Û(“х, у, z Î Х) х R у Ù у R z Þ х R z
Пример. Отношение «х кратно у» транзитивно, т.к. если первое число кратно второму, а второе кратно третьему, то первое число будет кратно третьему.
Граф транзитивного отношения с каждой парой стрелок от х к у и от у к z содержит стрелку, идущую от х к z.
7. Связность
Определение. Отношение R намножестве Х называется связным, если для любых элементов х, у из множества Х х находится в отношении с у или у находится в отношении с х или х = у.
R связнона Х Û(“х, у, z Î Х) х R у Ú у R z Ú х = у
Другими словами: отношение R намножестве Х называется связным, если для любых различных элементов х, у из множества Х х находится в отношении с у или у находится в отношении с х или х = у.
Пример. Отношение «х < у» связно, т.к. какие бы мы действительные числа не взяли, обязательно одно из них будет больше другого или они равны.
На графе связного отношения все вершины соединены между собой стрелками.
Пример. Проверить, какими свойствами обладает
отношение «х – делитель у», заданное на множестве
Х = {2; 3; 4; 6; 8}.
Построим граф данного отношения:
1) данное отношение рефлексивно, т.к. каждое число из данного множества является делителем самого себя;
2) свойством антирефлексивности данное отношение не обладает;
3) свойство симметричности не выполняется, т.к. например, 2 является делителем числа 4, но 4 делителем числа 2 не является;
4) данное отношение антисимметрично: два числа могут быть одновременно делителями друг друга только в том случае, если эти числа равны;
5) отношение транзитивно, т.к. если одно число является делителем второго, а второе – делителем третьего, то первое число обязательно будет делителем третьего;
6) отношение свойством связности не обладает, т.к. например, числа 2 и 3 на графе стрелкой не соединены, т.к. два различных числа 2 и 3 делителями друг друга не являются.
Таким образом, данное отношение обладает свойствами рефлексивности, асимметричности и транзитивности.
§ 3. Отношение эквивалентности.
Связь отношения эквивалентности с разбиением множества на классы
Определение. Отношение R на множестве Х называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.
Пример. Рассмотрим отношение «х однокурсник у» на множестве студентов педфака. Оно обладает свойствами:
1) рефлексивности, т.к. каждый студент является однокурсником самому себе;
2) симметричности, т.к. если студент х является однокурсником студента у, то и студент у является однокурсником студента х;
3) транзитивности, т.к. если студент х – однокурсник у, а студент у – однокурсник z, то студент х будет однокурсником студента z.
Таким образом, данное отношение обладает свойствами рефлексивности, симметричности и транзитивности, а значит, является отношением эквивалентности. При этом множество студентов педфака можно разбить на подмножества, состоящие из студентов, обучающихся на одном курсе. Получаем 5 подмножеств.
Отношением эквивалентности являются также, например, отношение параллельности прямых, отношение равенства фигур. Каждое такое отношение связано с разбиением множества на классы.
Теорема. Если на множестве Х задано отношение эквивалентности, то оно разбивает это множество на попарно непересекающиеся подмножества (классы эквивалентности).
Верно и обратное утверждение: если какое-либо отношение, заданное на множестве Х, порождает разбиение этого множества на классы, то оно является отношением эквивалентности.
Пример. На множестве Х = {1; 2; 3; 4; 5; 6; 7; 8} задано отношение «иметь один и тот же остаток при делении на 3». Является ли оно отношением эквивалентности?
Построим граф данного отношения:
Данное отношение обладает свойствами рефлексивности, симметричности и транзитивности, следовательно, является отношение эквивалентности и разбивает множество Х на классыэквивалентности. В каждом классе эквивалентности будут числа, которые при делении на 3 дают один и тот же остаток: Х1 = {3; 6}, Х2 = {1; 4; 7}, Х3 = {2; 5; 8}.
Считают, что класс эквивалентности определяется любым своим представителем, т.е. произвольным элементом этого класса. Так, класс равных дробей можно задать, указав любую дробь, принадлежащую этому классу.
В начальном курсе математики также встречаются отношения эквивалентности, например, «выражения х и у имеют одинаковые числовые значения», «фигура х равна фигуре у».
Источник