Бинарные отношения

Определение

Бинарное отношение R на A — подмножество A×A. Пишем aRb или (a,b) ∈ R.

Свойства:

• Рефлексивность: aRa для всех a.
• Антирефлексивность: не aRa ни для какого a.
• Симметричность: aRb → bRa.
• Антисимметричность: aRb и bRa → a=b.
• Транзитивность: aRb и bRc → aRc.

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

Рефлексивное + симметричное + транзитивное = отношение эквивалентности (~).

Класс эквивалентности: [a] = {b: b~a}. Классы образуют разбиение A (попарно непересекающиеся, покрывают A).

Примеры: Равенство по модулю n: a ~ b ⟺ n | (a−b). Классы: {0, n, 2n,...}, {1, n+1, 2n+1,...}, ..., {n-1, 2n-1, ...}.

Конгруэнтность треугольников (по трём сторонам/углам).

Отношения порядка

Частичный порядок (poset): рефлексивное, антисимметричное, транзитивное. Пример: делимость на ℕ.

Линейный порядок: дополнительно сравнимость: для любых a,b: aRb или bRa. Пример: обычное ≤ на ℝ.

Наименьший элемент и инфимум: Минимальный ≠ наименьший (наименьший меньше всех, минимальный — нет большего). В частично упорядоченных множествах минимальных может быть несколько.

Диаграммы Хассе

Для конечных poset: точки — элементы, ребра снизу вверх — если a < b и нет c с a < c < b. Наглядное представление структуры порядка.

Булева решётка 2^{1,2,3}: все подмножества {1,2,3} с включением. 8 элементов. Диаграмма — куб.

Свойства отношений порядка: минимумы и максимумы

В частично упорядоченных множествах важно различать несколько понятий. Наименьший элемент (minimum) — элемент m, который меньше всех остальных: m ≤ x для всех x. Минимальный элемент — элемент m, меньше которого нет: не существует x < m. В линейном порядке это одно и то же, но в частичном — нет. Например, в poset {a, b, c} с a < c и b < c (но a и b несравнимы) элементы a и b оба минимальные, но ни один не является наименьшим.

Точная верхняя грань (sup, супремум) множества S — наименьший элемент, больший или равный всем элементам S. Точная нижняя грань (inf, инфимум) — наибольший из нижних граней. В поле ℝ с обычным порядком: sup{x : x² < 2} = √2 ∈ ℝ, хотя √2 ∉ ℚ — это один из способов построить вещественные числа из рациональных (дедекиндовы сечения).

Функции и их свойства

Функция f: A → B называется инъекцией (мономорфизмом), если f(a₁) = f(a₂) ⟹ a₁ = a₂ (разные элементы отображаются в разные). Сюръекцией (эпиморфизмом) — если для каждого b ∈ B существует a ∈ A с f(a) = b (образ совпадает с B). Биекцией — если одновременно инъекция и сюръекция. Биекция f: A → B означает |A| = |B|.

Число инъекций из n-элементного в m-элементное множество (m ≥ n): m!/(m−n)! = A(m,n) (размещения). Число сюръекций: Σₖ₌₀ᵐ (−1)ᵏ C(m,k)(m−k)ⁿ (формула включений-исключений). Число функций: mⁿ.

Применение теории отношений в информатике

Отношения порядка повсеместны в программировании. Тополо­гическая сортировка — линейное расширение частичного порядка (зависимости между задачами, compile-order в build-системах). Алгоритм Кана: итеративно извлекаем вершины с нулевой входящей степенью — работает за O(V + E). Если граф DAG (directed acyclic graph), это задаёт частичный порядок.

Отношения эквивалентности используются в теории типов и семантике языков программирования. Два выражения обсервационально эквивалентны, если ни один контекст программы не может их различить. Это отношение эквивалентности, и классы эквивалентности — «поведенческие типы» программ. В системах управления версиями (git) коммиты образуют частичный порядок по отношению «является предком»; операция merge вычисляет супремум двух веток.

Функции Эйлера и кольца вычетов

В число-теоретических приложениях отношения порядка и эквивалентности тесно связаны с арифметическими структурами. Функция Эйлера φ(n) = количество чисел от 1 до n, взаимно простых с n. Формула: φ(n) = n·∏_{p|n}(1 − 1/p). φ(p) = p−1 для простых. Теорема Эйлера: a^{φ(n)} ≡ 1 (mod n) при gcd(a,n)=1 — обобщение малой теоремы Ферма.

Кольцо вычетов ℤₙ = ℤ/nℤ — классы эквивалентности по модулю n. Группа единиц ℤₙ* = {a: gcd(a,n)=1} — мультипликативная группа порядка φ(n). Дискретный логарифм в ℤₙ* (задача: найти x при gₓ≡h mod p) — вычислительно трудная задача, лежащая в основе алгоритма Диффи-Хеллмана и DSA. RSA, в отличие от них, основан на задаче факторизации больших чисел, а не на дискретном логарифме.

Решётки и приложения к криптографии

Решётка (lattice) частично упорядоченное множество, в котором каждые два элемента имеют точные верхнюю и нижнюю грани. Булева алгебра — дистрибутивная решётка с дополнением. В криптографии: задача ближайшего вектора (CVP) и задача кратчайшего вектора (SVP) в целочисленных решётках — NP-трудные задачи, лежащие в основе постквантовой криптографии (алгоритм CRYSTALS-Kyber, стандартизированный NIST в 2024).

Численный пример: отношения эквивалентности и частичного порядка

Задача: (а) Проверить, что сравнение по mod 3 — отношение эквивалентности. (б) Является ли «делитель» порядком на {1,2,3,6}?

Шаг 1 (экв.): R = «a≡b(mod3)». Рефлексивность: 3|(a−a)=0 ✓. Симметрия: 3|(a−b) → 3|(b−a) ✓. Транзитивность: 3|(a−b), 3|(b−c) → 3|(a−c) ✓. R — отношение эквивалентности.

Шаг 2 (экв.): Классы: [0]={...,−3,0,3,6,...}, [1]={...,−2,1,4,...}, [2]={...,−1,2,5,...}. Фактор-множество ℤ/3ℤ={[0],[1],[2]}.

Шаг 3 (порядок): R=«a|b» на {1,2,3,6}: рефл.(a|a)✓, антисимм.(a|b,b|a→a=b для натур.)✓, транз.(1|2,2|6→1|6)✓. Частичный порядок.

Шаг 4: Диаграмма Хассе: 1→2→6 и 1→3→6. 2 и 3 несравнимы. Решётка: sup{2,3}=6, inf{2,3}=1. Линейных расширений: 2 (1,2,3,6 или 1,3,2,6). Связь с криптографией: решётки над ℤₙ моделируют задачи LWE (Learning With Errors) — основу Kyber.