Отношения являются частным случаем соответствий. Поэтому для них справедливы абсолютно все свойства соответствий. Также вводятся несколько специальных свойств, используемых только для отношений.
Определение 2.23. Отношение на множестве называется рефлексивным, если для любого имеет место .
Главная диагональ матрицы рефлексивного отношения содержит только единицы.
Определение 2.24. Отношение на множестве называется антирефлексивным, если ни для какого не выполняется .
Главная диагональ матрицы антирефлексивного отношения содержит только нули.
Определение 2.25 Отношение на множестве называется нерефлексивным, если оно не рефлексивно и не антирефлексивно
Пример 2.21 Отношение «иметь общий делитель» на множестве натуральных чисел рефлексивно, поскольку число может иметь общий делитель с самим собой.
Пример 2.22 Отношение «быть сыном» антирефлексивно, т.к. любой человек не может быть сыном самого себя
Пример 2.23. Отношение «быть симметричным относительно оси х» нерефлексивно, поскольку, точка симметрична самой себе, если лежит на оси x, и несимметрично в противном случае
Определение 2.26. Отношение называется симметричным, если для пары из следует (иначе говоря, для любой пары выполняется либо в обе стороны, либо не выполняется вообще).
Матрица симметричного отношения симметрична относительно главной диагонали: для любых и .
Определение 2.27 Отношение называется антисимметричным, если из ; и следует, что ;.
Пример 2.24 Отношение «быть симметричным относительно оси х» является симметричным: если первая точка симметрична второй, то и вторая симметрична первой. Пример антисимметричного отношения — отношение <: действительно, если и , то . Нетрудно убедиться в том, что отношение симметрично тогда и только тогда, когда .
Определение 2.28. Отношение называется транзитивным, если для любых , , из и следует . Отношения «равенство», <, «жить в одном городе» транзитивны; отношение «быть сыном» нетранзитивно. Отношение «пересекаться», т. е. «иметь непустое пересечение», заданное на системе множеств, также нетранзитивно. Например, {1, 2} пересекается с {2, 3}, {2, 3} пересекается с {3, 4}, однако {1, 2} и {3, 4} не пересекаются.
Для любого отношения отношение , называемое транзитивным замыканием , определяется следующим образом: , если в существует цепочка из элементов , в которой между соседними элементами выполнено : , ,…, , Если транзитивно, то .
Пример 2.25 Транзитивным замыканием отношения «быть сыном» является отношение «быть прямым потомком», являю щееся объединением отношений «быть сыном», «быть внуком», «быть правнуком» и т. д.
Пример 2.26 Транзитивным замыканием отношения «иметь общую стену» для жильцов дома является отношение «жить на одном этаже».
Определение 2.29 Отношение называется отношением эквивалентности (или просто эквивалентностью), если оно рефлексивно, симметрично и транзитивно.
Пример 2.27. Отношение равенства Е на любом множестве является отношением эквивалентности. Равенство — это минимальное отношение эквивалентности в том смысле, что при удалении любой пары из Е (т. е. любой единицы на диагонали матрицы Е) оно перестает быть рефлексивным и, следовательно, уже не является эквивалентностью.
Пример 2.28 Утверждения вида или , состоящие из формул, соединенных знаком равенства, задают бинарное отношение на множестве формул, описывающих суперпозиции элементарных функций (см. пример 1.10, г). Это отношение обычно называется отношением равносильности и определяется следующим образом: формулы равносильны, если они задают одну и ту же функцию. Равносильность, хотя и обозначается знаком =, отличается от отношения равенства Е, так как оно может выполняться для различных формул (впрочем, можно считать, что знак равенства в таких соотношениях относится не к формулам, а к функциям, которые ими описываются). Отношение Е для формул — это совпадение формул по написанию. Оно называется графическим равенством.
Введём в рассмотрение определение класса:
Определение 2.30 Подмножество, все элементы которого обладают некоторым общим свойством, называется классом.
Пусть на множестве задано отношение эквивалентности . Осуществим следующее построение. Выберем элемент и образуем класс , состоящий из и всех элементов, эквивалентных . Затем выберем элемент и образуем класс , состоящий из и всех элементов, эквивалентных , и т. д.
Получится система классов , , …. . (возможно, бесконечная) такая, что любой элемент из М входит хотя бы в один класс, т. е. . Эта система классов обладает следующими свойствами: 1) она образует разбиение, т. е. классы попарно не пересекаются; 2) любые два элемента из одного класса эквивалентны; 3) любые два элемента из разных классов неэквивалентны. Все эти свойства немедленно вытекают из рефлексивности, симметричности и транзитивности . Действительно, если бы классы, например и С2, пересекались, то они имели бы общий элемент , эквивалентный и , но тогда из-за транзитивности было бы , что противоречит построению . Аналогично доказываются другие два свойства.
Построенное разбиение, т. е. система классов, называется системой классов эквивалентности по отношению . Мощность этой системы называется индексом разбиения. С другой стороны, любое разбиение М на классы определяет некоторое отношение эквивалентности, а именно, отношение «входить в один и тот же класс (данного разбиения).
Пример 2.29. Все классы эквивалентности по отношению равенства Е состоят из одного элемента.
Пример 2.30 Формулы, описывающие одну и ту же элементарную функцию, находятся в одном классе эквивалентности по отношению равносильности. В этом примере счетны само множество формул, множество классов эквивалентности (т. е. индекс разбиения) и каждый класс эквивалентности.