Отношения и соответствия: эквивалентность, порядок, функции

«Ваня дружит с Петей», «6 больше 4», «эти два треугольника подобны», «файл лежит в папке» — за всеми этими фразами прячется одна и та же конструкция: пара объектов и связь между ними. Дискретная математика выдирает связку из языка и учит её считать: сколько связей может быть, какими свойствами они обладают и что из этих свойств следует. Получается инструмент, без которого не строятся ни базы данных, ни графы, ни сортировки.

Декартово произведение и бинарное отношение#

В уроке о множествах мы уже строили декартово произведение: для множеств $A$ и $B$ множество $A\times B$ — это все упорядоченные пары $(a,b)$. Например, $A=\{1,2\}$, $B=\{a,b,c\}$, тогда $A\times B=\{(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)\}$ — всего $2\cdot 3=6$ пар.

Бинарное отношение из $A$ в $B$ — это просто любое подмножество $A\times B$: $R\subseteq A\times B$. Если пара $(a,b)$ попала в $R$, пишут $aRb$ и читают «$a$ находится в отношении $R$ с $b$». Из 6 пар произведения выше можно составить $2^6=64$ разных отношения — от пустого до полного.

Живой пример: $A=B=\{1,2,3\}$, отношение «меньше». Оно собирается из пар $(1,2),(1,3),(2,3)$ — именно они удовлетворяют условию $a<b$. Отношение на одном множестве (когда $R\subseteq A\times A$) удобно рисовать стрелками между элементами — по сути, получается ориентированный граф, см. словарную статью граф.

Числовая проверка: если $|A|=n$, то число пар в $A\times A$ равно $n^2$, а число возможных отношений на $A$ — $2^{n^2}$. Уже при $n=3$ это $2^9=512$ отношений, при $n=5$ — $2^{25}\approx 33,5$ миллиона. Поэтому с отношениями работают не перебором, а через свойства.

Как хранить отношение в компьютере? Таблицей: строки — элементы $A$, столбцы — элементы $B$, в ячейке 1, если пара есть в $R$, и 0, если нет. Такая таблица называется матрицей отношения — это обычная матрица из нулей и единиц, только с особым смыслом.

Четыре свойства: рефлексивность и компания#

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

Проверим свойства на конкретном отношении. Возьмём $A=\{1,2,3\}$ и $R$ = «делится на» ($aRb$, если $a$ делится на $b$). Рефлексивность: каждое число делится на себя — есть. Антисимметричность: если $a$ делится на $b$ и $b$ на $a$, то $a=b$ — есть. Транзитивность: если $a$ делится на $b$ и $b$ на $c$, то $a$ делится на $c$ — тоже есть (например, 12 делится на 6, 6 на 3, и 12 делится на 3). Симметричности нет: 12 делится на 3, а 3 на 12 — нет. Выходит, «делится на» — рефлексивное, антисимметричное, транзитивное отношение. И это не случайный набор свойств.

• Эквивалентность = рефлексивность + симметричность + транзитивность: «равенство с расфокусом».
• Порядок = рефлексивность + антисимметричность + транзитивность: те же три, но средняя строже.
• Симметричность спрашивает «а в обратную сторону?», антисимметричность — «а если в обе, то может, это один элемент?»
• Транзитивность — мостик через посредника: если $a$ связан с $b$, а $b$ с $c$, то $a$ обязан быть связан с $c$.

Эквивалентность: равенство с поправкой на задачу#

Отношение, которое рефлексивно, симметрично и транзитивно, называется отношением эквивалентности. Интуиция: это «равенство» в широком смысле — объекты считаются одинаковыми по выбранному критерию. Примеры вокруг: «жить в одном городе», «дроби равны по значению» ($\frac{1}{2}=\frac{2}{4}$, хотя записи разные), «углы равны по мере».

Главный факт: отношение эквивалентности на множестве разбивает его на классы эквивалентности — непересекающиеся группы, внутри которых все элементы эквивалентны друг другу. Вместе классы покрывают всё множество. Такое разделение называется разбиением. И работает в обе стороны: всякое разбиение порождает эквивалентность «лежать в одной группе».

Числовой пример. Отношение $a\equiv b(\text{mod }3)$ на целых числах: числа эквивалентны, если их разность делится на 3. Проверим свойства: $a-a=0$ делится на 3 — рефлексивность; если $a-b$ делится на 3, то и $b-a=-(a-b)$ — симметричность; суммы разностей тоже делятся на 3 — транзитивность. Классы получаются три: остаток 0 — $\{0,3,6,\dots \}$, остаток 1 — $\{1,4,7,\dots \}$, остаток 2 — $\{2,5,8,\dots \}$. Множество всех целых чисел рассыпалось на три бесконечные полки.

Порядок: когда элементы можно сравнивать#

Рефлексивное, антисимметричное и транзитивное отношение называется отношением порядка (нестрогого: $\le$). Если убрать рефлексивность и потребовать вместо антисимметричности иррефлексивность (никто не связан с самим собой), получится строгий порядок вроде $<$. Порядок называется линейным, если любые два элемента сравнимы (числа: $3\le 7$ или $7\le 3$ — всегда), и частичным, если есть несравнимые пары.

Эталон частичного порядка — отношение включения на множествах: $\{1\}\subseteq \{1,2\}$, но $\{1\}$ и $\{2\}$ не сравнимы ни так, ни этак. Второй пример — «является предком» в генеалогическом дереве: двоюродные братья друг другу не предки. Рисуют частичный порядок диаграммой Хассе — снизу вверх, от меньших элементов к большим. Топологическая сортировка, о которой вы услышите в курсе алгоритмов, — это вытащить из частичного порядка линейный, не нарушив стрелок.

Соответствия и функции#

Отношение из $A$ в $B$ называют ещё соответствием. Каждому $a\in A$ соответствие ставит в пару подмножество $B$ — его образ. Соответствие, у которого образ каждого элемента состоит ровно из одного элемента, — это уже знакомая функция. Так что функция — частный случай отношения: $f\subseteq A\times B$, где у каждого $a$ ровно одна пара.

Функции делят по тому, насколько они «покрывают» $B$:

• Инъекция: разные элементы $A$ уходят в разные точки $B$ — никаких совпадений ($f(x)=x+1$ на $\mathbb{Z}$: сдвиг не склеивает значения)
• Сюръекция: каждый элемент $B$ чей-то образ — нет «брошенных» целей ($f(x)=x^2$ с $\mathbb{Z}$ на множество неотрицательных квадратов)
• Биекция: и то и другое — взаимно однозначное соответствие, у которого есть обратная функция ($f(x)=2x$ между чётными числами и всеми целыми)

Биекция — главный инструмент сравнения мощностей: два множества равномощны, если между ними есть биекция. Именно так доказывают, что натуральных чисел «столько же», сколько целых, и что существуют разные бесконечности. Конечный частный случай вы уже считали: биекция между $A$ и $B$ существует, когда $|A|=|B|$.

Свойства отношений понадобятся дальше повсюду: отношение достижимости в графах транзитивно, а кванторы, которыми записывают определения вроде $\forall a:aRa$, подробно разбираются в логике предикатов. Потренироваться в подсчёте вариантов полезно в тренажёре комбинаторики — там, в частности, встречаются задачи на разбиения множеств.