Отношения. Их графы и графики

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

Замечание. Иногда вместо термина «отношение» употребляют термин «бинарное отношение», подчеркивая этим, что речь идет об отношении между двумя элементами множества. При этом, поскольку речь идет об элементах одного и того же множества X, говорят не об отношениях между X и Y, а об отношениях в множестве X.

П р и м е р ы.

1) В множестве натуральных чисел N задано отношение R характеристическим свойством «число х делится на число у», х, у Î N.

2) В множестве геометрических фигур можно задать отношение «фигура х равна фигуре у».

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

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

1. Отношение R ^-1, обратное отношению R в множестве X, само является отношением в том же самом множестве (ведь в этом случае в записи xRy, и х, и у принадлежат X). При этом yR^-1х Û xRy. Например, если в множестве N – натуральных чисел задано отношение «х делится на у», то обратным ему будет отношение «у является делителем х» в том же множестве N.

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

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

3. Если некоторое отношение R в X задано графом, то для получения графа обратного отношения надо повернуть все стрелки в обратную сторону, а чтобы получить граф противоположного отношения надо стереть все имеющиеся стрелки и провести все стрелки, которых не было на рисунке (рис. 5).

Рис. 5

4. На любом множестве X можно рассматривать отношения тождества и различия.

Отношение тождества «х º у» задается множеством пар вида (х, х), х Î Х. Иными словами, х º у в том и только в том случае, когда х совпадает с у. Часто вместо х º у отношение тождества обозначают х = у и называют отношением равенства.

Отношение, противоположное отношению тождества, называют отношением различия и обозначают х ≠ у или х ¹ у. График отношения различия состоит из таких пар (х, у), что х и у различны.

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

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

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

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

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

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

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

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

Рассмотрим снова отношение «фигура х равна фигуре у» в множестве геометрических фигур. Известно, что если «фигура х равна фигуре у», то «фигура у равна фигуре х». Это означает, что если пара (х, у) принадлежит заданному отношению, то и пара (у, х) принадлежит заданному отношению. Такое отношение называется симметричным.

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

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

Если отношение R симметрично, то его граф состоит из двойных стрелок, то есть вместе с каждой стрелкой, идущей от х к у, содержится стрелка, идущая от у к х. При задании симметричного отношения точечным графиком получается множество точек, симметричное относительно прямой у = х.

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

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

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

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

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

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

Не всякое отношение обладает свойством транзитивности. Например, отношение перпендикулярности прямых не транзитивно. В самом деле, если какая-нибудь прямая х перпендикулярна прямой у, и прямая у перпендикулярна прямой z, то прямая х не перпендикулярна прямой z.

П р и м е р. По графам бинарных отношений, заданных на конечных множествах, определим их свойства (рис. 6).

I. II. III.