Основы высшей математики / Отношения и соответствия

В обычной жизни мы постоянно говорим об отношениях между двумя объектами. Например, х работает иод руководством у, х является отцом у, х и у друзья — это отношения между людьми. Число х больше числам, число х делится на у, числа х и у при делении на 3 дают одинаковый остаток — это отношения между числами.

Всякая математическая теория имеет дело с множеством каких-нибудь объектов или элементов. Чтобы построить математическую теорию нужны не только сами элементы, но и отношения между ними. Для чисел имеет смысл понятие отношений: a = b , или а > b, или а < b. Две прямые плоскости могут быть параллельными или пересекаться.

Все эти отношения касаются двух объектов. Поэтому они называются бинарными отношениями.

Когда мы рассматриваем те или иные отношения, мы всегда имеем дело с упорядоченными парами, образованными из элементов данного множества. Например, для отношения «число x больше на 4, чем число y », которое рассматривается на множестве X = , это будут упорядоченные пары (6,2), (10, 6), (14, 10). Они — подмножество декартова произведения X X .

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

Бинарные отношения обычно обозначают заглавными буквами латинского алфавита: Р, Т, S, R, Q и т.д. Итак, если P — отношение на множестве X, то Р X X. Множество всех первых элементов пар из Р называется областью определения отношения Р. Множеством значений отношения Р называется множество всех вторых элементов пар из Р.

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

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

Например, граф отношения Р: «число х — делитель числа у», заданного на множестве X = , изображен на рис. 54.

Стрелки графа, у которых началом и концом является одна и та же точка, называются петлями. Если на графе отношения Р изменить направления всех стрелок на

противоположные, то получится новое отношение, которое называют обратным для Р. Его обозначают Р -1 . Отметим, что хРу уР -1 х.

Способы задания бинарных отношений, их свойства

Поскольку отношение R между элементами множества Х — это множество, элементами которого являются упорядоченные пары, то его можно задать теми же способами, что и любое множество.

Чаще всего отношение R на множестве X задают при помощи характеристического свойства пар элементов, находящихся в отношении R. Это свойство формулируют в виде предложения с двумя переменными. Например, среди отношений на множестве Х = можно рассматривать следующие: «число х меньше числа у в 2 раза», «число х — делитель числа у» и др.

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

Например, если записать множество пар (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3,

4), то на множестве

X = мы зададим некоторое

Это же отношение R можно задать и при помощи графа (рис). Выделим важнейшие свойства бинарных отношений.

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

Короче данное определение можно записать так: R рефлексивно на Х хRх для любого х X.

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

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

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

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

Короче: R симметрично на X xRy yRx.

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

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

Определение 3 . Если ни для каких элементов х и у из множества X не может случиться, что одновременно и xRy, и yRx, то отношение R на множестве X называется асимметричным. Пример асимметричного отношения: «быть отцом» (если х — отец у , то у не может быть отцом х).

Определение 4. Отношение R на множестве X называется антисим-

метричным, если для разных элементов х, у

того, что элемент х

находится в отношении R с элементом у, следует, что элемент у не находится в