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

Отношение R называется рефлексивным, если для любого аÎ М имеет место aRa. Главная диагональ его матрицы содержит только единицы. Отношение R называется антирефлексивным, если ни для какого a Î R не выполняется aRa. Главная диагональ его матрицы содержит только нули. Отношение £ и «иметь общий делитель» рефлексивны, отношения < и «быть сыном» антирефлексивны. Отношение «быть симметричным относительно оси х» не является ни рефлексивным, ни антирефлексивным: точка плоскости симметрична сама себе, если она лежит на оси х, и несимметрична сама себе в противном случае.

Отношение R называется симметричным, если для пары (а, b) Î М² из aRb следует bRa (иначе говоря, для любой пары R выполняется либо в обе стороны, либо не выполняется вообще). Матрица симметричного отношения симметрична относительно главной диагонали: c_ij = c_ji для любых i и j. Отношение R называется антисимметричным, если из a_iRa_j, и a_jRa_i следует, что a_i = a_j. Отношение «быть симметричным относительно оси х» является симметричным: если первая точка симметрична второй, то и вторая симметрична первой. (Эта фраза вовсе не является тавтологией, так как два упоминания в ней термина «симметричный» имеют разный смысл и относятся к двум разным типам объектов: первое упоминание – к свойству пар точек на плоскости, а второе – к свойству отношения между парами точек.) Пример антисимметричного отношения – отношение £: действительно, если а £ b и b £ a, то a = b. Нетрудно убедиться в том, что отношение R симметрично тогда и только тогда, когда R = R ^-1.

Отношение R называется транзитивным, если для любых a, b, с из aRb и bRc следует aRc. Отношения «равенство», £, «жить в одном городе» транзитивны; отношение «быть сыном» не транзитивно. Отношение «пересекаться», т.е. «иметь непустое пересечение», заданное на системе множеств, также не транзитивно. Например, {1, 2} пересекается с {2, 3}, {2, 3} пересекается с {3, 4}, однако {1, 2} и {3, 4} не пересекаются.

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

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

Отношения эквивалентности

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

Пример 3.13.

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

2. Утверждения вида (а + b)(a – b) = а^{2 –} b² или sin² x + cos² x = 1, состоящие из формул, соединенных знаком равенства, задают бинарное отношение на множестве формул, описывающих суперпозиции элементарных функций. Это отношение обычно называется отношением равносильности и определяется следующим образом: формулы равносильны, если они задают одну и ту же функцию. Равносильность, хотя и обозначается знаком =, отличается от отношения равенства Е, так как оно может выполняться для различных формул (впрочем, можно считать, что знак равенства в таких соотношениях относится не к формулам, а к функциям, которые ими описываются). Отношение Е для формул – это совпадение формул по написанию. Оно называется графическим равенством.

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

4. Отношение «иметь один и тот же остаток от деления на 7» является эквивалентностью на N. Это отношение выполняется, например, для пар (11, 46), (14, 70) и не выполняется для пар (12, 13), (14, 71).

Пусть на множестве М задано отношение эквивалентности R. Осуществим следующее построение. Выберем элемент a₁ Î M и образуем класс (подмножество М) С₁, состоящий из а₁ и всех элементов, эквивалентных a₁; затем выберем элемент a₂ Ï C₁ и образуем класс C₂, состоящий из a₂ и всех элементов, эквивалентных a₂, и т. д. Получится система классов С₁, С₂, … (возможно, бесконечная) такая, что любой элемент из М входит хотя бы в один класс, т.е. È C_i = M. Эта система классов обладает следующими свойствами: 1) она образует разбиение, т.е. классы попарно не пересекаются; 2) любые два элемента из одного класса эквивалентны; 3) любые два элемента из разных классов неэквивалентны. Все эти свойства немедленно вытекают из рефлексивности, симметричности и транзитивности R. Действительно, если бы классы, например С₁ и С₂, пересекались, то они имели бы общий элемент b, эквивалентный а₁ и a₂, но тогда из-за транзитивности R было бы a₁Ra₂, что противоречит построению C₂ . Аналогично доказываются другие два свойства.

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

Пример 3.14.

1. Все классы эквивалентности по отношению равенства Е состоят из одного элемента.

2. Формулы, описывающие одну и ту же элементарную функцию, находятся в одном классе эквивалентности по отношению равносильности. В этом примере счетны само множество формул, множество классов эквивалентности (т. е. индекс разбиения) и каждый класс эквивалентности.

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

4. Разбиение N по отношению «иметь общий остаток от деления на 7» имеет конечный индекс 7 и состоит из 7 счетных классов 0, 7, 14...; 1, 8, 15...; 2, 9, 16...; ...; 6, 13, 20... .