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

Отношение R называется рефлексивным, если для любого аМ имеет место аRа. Главная диагональ его матрицы содержит только единицы. Отношение R называется антирефлексивным, если ни для одного из аМ не выполняется аRа. Главная диагональ его матрицы содержит только нули.

Так например, отношения  и “имеет общий делитель” - рефлексивны, отношения < и “быть сыном” – антирефлексивны.

Отношение R называется симметричным, если для пар (а, в)М² из аRв следует вRа. (Иначе говоря, для любой пары R выполняется либо в обе стороны либо не выполняется вообще матрица симметричного отношения, симметрична относительно главной диагонали: a_ij = a_ji.

Пример. – Быть симметричным относительно оси Х.

Отношение R называется антисимметричным, если из a_iRa_j и a_jRa_i следует, что a_i=a_j. Отношение ”быть симметричным: если первая точка симметрична второй, то и вторая симметрична первой.

Пример антисимметричного отношения – отношение : действительно, если а  в и в а, то а=в. Нетрудно убедится в том, что отношение R симметрично тогда и только тогда, когда R=R^-1.

Отношение r называется транзитивным, если для любых а, в, с из аRв и вRс следует аRс. Отношения “равенство”,, “жить в одном городе” транзитивны; отношение “быть сыном” не транзитивно.

Для любого отношенияR отношение называемое транзитивным замыканием R, определяется следующим образом: а в, если, в М существует цепочка из n элементов а=а₁, а₂, …, а_n-1, а_n=в, в которой между соседними элементами выполнено R: а₁Rа₂, а₂Rа₃, ……, а_n1Rв. Если R транзитивно, то = R. Действительно, если аRв, то ав (цепочка состоит из двух элементов а, в), поэтому R . Если же ав, то существует цепочка а₁Rа₂, а₂Rа₃,…,а_n-1Rв. Но так как R транзитивно, то аRв, поэтому  R. Из включения в обе стороны следует R=.

Транзитивным замыканием отношения “быть сыном” является отношение “быть прямым потомком”, являющееся объединением отношений “быть сыном”, “быть внуком”, “быть правнуком” и т. д

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

Пример 1. Отношение равенства Е на любом множестве является отношением эквивалентности. Равенство – это минимальное отношение эквивалентности в том смысле, что при удалении любой пары из Е (т. е. любой единицы на диагонали матрицы Е) оно перестает быть рефлексивным, и, следовательно, уже не является эквивалентностью.

Пример 2. Рассмотрим множество треугольников на плоскости, считая, что треугольник задан, если заданы координаты его вершин. Два треугольника называются равными, если при наложении они совпадают, т. е. могут быть переведены друг в друга путем некоторого перемещения. Отношение равенства (конгруэнтности) является отношением эквивалентности на множестве .

Пример 3. Отношение “иметь один и тот же остаток отделения на 7” является эквивалентностью на множестве целых положительных чисел N. Это отношение выполняется, например, для пар (11, 46), (14, 70) и не выполняется для пар (12, 13), (14, 71).

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

Пример 4. Отношение  и  для чисел являются отношениями нестрогого порядка, отношения  и  - отношениями строгого порядка. Оба отношения полностью упорядочивают множества N и R.

Пример 5. На системе подмножеств множества М отношение включения  задает нестрогий частичный порядок, а отношение строгого порядка включения  задает строгий порядок. Например

{1, 2}{1, 2, 3}, a {1, 2} и {1, 3, 4} не сравнимы.

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

Пример 7. Пусть в списке конечного алфавита А порядок букв зафиксирован, т. е. всегда один и тот же. Тогда этот список определяет полное упорядочение букв, которое назовем отношением предшествования и обозначим aiaj (если ai предшествует aj в списке букв). На отношение предшествования букв строится отношение предшествования слов. Это отношение задает полное упорядочение множества всех конечных слов в алфавите А, которое называется лексикографическим упорядочением слов. Примером такого упорядочения является словарь.

Пример 8. Если рассматривать числа в позиционных системах счисления (напр. десятичной), как слова в алфавите цифр, то их лексикографическое упорядочение совпадает с обычным, если все сравнимые числа имеют одинаковое число разрядов.

20 < 1073;

20 1073;

0020 1073.