Специальные свойства бинарных отношений

В этой лекции дана определенная классификация бинарных отношений на множестве. В основе этой классификации лежат специальные свойства отношений.

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

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

Не следует путать иррефлексивное отношение с нерефлексивным, т.е. не являющимся рефлексивным, отношением. Иррефлексивное отношение нерефлексивно, но не всякое нерефлексивное отношение иррефлексивно. Иррефлексивному отношению на , а нерефлексивное отношение может содержать некоторые (но не все!) элементы диагонали. На рис. 1.7 приведены примеры графиков иррефлексивного и нерефлексивного отношений (пунктиром указаны диагонали множеств).

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

Бинарное отношение на множестве 1) симметричным, если для любых из следует ;2) антисимметричным, если для любых из одновременной справедливости и следует, что .

Соответствующие свойства бинарных отношений на множестве Теорема 1.1. Бинарное отношение на множестве , совпадает с .

Пусть , то есть . Тогда, в силу симметричности . Следовательно, . Аналогично доказывается включение .

Теперь пусть и . Из определения обратного отношения вытекает, что . Следовательно, — симметричное бинарное отношение.

Теорема 1.2. Бинарное отношение на множестве .

Действительно, если , то и (т.е. ). Но из выполнения соотношений и ввиду антисимметричности следует, что , то есть .

Обратно, пусть . Предположим, что и , причем . Тогда и , но . Получаем противоречие.

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

Бинарное отношение на множестве из того, что и , следует . Соответствующее свойство бинарного отношения называют транзитивностью.

Пример 1.12. а. Пусть — некоторое множество населенных пунктов. Зададим на нем бинарное отношение достижимости: из пункта , то из .

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

в. Бинарное отношение неравенства на множестве действительных чисел не транзитивно, так как из того, что и , вовсе не следует, что . Аналогично, если , а друг

Транзитивность бинарного отношения

Докажем следующее важное свойство транзитивного бинарного отношения.

Теорема 1.3. Бинарное отношение на множестве .

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

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

Плотное бинарное отношение

Бинарное отношение на множестве , отличных друг от друга и таких, что , найдется , такой, что и .

Образно говоря, для любой пары элементов, связанных плотным отношением, всегда найдется третий элемент, который "встраивается между ними" и связан с каждым из них тем же отношением. Так, отношения неравенства (строгого и нестрогого) на множествах рациональных и действительных чисел плотны, но аналогичные отношения на множествах целых и натуральных чисел плотными не являются. В самом деле, каковы бы ни были рациональные (или действительные) числа , из того, что , следует, что существует число , такое, что . Например, подходит число . Но для целых чисел — плотное бинарное отношение на множестве имеет место , то найдется и . Отсюда в силу определения композиции отношений следует, что . Значит, из следует , то есть .

Итак, если плотно, то оно содержится в своем квадрате. Напомним, что для транзитивного бинарного отношения . Следовательно, если бинарное отношение одновременно плотно и транзитивно, то

Классы бинарных отношений

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

Бинарное отношение на некотором множестве называют:

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

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

б. Бинарное отношение на множестве всех непустых подмножеств некоторого множества тогда и только тогда, когда , является толерантностью. Это отношение рефлексивно и симметрично, но не транзитивно. Действительно, из того, что и , никак не следует, что (рис. 1.9).

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

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

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

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

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

е. Отношение строгого неравенства на числовом множестве, равно как и отношение строгого включения множеств, есть отношение строгого порядка.

ж. В качестве примера отношения строгого предпорядка можно привести отношение "строгой достижимости" на некотором множестве населенных пунктов: пункт

Связь между классами бинарных отношений

Отношения толерантности, эквивалентности, предпорядка и порядка — важнейшие в современной математике. Связь между этими четырьмя классами бинарных отношений показана на рис. 1.10. Можно сказать, что эквивалентность есть транзитивная толерантность или симметричный предпорядок. Порядок же есть антисимметричный предпорядок.

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

Отношение называют рефлексивно-транзитивным замыканием бинарного отношения на соответствующем множестве.

Можно также обозначить , и тогда .

Отношение является рефлексивным, так как . Докажем его транзитивность. Пусть для каких-то выполняется и . Докажем, что . Будем считать, что элементы попарно различны (так как при или доказывать нечего). Тогда существуют последовательности

такие, что для каждого и для каждого .

В итоге получаем последовательность

для всякого , для всякого , такую, что для любого , то есть , что и требовалось доказать.