§12. Понятие бинарного отношения между элементами одного множества
Чтобы построить математическую теорию нужны не только сами элементы, но и отношения между ними. Для чисел имеет смысл понятие равенства: а = b. Если числа а и b разные, а ? b, тогда возможно или а > b, или а < b.
Две прямые плоскости могут быть перпендикулярными, параллельными, пересекаться под некоторым углом.Все эти отношения касаются двух объектов. Поэтому они называются бинарными отношениями.
Для изучения отношений между объектами в математике создана теория бинарных отношений.
Когда мы рассматриваем те или иные отношения, мы всегда имеем дело с упорядоченными парами, образованными из элементов данного множества. Например, для отношения «больше на 4», которое рассматривается на множестве Х = {2, 6, 10, 14}, это будут упорядоченные пары (2, 6), (6, 10), (10, 14), а для отношения «делится» — (6, 2), (10, 2), (14, 2).
Можно заметить, что множество пар, которые определяют отношения «больше на 4», «делится», являются подмножествами декартова произведения
Х ´ Х ={(2, 2), (2, 6), (2, 10), (2, 14), (6, 2), (6, 6), (6, 10), (6, 14), (10, 2), (10, 6), (10, 10), (10, 14), (14, 2), (14, 6), (14, 10), (14, 24)}.
Определение 1. Бинарным отношением между элементами множества Х или отношением на множестве Х называется всякое подмножество декартова произведения Х ´ Х.
Бинарные отношения обычно обозначают заглавными буквами латинского алфавита: P, T, S, R, Q и т. д. Итак, если Р–отношение на множестве Х, то Р Ì Х ´ Х. Часто для записи отношений используются разные специальные символы, например, =, >, ~, ½½, ^ и т. д. Множество всех первых элементов пар из Р называется областью определения отношения Р. Множеством значений отношения Р называется множество всех вторых элементов пар из Р.
Для наглядности бинарные отношения изображают графически с помощью специального рисунка графа. Элементы множества Х изображают точками.
Если имеет место (х, у) Î Р(хРу), то из точки х проводят стрелку в точку у. Такой чертеж называют графом отношения Р, а точки, изображающие элементы множества Х, вершинами графа. стрелки рёбрами графа.Пример. Пусть отношение Р: «число х — делитель числа у», заданного на множестве
Х = {5, 10, 20, 30, 40}, изображен на рисунке 25.
Рис. 25
Стрелки графа, у которых началом и концом является одна и та же точка, называются петлями. Если на графе отношения Р изменить направления всех стрелок на противоположные, то получится новое отношение, которое называют обратным для Р. Его обозначают Р–1. Отметим, что хРу Û уР–1х.
Способы задания бинарных отношений.
Поскольку отношение R между элементами множества Х — это множество, элементами которого являются упорядоченные пары, то его можно задать теми же способами, что и любое множество.
1. Чаще всего отношение R на множестве Х задают при помощи характеристического свойства пар элементов, находящихся в отношении R. Это свойство формулируют в виде предложения с двумя переменными.
Например, среди отношений на множестве Х = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, можно рассматривать следующие: «число х меньше числа у в 2 раза», «число х — делитель числа у», «число х больше, чем число у» и другие.
2. Отношение R на множестве Х можно задать и путем перечисления всех пар элементов множества Х, связанных отношением R.
Например, если записать множество пар (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4), то на множестве Х = {1, 2, 3, 4} мы зададим некоторое отношение R. Это же отношение R можно задать и
3. при помощи графа (рис. 26).
Рис. 26
Свойства бинарных отношений.
Определение 2. Отношение R на множестве Х называется рефлексивным, если каждый элемент из множества Х сам с собой находится в этом отношении.
Короче: R рефлексивно на Х Û хRx для любого x Î X.
или, что тоже: в каждой вершине графа отношения есть петля. Верно и обратное: если ни каждая вершина графа отношения имеет петлю, то это рефлексивное отношение.
Пример. Рефлексивные отношения: «быть равными на множестве всех треугольников плоскости», «? и £ на множестве всех действительных чисел».
Отметим, что существуют отношения, которые не обладают свойством рефлексивности.(привести пример «х больше у»)
Определение 3. Бинарное отношение R на множестве Х называется антирефлексивным на Х, если для каждого х из Х (х, х) Ï R, т.е. для каждого х из Х не выполняется условие хRх.
Если отношение R антирефлексивно, то ни одна вершина его графа не имеет петли. Обратно: если ни одна вершина графа не имеет петли, то граф представляет антирефлексивное отношение.
Примеры антирефлексивных отношений: «быть старше», «быть меньше», «быть дочерью» и др.
Определение 4. Отношение R на множестве Х называется симметричным, если для любых элементов х, 
Î X выполняется условие: если х и у находятся в отношении R, то у и х тоже находятся в этом отношении.
Короче: R симметрично на Х Û хRу Û уRх.
Граф симметричного отношения обладает свойством: если есть стрелка, соединяющая пару элементов, то обязательно есть вторая, которая соединяет эти же элементы, но идет в противоположно направлении. Верно и обратное утверждение.
Примерами симметричных отношений являются отношения: «быть взаимно перпендикулярными на множестве всех прямых плоскости», «быть подобными на множестве всех прямоугольников плоскости».
Определение 5. Если ни для каких элементов х и у из множества Х не может случиться, что одновременно и хRу, и уRх, то отношение R на множестве Х называется асимметричным.
Пример асимметричного отношения: «быть отцом» (если х –– отец у, то у не может быть отцом х).
Определение 6. Отношение R на множестве Х называется антисимметричным, если для разных элементов х, у Î Х из того, что элемент х находится в отношении R с элементом у, следует, что элемент у не находится в отношении R с элементом х.
Короче: R антисимметрично на Х Û хRу и х ? у ? 
.
Например, отношение «меньше» на множестве целых чисел, является антисимметричным.
Граф антисимметричного отношения обладает особенностью: если две вершины графа соединены стрелкой, то эта стрелка только одна. Справедливым является и обратное утверждение.
Заметим, что существуют отношения, которые не обладают ни свойством симметричности, ни свойством антисимметричности.
Определение7. Отношение R на множестве Х называется транзитивным, если для любых элементов х, у, z Î Х выполняется условие: если х находится в отношении R с у и у находится в отношении R с z, то элемент х находится в отношении R с элементом z.
Короче: R транзитивно на Х Û хRу и уRz ? хRz.
Например, отношение «прямая х параллельна прямой у», заданное на множестве прямых плоскости, является транзитивным.
Граф транзитивного отношения обладает особенностью: с каждой парой стрелок, идущих от х к у и от у к z, он содержит и стрелку, идущую от х к z. Верно и обратное утверждение.
Заметим, что существуют отношения, которые не обладают свойством транзитивности. Например, отношение «стоять рядом на полке» не транзитивно.
Все общие свойства отношений можно разбить на три группы:
рефлексивности (каждое отношение рефлексивно или антирефлексивно),
симметричности (отношение всегда или симметрично или асимметрично, или антисимметрично),
транзитивности (каждое отношение транзитивно или не транзитивно). Отношениям, обладающим определенным набором свойств, присвоены специальные названия.