В абстрактной алгебре одна из первых реально важных идей такова: иногда разные с виду объекты удобно считать “одинаковыми” — не вообще, а в рамках выбранного правила. Для этого вводится отношение эквивалентности (equivalence relation).
Это не просто формальная академическая муть. Эта идея потом постоянно всплывает в криптографии и zero-knowledge в записях типа:
Z/nZ
F_p
G/H
На первый взгляд блок про эквивалентность кажется простым и почти философским, но это важный кирпич. Без него потом сложнее понимать, что вообще означает запись типа Z/5Z или почему математик говорит “это не число 2, а класс [2]”.
Эквивалентность — это “равенство по выбранному правилу”
Как известно, обычное равенство (equality) говорит:
a = b
То есть a и b — это буквально одно и то же. Спасибо, Кэп.
Но в математике часто нужно более гибкое понятие. Поэтому вводим эквивалентность (equivalence):
a ~ b
Да, вот с такой тильдой. Это означает: a и b считаются одинаковыми по выбранному правилу.
Эквивалентность — это не обязательно обычное равенство (equality). Это “одинаковость” по какому-то выбранному признаку.
Пример с modulo arithmetic
В обычной арифметике:
2 != 7
Очевидным образом, 2 — это не 7.
Но что если взять их по модулю 5?
2 mod 5 = 2
7 mod 5 = 2
Или, если записать иначе:
5 | (7 - 2)
То есть, “7 минус 2 делится на 5”.
Следовательно, в странном мире, где мы рассматриваем числа по модулю 5, число 2 будет эквивалентно 7 или, говоря точнее, конгруэнтно:
2 ≡ 7 (mod 5)
Вот этот знак равенства с лишней палочкой означает “конгруэнтно”, что является частным случаем эквивалентности. Потом можно продемонстрировать свою эрудицию в компании друзей.
Отношение эквивалентности
Пусть существует множество, обозначенное как S.
Множество (set) — это просто набор объектов. Обычно множество записывают так:
S = {1,2,3}
Такое множество S содержит элементы 1, 2 и 3. Элементы множества записываются в фигурных скобках. Соответственно, элементы могут принадлежать (∈) и не принадлежать (∉) множеству. Короче, множество — это просто коробка с объектами.
Отношение эквивалентности (equivalence relation) на множестве S — это правило, которое говорит, какие элементы из S считаются эквивалентными.
Обычно это записывают так:
a ~ b
То есть “a эквивалентно b”.
Чтобы отношение было именно отношением эквивалентности (equivalence relation), оно должно иметь три свойства:
- рефлексивность (reflexivity);
- симметричность (symmetry);
- транзитивность (transitivity).
Эти три свойства нужны, чтобы наше “считать одинаковыми” не превращалось в кривое нечто.
Рефлексивность (Reflexivity)
Для любого элемента a ∈ S, элемент a должен быть эквивалентен самому себе:
a ~ a
Например:
7 ≡ 7 (mod 5)
Логично. Если правило “одинаковости” даже не считает объект одинаковым самому себе — это уже не нормальная эквивалентность.
Симметричность (Symmetry)
Если a эквивалентно b, то b эквивалентно a.
a ~ b => b ~ a
Например, если:
7 ≡ 2 (mod 5)
Тогда:
2 ≡ 7 (mod 5)
Если отношение работает только в одну сторону, это уже не “одинаковость”, а что-то другое.
Например, отношение “быть предком” симметричным не является. Если дед — предок внука, это не значит, что внук — предок деда (в мире нормальных людей). Поэтому “быть предком” — не отношение эквивалентности (equivalence relation).
Транзитивность (Transitivity)
Если a эквивалентно b, а b эквивалентно c, то a эквивалентно c:
a ~ b,
b ~ c
=> a ~ c
Короче, если a в одной куче с b, а b в одной куче с c, то a тоже должен быть в одной куче с c.
Например если имеем:
2 ≡ 7 (mod 5)
7 ≡ 12 (mod 5)
Значит:
2 ≡ 12 (mod 5)
Почему? Потому что все три числа дают один и тот же остаток при делении на 5.
Класс эквивалентности (Equivalence Class)
Теперь самая важная штука после самого отношения.
Если у нас есть отношение эквивалентности (equivalence relation) ∼ на множестве S, то для любого элемента a ∈ S можно определить его класс эквивалентности (equivalence class):
[a] = { x in S | x ~ a }
Читается так: “класс эквивалентности элемента a — это множество всех элементов x, которые эквивалентны a”. То есть [a] — это вся куча объектов, которые по нашему правилу считаются такими же, как a.
Пример по модулю 5:
[2] = { ..., -8, -3, 2, 7, 12, 17, ... }
Почему все эти числа в одном классе? Потому что каждое из них даёт остаток 2 при делении на 5.
Представитель класса (Representative)
Когда мы пишем:
[2]
Число 2 здесь играет роль представителя класса (representative).
Но тот же самый класс можно обозначить и через другое число из этой же кучки:
[2] = [7] = [12] = [-3]
Потому что все эти числа эквивалентны друг другу по модулю 5.
Класс эквивалентности (equivalence class) — это сама куча, а представитель (representative) — просто удобный элемент, через который мы называем эту кучу.
То есть [2] — это не “число 2”. Это целый набор чисел, которые дают остаток 2. Просто для удобства мы называем этот класс через самого простого представителя — 2.
Разбиение множества (Partition)
Разбиение множества (partition of a set) S — это набор непустых, непересекающихся подмножеств (nonempty disjoint subsets), объединение которых даёт всё множество S.
Смысл простой: мы разложили все элементы множества по коробкам так, что каждый элемент попал ровно в одну коробку.
Partition — это набор подмножеств (subsets), который:
- покрывает всё множество (their union is S);
- части не пересекаются (disjoint);
- части непустые (nonempty).
Пример partition
Пусть:
S = {1,2,3,4,5,6}
Можно разбить S на чётные и нечётные:
{ {1,3,5}, {2,4,6} }
Это именно разбиение, потому что:
- обе части непустые;
- они не пересекаются;
- вместе они дают всё множество
S.
Что не является разбиением
Например:
{ {1,2}, {2,3}, {4,5,6} }
Это не partition, потому что число 2 лежит сразу в двух подмножествах. То есть “коробки” пересекаются.
Вот это тоже не partition:
{ {1,2}, {3,4} }
Потому что элементы 5 и 6 потерялись, если мы считаем, что изначальное множество было {1,2,3,4,5,6}.
Главная теорема: классы эквивалентности образуют разбиение
Классы эквивалентности (equivalence classes) отношения эквивалентности (equivalence relation) на множестве
Sобразуют разбиение (partition) множестваS.
И наоборот:
Для любого разбиения (partition) множества
Sсуществует отношение эквивалентности (equivalence relation), классы которого являются элементами этого разбиения.
На человеческом языке:
Отношение эквивалентности (equivalence relation) и разбиение множества (partition) — это одна и та же идея, просто с двух разных сторон.
Одна “сторона” теоремы — это правило: a ~ b. То есть a и b считаются одинаковыми.
Другая сторона — это кучки:
S=A1 ∪ A2 ∪ A3 ∪ ...
где каждый элемент лежит ровно в одной кучке.
Первая “сторона” теоремы: equivalence relation → partition
Если у нас есть отношение эквивалентности (equivalence relation), то оно автоматически разбивает множество на классы эквивалентности (equivalence classes).
Пример:
a ~ b <=> a ≡ b (mod 5)
То есть a эквивалентно b, если они дают одинаковый остаток при делении на 5.
Тогда все целые числа (Z) разбиваются на 5 классов:
[0]
[1]
[2]
[3]
[4]
Эти классы образуют разбиение (partition) множества целых чисел Z. Почему? Потому что любое целое число при делении на 5 даёт ровно один остаток: 0, либо 1, 2, 3 или 4.
Почему классы не пересекаются
Очень важная мысль:
Два класса эквивалентности (equivalence classes) либо вообще не пересекаются, либо полностью совпадают.
Допустим, есть два класса эквивалентности:
x in [a]
x in [b]
И допустим, они пересеклись. Это значит, что существует элемент x, который лежит в обоих классах:
x ∈ [a]
x ∈ [b]
Что это значит? Если x ∈ [a], то x ~ a.
Если: x ∈ [b], то x ~ b.
Теперь используем симметричность (symmetry):
x ∼ a => a ∼ x
И затем транзитивность (transitivity):
a ~ x
x ~ b
Значит:
a ~ b
А если a ∼ b, то классы [a] и [b] — это один и тот же класс:
[a] = [b]
Вывод:
Если два класса эквивалентности имеют хотя бы один общий элемент, значит это не два разных класса, а один и тот же класс.
Вторая сторона теоремы: partition → equivalence relation
Теперь наоборот. Если у нас уже есть разбиение множества (partition), то из него можно построить отношение эквивалентности (equivalence relation).
Берём множество и partition:
S = {1,2,3,4,5,6}
{ {1,3,5}, {2,4,6} }
То есть одна куча — нечётные, другая — чётные. Теперь можно определить отношение:
a ~ b
если a и b лежат в одной и той же куче.
Например:
1 ~ 3
2 ~ 6
но:
1 !~ 2
потому что 1 и 2 лежат в разных кучках.
Это отношение будет отношением эквивалентности (equivalence relation). Почему? Проверяем три свойства.
Рефлексивность (Reflexivity)
Любой элемент лежит в той же кучке, что и он сам.
3 ~ 3
Симметричность (Symmetry)
Если a лежит в той же кучке, что и b, то b лежит в той же кучке, что и a:
1 ~ 5
5 ~ 1
Транзитивность (Transitivity)
Если a лежит в той же кучке, что и b, а b лежит в той же кучке, что и c, то a лежит в той же кучке, что и c.
Если:
1 ~ 3
3 ~ 5
Значит:
1 ~ 5
Так что любое разбиение (partition) автоматически задаёт отношение эквивалентности (equivalence relation).
Главная идея теоремы
Эта теорема говорит:
Отношение эквивалентности (equivalence relation) и разбиение множества (partition) — это по сути одно и то же.
Просто:
- equivalence relation — это правило;
- partition — это результат применения правила.
Или ещё короче:
- Equivalence relation — это логика “одинаковости”.
- Partition — это геометрия этой “одинаковости”.
Если есть правило “кого считать одинаковыми”, оно разбивает множество на классы. Если есть разбиение на классы, оно задаёт правило: “одинаковыми считаются те, кто лежит в одном классе”.
В итоге
- Отношение эквивалентности (equivalence relation) — это способ сказать: “эти штуки разные, но для нашей задачи мы считаем их одинаковыми.”
- Класс эквивалентности (equivalence class) — это: “вся куча штук, которые считаются одинаковыми.”
- Разбиение (partition) — это: “всё множество разложено на такие кучки без пересечений и потерь.”
- Главная теорема: “любая нормальная эквивалентность режет множество на кучки; любая нормальная нарезка на кучки задаёт эквивалентность”.
Образ для запоминания
Можно использовать такой образ: есть огромное множество объектов, например, все целые числа Z. Мы вводим правило:
Числа считаются одинаковыми, если дают один и тот же остаток при делении на
5.
Это отношение эквивалентности (equivalence relation). Оно раскладывает все числа по коробкам:
[0]
[1]
[2]
[3]
[4]
Это разбиение (partition).
Потом мы перестаём смотреть на отдельные числа и начинаем работать с коробками как с новыми объектами. Это и есть запись вида:
Z/5Z
Если модуль p — простое число, то Z/pZ является конечным полем (finite field), обычно его обозначают F_p.
F_5
И именно на таких конечных полях (finite fields) строится куча crypto и zero knowledge математики.
Если же модуль составной, например 6, то Z/6Z обычно является кольцом (ring), но не полем (field), потому что не у каждого ненулевого элемента есть обратный.
Что же такое такое Z/nZ
Запись:
Z/nZ
строго говоря означает:
{[0], [1], ..., [n-1]}
То есть множество классов эквивалентности (set of equivalence classes).
Учтите, что символ / в записи Z/nZ — это не обычное деление. Это quotient construction, то есть переход от исходного множества/структуры к классам эквивалентности. Грубо говоря, мы берём все целые числа Z, склеиваем числа с одинаковыми остатками по модулю n, и получаем новое множество классов.
Конечное поле (Finite Field)
Если p — простое число (prime number):
F_p = Z/pZ
Это конечное поле (finite field).
Почему это важно для crypto / zk
В zero knowledge и криптографии вычисления часто происходят внутри:
F_p
То есть арифметика идёт не над обычными integers, а над finite field.
Например:
a + b = c
часто означает:
a + b ≡ c (mod p)