Понятие отношения наряду с понятием множества «пронизывает» всю математику. Интуитивно отношение понимается как связь объектов. Наша задача заключается в том, чтобы, используя сформулированные выше конструкции теории множеств, определить на математическом языке, что же понимается в математике под термином «отношение».

Бинарные отношения на множестве

Пусть дано множество А. Связь элементов хну множества А моделируется парой (ду>). Если элемент х связан с у, значит, мы имеем пару (л:,у) в качестве элемента некоторого множества; если д; не связан с у , значит, пара (л:^) не является объектом множества. Итак, имеем следующее определение.

Бинарным отношением на множестве А называется произвольное множество пар элементов из А.

Другими словами, бинарное отношение на множестве А - ото подмножество прямого произведения АхА=А 2 . В частности, само множество А 2 всех пар является бинарным отношением.

По аналогии с бинарным (или двуместным) отношением можно рассматривать п-местное отношение на множестве как подмножество прямого произведения А". Мы в основном будем рассматривать бинарные отношения, но для краткости речи говорить просто: «отношение на множестве А».

Обозначим произвольное бинарное отношение греческой буквой р.

Если (л",у)е р, то говорят, что л" находится в отношении р с у, и пишут

Если (ду)?Р> то имеем отрицание соответствующего утверждения. В этом случае наряду с записью ~|(хру) (или хру) пишут д-ру, перечеркивая знак отношения.

Пример 8.1.1. Рассмотрим множество А = {1,2,3,4,5}. Множество пар

определяет на А отношение «меньше», обозначаемое знаком <.>

11а этом же множестве можно рассмотреть другое множество пар

оно определяет отношение равенства.

Пример 8.1.2. Рассмотрим множество {N, Z, Q, I, R} основных числовых множеств и множество пар

Имеем отношение, определенное нами в пункте 2.2 как отношение строгого включения множеств. Заметим, что, например, пара (Q. I) нс лежит в указанном множестве, так как Qczl, более того, эти множества не пересекаются.

Пример 8.1.3. Дано множество слов Л={ток, кот, шок, кол, лак}. Рассмотрим такое отношение:

р = {(ток, шок), (шок, ток), (шок, кол), (кол, шок),

(кол, лак), (лак, кол), (кот, кол), (кол, кот)}.

Это отношение можно выразить таким образом: слова множества А находятся в отношении р тогда и только тогда, когда они имеют ровно две одинаковые буквы.

Заметим, что любое множество пар является отношением, неважно, имеется ли для этого отношения хорошее словесное описание.

Так как отношение является множеством, то его можно задать характеристическим свойством, то сеть предикатом Р(ху): р = {(.*,>>) еЛ 2 Р(ху)}. Также используется запись:

Читают: «г находится в отношении с у тогда и только тогда, когда истинно Р(ху)».

Пример 8.1.4. Определим на множестве/! = {1,2,3,4,5} отношение:

Здесь Р(ху) = (л+2=у). Зададим это отношение перечислением пар:

Пример 8.1.5. Зададим на множестве Z (или на множестве N) отношение с помощью предложения: «Существует целое число /?, такое, что х=п у». Символически можно записать:

Имеем уже определенное ранее отношение делимости, обозначаемое знаком:. Этому отношению принадлежат такие пары, как (6,2), (6,3), (4,4), (111, -37) и другие. В отличие от предыдущих примеров это множество пар бесконечно, и перечислить все пары не удастся.

Рассмотрим важнейшие свойства, которыми могут обладать бинарные отношения на множестве.

Отношение р на множестве А называется рефлексивным , если любой элемент х из А находится в отношении р сам с собой, то есть для всех д; из А выполняется лрт:

Пример 8.1.6. Рассмотрим отношение делимости на множестве Z. Возьмем произвольное целое число х. Так как х=х 9 то х‘:х. Значит, любое целое число делится на само себя: V.veZ (л:л). Поэтому отношение делимости рефлексивно.

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

Отношение р на множестве А называется аитирефлексивным , если ни один элемент множества А не находится в отношении р с самим собой:

Пример 8.1.7. R антирефлексивно, так как никакое число не меньше самого себя.

Построим отрицание к предложению «Отношение р рефлексивно»:

Таким образом, отношение р не является рефлексивным тогда и только тогда, когда существует элемент хеА, который не находится в отношении р сам с собой. Отношение, не являющееся рефлексивным, не обязано быть аитирефлексивным.

Пример 8.1.8. Рассмотрим отношение на множестве R, заданное предложением «Число х противоположно числу у». Число х называется противоположным числу у, если сумма х+у равна 0.

Это отношение не рефлексивно. Контрпример: х=1. Так как 1 + 1*0, то число 1 не противоположно 1.

Это отношение нс антирефлексивно. Контрпример: ,v=0. Так как 0+0=0, то число 0 противоположно 0.

Отношение р на множестве А называется симметричным , если из того, что х находится в отношении р с у, следует, что у находится в отношении р с

Пример 8.1.9. Из тождества х+у=у+.х вытекает утверждение: для любых действительных чисел х и у если х противоположно v, то у противоположно х. Значит, данное отношение симметрично. Часто говорят просто: «Числа х и у противоположны».

Отношение «Число х меньше числа у» на множестве R не является симметричным: 3 меньше 4, но 4 не меньше 3.

Отношение р на множестве А называется антисимметричным , если ни для каких различных элементов х и у из А, таких, что хру, не выполняется

урх:

Пример 8.1.10. Отношение «меньше» на множестве R антисимметрично.

Определение антисимметричного отношения можно сформулировать другими способами. Введем обозначения:

Используя таблицу истинности, можно доказать, что формула 1Р л М -равносильна формуле М л К -> Р, которая, в свою очередь, по правилу контрапозиции равносильна 1Р ->~|(Л/ л К). На основании этого можно сказать, что отношение р является антисимметричным тогда и только тогда, когда выполняется одно из равносильных условий:

А) Из того, что хру и урх, следует х=у:

Б) Никакие различные элементы не могут одновременно находиться в отношении р друг с другом.

Пример 8.1.11. Рассмотрим отношение включения на произвольном семействе множеств. Так как ЛсУл Y^X=>X=Y, то включение е есть антисимметричное отношение.

Пример 8.1.12. Отношение делимости на множестве Z не является ни симметричным, ни антисимметричным. Так как 4:2, но 2?4, то отношение не симметрично. Так как 2:(-2) и (-2):2, но (-2)^2, то отношение не является антисимметричным.

Однако на множестве N натуральных чисел имеем антисимметричное отношение: Vjt^eN (х:у лу:х ->х=у). Проверьте это утверждение, пользуясь определением делимости.

Отношение р на множестве А называется транзитивным , если из того, что х находится в отношении р с у, а у находится в отношении р с z, следует, что.V находится в отношении р с z:

Пример 8.1.13. Отношение делимости транзитивно (и на множестве Z и на множестве N): х:у л у: z => x:z. Покажем это. Пусть х:у и y:z. Тогда х=пу и y=kz для некоторых целых чисел п и к. Тогда х = n(kz) = (nk)z = mz, где т есть целое число. Поэтому xz.

Отношение включения множеств также транзитивно: XcY л YcZ => XezZ. Докажите.

Отношение «Числа х и у противоположны» не является транзитивным. Контрпример: х=2,у=-2, 2=2. Тогда числа 2 и (-2) противоположны, а также (-2) и 2 противоположны. Но числа х=2 и z=2 нс являются противоположными.

Пример 8.1.14. Рассмотрим некоторые примеры отношений из предыдущего пункта.

Отношение из примера 8.1.3 антирефлексивно и симметрично. Отношение из примера 8.1.4 антирефлексивно и антисимметрично. Ни одно из этих отношений нс транзитивно. Докажите это, рассмотрев соответствующие контрпримеры.

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

Рефлексивное, антисимметричное и транзитивное отношение называется отношением порядка.

Множество А , на котором задано отношение порядка р, называется упорядоченным множеством . Пишут (А, р).

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

Интуитивно слова «упорядоченное множество» часто понимаются в более узком смысле. Рассмотрим упорядоченную л-ку, составленную из попарно различных элементов. Например, пятерка букв (III,К,О,Л,А) определяет слово ШКОЛА. В этом случае слова «элементы записаны в определенном порядке» понимаются в том смысле, что мы занумеровали их натуральными числами 1, 2, 3, 4, 5 и расположили в порядке возрастания номеров. Обобщим этот пример.

Пусть дано «-элементное множество А. Занумеровав каким-то образом ею элементы а, а 2 >а„, мы действительно получим упорядоченное множество, определив отношение порядка следующим образом:

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

Пример 8.1.15. Дано множество /4={а,б.в,г}. Упорядоченная четверка его различных элементов (б,в,а,г) задаст такое отношение порядка:

{(б,б), (б,в), (б,а), (б,г), (в,в), (в,а), (в,г), (а,а), (а,г), (г,г)}.

Заметим, что порядок не обязан обладать так называемым свойством линейности.

Пример 8.1.16. Рассмотрим на множестве А = {2,4,6,8} отношение делимости:. Задайте это отношение множеством пар. Так как в А лежат только натуральные числа, то: отношение порядка. Имеем упорядоченное множество А, :).

Такой порядок нельзя представить в виде упорядоченной четверки следующих друг за другом элементов. Можно привести графическую иллюстрацию отношения с помощью точек и стрелок: из точки х в точку у ведет стрелка тогда и только тогда, когда х:у.

Рассмотрим числа 6 и 4. Ни одно из них нс делится на другое. Говорят, что это несравнимые элементы.

Пусть на множестве А задано отношение порядка р. Элементы * и у называются сравнимыми , если выполняется хотя бы одно из двух соотношений хру или урх.

Порядок р на множестве А называется линейным , если любые два элемента множества А сравнимы. Множество, на котором определен линейный порядок, называется линейно упорядоченным (или цепью).

Пример 8.1.17. Отношение R является линейным порядком, так как Vx^yeR (х Поэтому (R,

упорядоченное множество.

Отношение делимости натуральных чисел в общем случае не является линейным порядком. Контрпример дан в примере 8.1.16.»

Отмстим, что любой линейный порядок на конечном множестве задается нумерацией его элементов. Чтобы подчеркнуть, что порядок может быть нс линейным, упорядоченное множество в общем случае иногда называют частично упорядоченным.

Чтобы определить общее понятие бинарного отношения на множестве, поступим так же, как и в случае с соответствиями,

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

Вообще бинарные отношения на множестве X определяют следующим способом:

Определение. Бинарным отношением на множестве X называется всякое подмножество декартова произведения X х X.

Так как в дальнейшем мы будем рассматривать только бинарные отношения, то слово «бинарные», как правило, будем опускать.

Условимся отношения обозначать буквами R, S, Т, Р и др.

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

Утверждение о том, что элементы х и у находятся в отношении R, можно записывать так: (х, у) R или x R y. Последняя запись читается: «Элемент х находится в отношении R с элементом у».

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

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

На том же множестве X можно рассмотреть другое отношение - «кратно». Граф этого отношения будет в каждой вершине иметь петлю (стрелку, начало и конец которой совпадают), так как каждое число кратно самому себе (рис. 2).

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

Для отношения R, заданного на множестве X, всегда можно задать отношение R -1 , ему обратное, - оно определяется так же, как соответствие, обратное данному. Например, если R - отношение «х меньше у», то обратным ему будет отношение «у больше х».

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

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

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

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

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

R рефлексивно на Х <=> xRx для любого х X

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

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

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

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

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

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

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

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

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

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

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

R симметрично на X <=> (xRy => yRx)

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

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

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

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

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

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

антисимметрично на X <=> (xRy и х≠у => )

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

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

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

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

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

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

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

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

R транзитивно на X <=> (xRy и yRz => xRz)

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

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

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

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

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

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

R связанно на множестве X <=> (х≠у xRy или yRx)

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

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

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

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

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

отрезков связанными не являются.

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

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

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

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

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

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

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

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

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

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

Пусть задано некоторое непустое множество А и R – некоторое подмножество декартова квадрата множества А: R  A  A .

Отношением R на множестве А называют подмножество множества А  А (или А 2 ). Таким образом отношение есть частный случай соответствия, где область прибытия совпадает с областью отправления. Так же, как и соответствие, отношение – это упорядоченные пары, где оба элемента принадлежат одному и тому же множеству.

R  A  A = {(a, b) | aA, bA, (a, b)R}.

Тот факт, что (a , b )R можно записать так: a R b . Читается: «а находится в отношении R к b » или «между а и b имеет место отношение R». В противном случае записывают: (a , b )R или a R b .

Примером отношений на множестве чисел являются следующие: «=», «», «», «>» и т.д. На множестве сотрудников какой-либо фирмы ‑ отношение «быть начальником» или «быть подчинённым», на множестве родственников – «быть предком», «быть братом», «быть отцом» и т.д.

Рассмотренные отношения носят название бинарных (двухместных) однородных отношений и являются важнейшими в математике. Наряду с ними рассматривают также п -местные или п -арные отношения:

R  A  A … A = A n = {(a 1 , a 2 ,…a n) | a 1 , a 2 ,…a n  A}.

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

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

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

вершины, обозначаемые точками или кружочками, которые соответствуют элементам множества,

и дуги (линии), соответствующие парам элементов, входящих в бинарные отношения, обозначаемые линиями со стрелками, направленными от вершины, соответствующей элементу a к вершине, соответствующей элементу b , если a R b .

Такая фигура называется ориентированным графом (или орграфом) бинарного отношения.

Задача 4.9.1 . Отношение R «быть делителем на множестве M = {1, 2, 3, 4 }» может быть задано матрицей :

перечислением: R = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), ((4,4)};

геометрически (графически) :

1. Выписать упорядоченные пары, принадлежащие следующим бинарным отношениям на множестве А = {1, 2, 3, 4, 5, 6, 7}:

R1 = {(x, y)| x, yA; x + y = 9};

R2 = {(x, y)| x, yA; x < y}.

2. Отношение R на множестве X = {a, b, c, d} задано матрицей

,

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

3. Отношение на множестве А = {1, 2, 3, 4} представлено графом. Необходимо:

перечислить упорядоченные пары, принадлежащие R;

выписать соответствующую матрицу;

определить это отношение с помощью предикатов.

(ответ: a-b= 1).

4.10. Основные типы (свойства) бинарных отношений

Пусть задано бинарное отношение R на множестве А 2 : R  A  A = {(a , b ) | a A, b A, (a , b )R}

Бинарное отношение R на множестве А называется рефлексивным , если для любого a А выполняется a R a , то есть (а , а )R. Главная диагональ матрицы рефлексивного отношения состоит из единиц. Граф рефлексивного отношения обязательно имеет петли у каждой вершины.

Примеры рефлексивных отношений: , =,  на множестве действительных чисел, «не быть начальником» на множестве сотрудников.

Бинарное отношение R на множестве А называется антирефлексивным (иррефлексивным ), если для любого a А не выполняется отношение a R a , то есть (а , а )R. Главная диагональ матрицы иррефлексивного отношения состоит из нулей. Граф иррефлексивного отношения не имеет петель.

Примеры антирефлексивных отношений: <, > на множестве действительных чисел, перпендикулярность прямых на множестве прямых.

Бинарное отношение R на множестве A называется симметричным , если для любых a , b А из a R b следует b R a , то есть если (a , b )R , то и(b , a )R . Матрица симметричного отношения симметрична относительно своей главной диагонали (σ ij = σ ji ). Граф симметричного отношения не является ориентированным (рёбра изображаются без стрелок). Каждая пара вершин здесь соединена неориентированным ребром.

Примеры симметричных отношений:  на множестве действительных чисел, «быть родственником» на множестве людей.

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

анти симметричным , если для любых a , b А из a R b и b R a следует, что a =b . То есть, если (a , b )R и(b , a )R , то отсюда вытекает, что a =b . Матрица антисимметричного отношения вдоль главной диагонали имеет все единицы и не имеет ни одной пары единиц, расположенных на симметричных местах по отношению к главной диагонали. Иными словами, все σ ii =1, и если σ ij =1, то обязательно σ ji =0. Граф антисимметричного отношения имеет петли у каждой вершины, а вершины соединяются только одной направленной дугой.

Примеры антисимметричных отношений: , ,  на множестве действительных чисел; ,  на множествах;

а симметричным , если для любых a , b А из a R b следует невыполнение b R a , то есть если (a , b )R , то (b , a )R . Матрица асимметричного отношения вдоль главной диагонали имеет нули (σ ij =0) все и ни одной симметричной пары единиц (если σ ij =1, то обязательно σ ji =0). Граф асимметричного отношения не имеет петель, а вершины соединены одной направленной дугой.

Примеры асимметричных отношений: <, > на множестве действительных чисел, «быть отцом» на множестве людей.

Бинарное отношение R на множестве A называется транзитив ным , если для любых a , b , с А из a R b и b R a следует, что и a R с . То есть если (a , b )R и(b , с )R вытекает, что (а , с )R . Матрица транзитивного отношения характеризуется тем, что если σ ij =1 и σ jm =1, то обязательно σ im =1. Граф транзитивного отношения таков, что если соединены дугами, например, первая-вторая и вторая-третья вершины, то обязательно есть дуги из первой в третью вершину.

Примеры транзитивных отношений: <, , =, >,  на множестве действительных чисел; «быть начальником» на множестве сотрудников.

Бинарное отношение R на множестве A называется антитранзитив ным , если для любых a , b , с А из a R b и b R a следует, что не выполняется a R с . То есть если (a , b )R и(b , с )R вытекает, что (а , с )R . Матрица антитранзитивного отношения характеризуется тем, что если σ ij =1 и σ jm =1, то обязательно σ im =0. Граф антитранзитивного отношения таков, что если соединены дугами, например, первая-вторая и вторая-третья вершины, то обязательно нет дуги из первой в третью вершину.

Примеры антитранзитивных отношений : «несовпадение чётности» на множестве целых чисел; «быть непосредственным начальником» на множестве сотрудников.

Если отношение не обладает некоторым свойством, то, добавив недостающие пары, можно получить новое отношение с данным свойством. Множество таких недостающих пар называют замыканием отношения по данному свойству. Обозначают его как R * . Так можно получить рефлексивное, симметричное и транзитивное замыкание.

Задача 4.10.1. На множестве А = {1, 2, 3, 4} задано отношение R={(a ,b )| a ,b A, a +b чётное число}. Определить тип данного отношения.

Решение. Матрица данного отношения:

. Очевидно, что отношение является рефлексивным , так как вдоль главной диагонали расположены единицы. Оно симметрично : σ 13 = σ 31 , σ 24 = σ 42 . Транзитивно : (1,3)R, (3,1)R и (1,1)R; (2,4)R, (4,2)R и (2,2)R и т.д.

Задача 4.10.2. Какими свойствами на множестве А = {a , b , c , d } обладает бинарное отношение R = {(a ,b ), (b ,d ), (a ,d ), (b ,a ), (b ,c )}?

Решение . Построим матрицуданного отношения и его граф:

Отношение иррефлексивно , так как все σ ii = 0. Оно не симметрично , так как σ 23 =1, а σ 32 =0, однако σ 12 =σ 21 =1. Отношение не транзитивно , поскольку σ 12 =1, σ 23 =1 и σ 13 =0; σ 12 =1, σ 21 =1 и σ 11 =0; но при этом σ 12 =1, σ 24 =1 и σ 14 =1.

Задача 4.10.3. На множестве А = {1,2,3,4,5} задано отношение R = {(1,2), (2,3), (2,4), (4,5)}. Определить тип отношения и найти следующие замыкания для R:

рефлексивное;

симметричное;

транзитивное.

Решение. Отношение иррефлексивно, поскольку нет ни одного элемента вида (а ,а ). Асимметрично, так как не содержит пар вида (a ,b ) и (b ,a ) и все диагональные элементы равны 0. Антитранзитивно, поскольку (1,2)R, (2,3)R, но (1,3)R. Аналогично (2,4)R, (4,5)R, а (2,5)R и т.д.

рефлексивное замыкание данного отношения R * ={(1,1), (2,2), (3,3), (4,4), (5,5)};

симметричное замыкание: R*={(2,1), (3,2), (4,2), (5,4)};

транзитивное замыкание: R*={(1,3), (1,4), (2,5)}. Рассмотрим граф исходного отношения и полученного транзитивного.

Задачи для самостоятельного решения.

1. Задано отношение R = {(1,1), (1,2), (1,3), (3,1), (2,3)}. Определить его тип и найти замыкания по рефлексивности, симметричности и транзитивности.

2.Отношение на множестве слов русского языка определено следующим образом: а Rb тогда и только тогда, когда они имеют хоть одну общую букву. Определить тип отношения на множестве А = {корова, вагон, нить, топор}.

3. Указать примеры бинарных отношений на множестве А = {1, 2) и В = {1, 2, 3}, которые были бы:

не рефлексивное, не симметричное, не транзитивное;

рефлексивное, не симметричное, не транзитивное;

симметричное, но не рефлексивное и не транзитивное;

транзитивное, но не рефлексивное и не симметричное;

рефлексивное, симметричное, но не транзитивное;

рефлексивное, транзитивное, но не симметричное;

не рефлексивное, симметричное, транзитивное;

рефлексивное, симметричное, транзитивное.

Рассмотрим отношение «уважать», определенное на множестве всех людей %%M%%. Для полной информации о том, кто кого уважает, составим следующее множество %%R%%. Переберем все пары %%(a, b)%%, где %%a, b%% пробегают множество всех людей. Если %%a%% уважает %%b%%, то пару %%(a,b)%% отнесем к множеству %%R%%, иначе — нет.

Этот список полностью отражает отношение «уважать». Если нужно узнать, уважает ли человек %%a%% человека %%b%%, то просмотрим множество %%R%%. Если пара %%(a, b) \in R%%, то заключаем, что %%a%% уважает %%b%%. В случае %%(a,b) \notin R%% — %%a%% не уважает %%b%%.

Определение

Бинарным отношением , определенным на множестве %%M%%, называется произвольное подмножество %%R%% из декартового произведения %%M^2%%.

Пример

Рассмотрим отношение больше на множестве %%M = \{1, 2\}%%. Тогда

$$ M^2 = \big\{(1, 1), (1,2), (2,1), (2,2)\big\} $$ Из него выбирем все пары %%(a,b)%%, где %%a > b%%. Получим $$ R = \big\{(2,1)\big\} $$

Виды бинарных отношений

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

рефлексивным , если для любого элемента %%a%% из %%M%%, выполняется условие %%a~R~a%%. $$ \begin{array}{l} \forall a\in M~~a~R~a \text{ или}\\ \forall a\in M~~(a,a) \in R. \end{array} $$

Примеры

1. Рассмотрим отношение больше больше рефлексивным? Если да, то каждое число является больше самого себя, что неверно. Поэтому отношение больше не рефлексивно.
2. Рассмотрим отношение равно на множестве действительных чисел. Оно является рефлексивным , так как каждое действительное число равно самому себе.

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

Бинарное отношение %%R%% на множестве %%M%% называется симметричным , если для любых двух элементов %%a, b%% из %%M%%, из условия %%a~R~b%% следует условие %%b~R~a%%.

$$ \begin{array}{l} \forall a,b\in M~~a~R~b \rightarrow b~R~a \text{ или}\\ \forall a,b\in M~~(a,b) \in R \rightarrow (b,a) \in R. \end{array} $$

Примеры

1. Рассмотрим отношение больше на множестве действительных чисел. Является ли отношение больше симметричным? Оно не является симметричным, так как если %%a > b%%, то условие %%b > a%% не выполняется. Поэтому отношение больше не симметрично.
2. Пусть %%R%% — отношение, определенное на множестве %%M = \{a,b,c\}%%. При этом %%R = \big\{ (a,b), (b,c), (a,a), (b,a), (c,b)\big\}%%. Для этого отношения имеем %%\forall x,y \in M ~~ (x,y) \in R \rightarrow (y,x) \in R%%. По определению %%R%% симметрично.

Транзитивное бинарное отношение

Бинарное отношение %%R%% на множестве %%M%% называется транзитивным , если для любых элементов %%a, b, c%% из %%M%%, из условий %%a~R~b%% и %%b~R~c%% следует условие %%a~R~c%%.

$$ \begin{array}{l} \forall a,b,c\in M~~a~R~b \land b~R~c \rightarrow a~R~c \text{ или}\\ \forall a,b,c\in M~~(a,b) \in R \land (b,c) \in R \rightarrow (a,c) \in R. \end{array} $$

Пример

Рассмотрим отношение больше на множестве дейтсвительных чисел. Оно является транзитивным , так как для любых элементов выполняется условние %%\forall a,b,c\in M~~a > b \land b > c \rightarrow a > c%%. Так, например, подставив вместо %%a, b%% и %%c%% числа %%2, 1%% и %%0%% соответственно, получим: если %%2 > 1%% и %%1 > 0%%, то %%2 > 0%% — верное утверждение (вспомните импликацию, из истины следует истина).

Антисимметричное бинарное отношение

Бинарное отношение %%R%% на множестве %%M%% называется антисимметричным , если для любых элементов %%a, b%% из %%M%%, из условий %%a~R~b%% и %%b~R~a%% следует условие %%a = b%%.

$$ \begin{array}{l} \forall a,b,c\in M~~a~R~b \land b~R~a \rightarrow a = b \text{ или}\\ \forall a,b\in M~~(a,b) \in R \land (b,a) \in R \rightarrow a = b. \end{array} $$

Пример

Отношение больше или равно на множестве действительных чисел антисимметрично . Действительно, если %%a \geq b%% и %%b \geq a%%, %%a = b%%.

Эквивалентное бинарное отношение

эквивалентности , если оно рефлексивно , симметрично и транзитивно .

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

Отношение частичного порядка

Бинарное отношение %%R%% на множестве %%M%% называется отношением частичного порядка , если оно рефлексивно , антисимметрично и транзитивно .

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

Построение отрицаний

Пусть %%R%% — бинарное отношение на множестве %%M%%, и %%P%% — одно из следующих условий:

• отношение %%R%% рефлексивно,
• отношение %%R%% симметрично,
• отношение %%R%% транзитивно,
• отношение %%R%% антисимметрично.

Построим для каждого из них отрицание выполнения условия %%P%%.

Отрицание рефлексивности

По определению %%R%% рефлексивно, если каждый элемент множества %%M%% находится в отношении %%R%% к самому себе, то есть %%\forall a \in M~~a~R~a%%. Тогда рассмотрим отрицание рефлексивности как истинное высказывание %%\overline{\forall a \in M~~a~R~a}%%. Используем равносильность %%\overline{\forall x P(x)} \equiv \exists x \overline {P(x)}%%. В нашем случае получаем %%\forall a \in M~~a~R~a \equiv \exists a\in M~~a~\not\text{R }~a%%, что и нужно.

Аналогично получаем и остальные отрицания. В итоге получаем следующие утверждения:

%%R%% не рефлексивно тогда и только тогда, когда

$$ \exists a \in M~~a~\not R~a $$

%%R%% не симметрично тогда и только тогда, когда

$$ \exists a, b \in M~~ a~R~b \land b~\not R~a $$

%%R%% не транзитивно тогда и только тогда, когда

$$ \exists a, b, c \in M a~R~b \land b~R~c \land a~\not R~c $$

%%R%% не антисимметрично тогда и только тогда, когда

$$ \exists a, b \in M~~ a~R~b \land b~R~a \land a \neq b. $$

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

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.

Не следует думать, что все отношения делятся на отношения эквивалентности и отношения порядка. Существует огромное число отношений, не являющихся ни отношениями эквивалентности, ни отношениями порядка.