Свойства бинарных отношений: рефлексивность, симметричность

Бинарное отношение на множестве - это один из базовых инструментов дискретной математики. Три свойства - рефлексивность, симметричность и транзитивность - встречаются буквально в каждом разделе: теория групп, порядок, эквивалентность, алгоритмы на графах. Студенты регулярно путают определения и теряют баллы на контрольных. В этой статье разберём каждое свойство через матрицу и граф, покажем, как их быстро проверять, и объясним, почему именно сочетание всех трёх дёт отношение эквивалентности. Прежде чем читать дальше - попробуйте встроенный калькулятор: кликайте по ячейкам матрицы и смотрите, как меняются свойства.

Что такое бинарное отношение

Пусть $A$ - конечное множество. Бинарное отношение $R$ на $A$ - это подмножество декартова произведения $A \times A$:

$$R \subseteq A \times A.$$

Запись $(a, b) \in R$ (или $aRb$) означает, что элементы $a$ и $b$ "связаны" отношением. Примеры: "меньше или равно" на числах ($\leq$), "делится на" в натуральных числах, "быть однокурсником" среди студентов.

Удобный способ представить отношение на множестве $A = \{1, 2, 3, 4\}$ - это матрица отношения (матрица смежности) $M_R$ размером $|A| \times |A|$:

$$M_R[i][j] = \begin{cases} 1, & \text{если } (i, j) \in R, \\ 0, & \text{иначе.} \end{cases}$$

Второй способ - граф отношения: вершины = элементы $A$, направленное ребро из $i$ в $j$ - если $(i, j) \in R$. Петля из $i$ в $i$ соответствует паре $(i, i)$.

Рассчитать для своей задачи

Рефлексивность: каждый элемент связан с собой

Определение. Отношение $R$ на $A$ называется рефлексивным, если

$$\forall a \in A: (a, a) \in R.$$

Иначе говоря, в матрице $M_R$ вся главная диагональ должна состоять из единиц. В графе это означает, что у каждой вершины есть петля.

Пример. Отношение $\leq$ на $\mathbb{N}$ рефлексивно: $n \leq n$ всегда. Отношение строгого неравенства $<$ - нерефлексивно: $n \not< n$.

Антирефлексивность - противоположное требование: $(a, a) \notin R$ для всех $a$. Строгий порядок $<$ антирефлексивен. Не путайте: отношение может быть ни рефлексивным, ни антирефлексивным (если диагональ содержит и 0, и 1).

Алгоритм проверки по матрице: пробежать по $M_R[i][i]$ при $i = 1, \ldots, n$. Если хоть одна диагональная клетка равна 0 - отношение не рефлексивно. Сложность $O(n)$.

Связь с композицией. Рефлексивность эквивалентна тому, что тождественное отношение $I_A = \{(a,a) \mid a \in A\}$ содержится в $R$: $I_A \subseteq R$. Это удобно при доказательствах: чтобы показать рефлексивность, достаточно показать $I_A \subseteq R$.

Симметричность: парное равноправие

Определение. Отношение $R$ называется симметричным, если

$$\forall a, b \in A: (a, b) \in R \Rightarrow (b, a) \in R.$$

В матрице - $M_R$ симметрична: $M_R[i][j] = M_R[j][i]$ для всех $i, j$. В графе - каждое ребро $i \to j$ сопровождается обратным ребром $j \to i$.

Антисимметричность - если $(a, b) \in R$ и $(b, a) \in R$, то обязательно $a = b$. В матрице вне диагонали не может быть "парных" единиц: $M_R[i][j] \cdot M_R[j][i] = 0$ при $i \neq j$. Порядок $\leq$ - антисимметричен: из $a \leq b$ и $b \leq a$ следует $a = b$.

Ключевой факт: симметричное и антисимметричное одновременно - только диагональное отношение (тождественное или пустое). Это частое заблуждение на экзаменах: студенты думают, что несимметричное == антисимметричное. Нет: несимметричное значит "нарушение есть хоть для одной пары", антисимметричное - строгое требование для всех.

Рассчитать для своей задачи

Алгоритм проверки: для каждого $i < j$ проверить, что $M_R[i][j] = M_R[j][i]$. Если найдено расхождение - не симметрично. Сложность $O(n^2)$.

Симметричность и обратное отношение. Обратное отношение $R^{-1} = \{(b, a) \mid (a, b) \in R\}$ - это транспонирование матрицы $M_R$. Тогда $R$ симметрично тогда и только тогда, когда $R = R^{-1}$, то есть $M_R = M_R^T$. Эта формулировка часто встречается в задачах на проверку через операции над матрицами.

Транзитивность: цепочка подразумевает прямую связь

Определение. Отношение $R$ называется транзитивным, если

$$\forall a, b, c \in A: (a, b) \in R \text{ и } (b, c) \in R \Rightarrow (a, c) \in R.$$

Слоганом: "друг моего друга - мой друг" (но только если дружба ориентирована так же). В матрице транзитивность означает: если в строке $a$ есть единица в столбце $b$, и в строке $b$ есть единица в столбце $c$, то в строке $a$ должна стоять единица в столбце $c$.

Матричный критерий: $R$ транзитивно тогда и только тогда, когда $M_R^2 \leq M_R$ (в булевой алгебре: каждая единица матрицы $M_R^2$ покрыта единицей $M_R$). Здесь $M_R^2$ - булево произведение матриц, $(M_R^2)[i][j] = \bigvee_k (M_R[i][k] \wedge M_R[k][j])$.

Типичная ловушка: если пары $(a, b)$ нет в $R$, то никакого требования на $(a, c)$ не возникает. Условие "$(a,b) \in R$ и $(b,c) \in R$" должно выполняться оба сразу, иначе транзитивность не проверяется. Студенты иногда забывают это: видят отсутствие $(a,c)$ и сразу делают вывод о нетранзитивности, не проверяя наличие цепочки.

Алгоритм проверки (наивный): тройной цикл по $a, b, c$ - если $M_R[a][b]$ и $M_R[b][c]$ и не $M_R[a][c]$, то нарушение. Сложность $O(n^3)$. Альтернатива - алгоритм Уоршелла (аналог алгоритма Флойда-Уоршелла для достижимости): то же $O(n^3)$, но строит транзитивное замыкание.

Транзитивное замыкание

Если отношение не транзитивно, можно построить его транзитивное замыкание $R^+$ - минимальное транзитивное надотношение, содержащее $R$. Оно включает исходные пары и все пары, "следующие" по цепочкам.

Формально:

$$R^+ = R \cup R^2 \cup R^3 \cup \ldots \cup R^n,$$

где $R^k$ - $k$-кратная композиция $R$ с собой, $n = |A|$. В матрицах это соответствует булевой сумме степеней $M_R$:

$$M_{R^+} = M_R \vee M_R^2 \vee \ldots \vee M_R^n.$$

Алгоритм Уоршелла вычисляет $M_{R^+}$ за $O(n^3)$:

Связь свойств между собой

Три свойства независимы: каждое можно выполнять или нарушать отдельно. Однако есть полезные взаимосвязи.

Если $R$ симметрично и транзитивно, то из $(a, b) \in R$ следует $(b, a) \in R$ (симметричность), а затем из $(a, b) \in R$ и $(b, a) \in R$ по транзитивности - $(a, a) \in R$. Значит, каждый элемент, хотя бы с кем-то связанный, состоит в паре с собой. Но если элемент вообще ни с чем не связан, пара $(a, a)$ может отсутствовать. Поэтому симметричность + транзитивность не гарантирует рефлексивности - нужно явно проверять все элементы.

Транзитивность замкнута под пересечением: если $R_1$ и $R_2$ транзитивны, то $R_1 \cap R_2$ тоже транзитивно. То же для рефлексивности и симметричности. Поэтому пересечение отношений эквивалентности - снова отношение эквивалентности. Это используется при построении отношения, порождённого данным множеством пар: берётся пересечение всех эквивалентностей, содержащих эти пары.

Классификация отношений по свойствам

Комбинация трёх свойств даёт классические типы отношений, которые встречаются повсюду:

Отношение эквивалентности - рефлексивное, симметричное и транзитивное одновременно. Оно разбивает множество на непересекающиеся классы эквивалентности (теорема о разбиении). Классические примеры: "быть конгруэнтным по модулю $m$" на $\mathbb{Z}$, "иметь одинаковый остаток при делении на $n$".

Нестрогий частичный порядок $\leq$ - рефлексивный, антисимметричный и транзитивный. Пример - делимость на $\mathbb{N}$: $1 | 2 | 4$, но $2$ и $3$ не сравнимы. Если любые два элемента сравнимы - это линейный (полный) порядок.

Совместимость (толерантность) - рефлексивное и симметричное, но не обязательно транзитивное. Пример: "иметь хотя бы одного общего знакомого" - рефлексивно (вы знаете себя) и симметрично (если A знает общего знакомого с B, то и B с A), но не транзитивно (A-B и B-C не гарантируют общего знакомого для A-C).

Строгий порядок $<$ - антирефлексивное, антисимметричное и транзитивное. В матрице: диагональ полностью нулевая, нет парных единиц вне диагонали, квадрат матрицы не выходит за исходную. На диаграммах Хасе строгий порядок изображают без петель (антирефлексивность очевидна из рисунка).

Частые ошибки

• Путают "не симметричное" и "антисимметричное". Нет - это разные понятия. Несимметричность означает, что есть хоть одна пара $(a,b)$, у которой нет обратной. Антисимметричность - более строгое условие на все пары.
• Проверяют транзитивность для несуществующих цепочек. Условие $(a,b) \in R \wedge (b,c) \in R$ должно выполняться оба сразу; если первой пары нет, требование снимается.
• Забывают проверить диагональные элементы при рефлексивности. В частности, в пустом отношении $R = \emptyset$ нет пар $(a,a)$, поэтому оно нерефлексивно (и антирефлексивно).
• Считают, что любое антисимметричное отношение - порядок. Нет: нужна ещё рефлексивность и транзитивность.
• Применяют матрицу без чёткого порядка строк и столбцов. Строка $i$ и столбец $j$ должны соответствовать одному и тому же элементу $i$ и $j$ - иначе матрица бессмысленна.

FAQ

Может ли отношение быть одновременно симметричным и антисимметричным? Да - если вне диагонали нет ни одной единицы. Тождественное отношение $I_A = \{(a,a) \mid a \in A\}$ и пустое $\emptyset$ обладают обоими свойствами. Это не противоречие: требования просто не конфликтуют на пустом или диагональном носителе.

Как транзитивность связана с матрицей смежности? Отношение $R$ транзитивно тогда и только тогда, когда $M_R^2 \leq M_R$ в булевой алгебре, то есть $M_R \cdot M_R$ (булево произведение) не содержит единиц там, где $M_R$ их нет. Практически: вычисляем $M_R^2$, проверяем, что каждая единица $M_R^2$ покрыта единицей $M_R$.

Что такое рефлексивное замыкание и чем отличается от транзитивного? Рефлексивное замыкание $R \cup I_A$ - добавляем диагональные пары, которых не хватает для рефлексивности. Транзитивное замыкание $R^+$ - добавляем все пары, вытекающие из цепочек. Оба - наименьшие расширения $R$ с нужным свойством. Рефлексивно-транзитивное замыкание $R^* = R^+ \cup I_A$ используется в теории формальных языков и алгоритмах на графах.

Коротко

Бинарное отношение рефлексивно, если каждый элемент связан с самим собой (единицы на диагонали матрицы). Симметрично - если связь двусторонняя (матрица симметрична). Транзитивно - если из цепочки двух связей следует прямая (булево квадрат матрицы не выходит за пределы исходной). Сочетание всех трёх свойств даёт отношение эквивалентности и разбивает множество на классы; рефлексивность с транзитивностью без симметрии - нестрогий порядок. Быстро проверить свойства на конкретных парах поможет калькулятор выше: кликайте по ячейкам и наблюдайте, как меняется классификация.