Теория категорий
Сопряжённые функторы
Что общего между curry/uncurry в Haskell, теоремой Галуа из алгебры, тензорным произведением модулей и суспензией в топологии? Все они - примеры сопряжённых функторов. Это «самое важное открытие теории категорий» (Маклейн) - универсальная симметрия между «строить структуру» и «забывать структуру».
- **Curry/uncurry**: сопряжение (A × -) ⊣ (A → -) - основа функционального программирования и лямбда-исчисления. Каждый язык с замыканиями реализует это сопряжение
- **Абстрактная интерпретация**: статические анализаторы (Coverity, Facebook Infer) используют галуа-связи для звукового анализа программ. Абстрактный и конкретный домены - сопряжённые функторы
- **Квантовая механика**: сопряжение между операторами в гильбертовом пространстве. Эрмитово сопряжение A* - левый сопряжённый к A относительно скалярного произведения
Предварительные знания
Сопряжение
Маклейн сказал: «Сопряжения встречаются повсюду». Это не преувеличение - сопряжённые функторы объединяют десятки фундаментальных конструкций математики: свободные и забывающие функторы, тензорное произведение и пространство Hom, квантование и классический предел, синтаксис и семантику. Понять сопряжение - значит понять глубинную симметрию между «построить» и «забыть».
Функторы F: C → D и G: D → C называются **сопряжёнными** (F ⊣ G, «F левый сопряжённый к G»), если для любых A ∈ C и B ∈ D существует естественная биекция: Hom_D(F(A), B) ≅ Hom_C(A, G(B)). Это биекция **естественная** - то есть функториально зависит от A и B.
Интуиция: левый сопряжённый F «строит» объект из компонентов (свободная конструкция), правый G «забывает» структуру. Морфизм из свободного объекта F(A) в B - это то же самое, что морфизм из A в объект G(B) с меньшей структурой. Это принцип «расширения по определению»: чтобы задать гомоморфизм из свободного объекта, достаточно задать его на порождающих.
| Левый сопряжённый F | Правый сопряжённый G | Биекция |
|---|---|---|
| Свободная группа F(S) | Забывающий функтор |·| | Hom_Grp(F(S), G) ≅ Hom_Set(S, |G|) |
| Свободный модуль A⊗_ℤ- | Hom(A, -) | Hom(A⊗B, C) ≅ Hom(B, Hom(A,C)) |
| Дискретная топология | Забывающий Top → Set | Непр. отображения ↔ все функции |
| Суспензия ΣX | Пространство петель ΩX | Map(ΣX, Y) ≅ Map(X, ΩY) |
| Curry: (- × A) | Экспоненциал (A → -) | Hom(B×A, C) ≅ Hom(B, C^A) |
Открытие сопряжений
Дэниэл Кан ввёл понятие сопряжённых функторов в 1958 году. Он заметил, что многие конструкции приходят парами: свободное и забывающее, тензорное произведение и внутренний Hom, прямой образ и обратный образ. Статья Кана «Adjoint functors» показала, что все эти пары - одно и то же явление. Маклейн впоследствии назвал это «самым важным открытием в теории категорий».
Если F ⊣ G - сопряжение, что означает биекция Hom_D(F(A), B) ≅ Hom_C(A, G(B))?
Единица и коединица
Сопряжение можно задать не биекцией, а двумя естественными преобразованиями: **единицей** η: Id_C → G ∘ F и **коединицей** ε: F ∘ G → Id_D. Единица «вложит» A в G(F(A)) - объект G(B) при B = F(A). Коединица «применит» F к G(B) и «свернёт» обратно в B. Вместе они задают треугольные тождества.
Сопряжение F ⊣ G эквивалентно наличию естественных преобразований η: Id_C ⇒ G ∘ F и ε: F ∘ G ⇒ Id_D, удовлетворяющих **треугольным тождествам**: (ε_F) ∘ (F_η) = Id_F и (G_ε) ∘ (η_G) = Id_G.
Биекция φ из определения сопряжения выражается через единицу и коединицу: **φ(f: F(A) → B) = G(f) ∘ η_A** и **φ⁻¹(g: A → G(B)) = ε_B ∘ F(g)**. Это показывает эквивалентность двух определений. На практике удобнее работать с η и ε - они конкретные морфизмы, а не биекция на hom-множествах.
Важное следствие: **монада**. Если F ⊣ G, то T = G ∘ F - это монада на C. Единица монады - это η: Id → T, умножение монады - G ∘ ε ∘ F: T² = G∘F∘G∘F → G∘F = T. Так сопряжения рождают монады - и каждая монада рождается из некоторого сопряжения (теорема Клейсли-Эйленберга-Мура).
Единица η: Id_C → G ∘ F сопряжения F ⊣ G - это:
Свободный и забывающий функтор
Самый распространённый пример сопряжения в алгебре - пара «свободный ⊣ забывающий». Забывающий функтор U: Grp → Set «забывает» групповую структуру и возвращает только множество. Его левый сопряжённый F: Set → Grp строит **свободную группу** над множеством - «наименее обязывающую» группу, порождённую элементами множества.
**Забывающий функтор** U: Struct → Set отображает каждый структурированный объект в его носитель (underlying set). Его левый сопряжённый F: Set → Struct строит **свободную структуру** над множеством. Сопряжение: Hom_Struct(F(S), X) ≅ Hom_Set(S, U(X)) - задать гомоморфизм из свободного объекта равносильно заданию функции на порождающих.
| Свободный функтор F | Категория | Пример F(S) |
|---|---|---|
| Свободная группа | Grp | Слова над S ∪ S⁻¹ с сокращениями |
| Свободный моноид | Mon | Список элементов S (S*) |
| Свободный модуль | Mod_R | Формальные суммы Σ rᵢsᵢ |
| Свободный граф | Graph | Граф с вершинами S и нет рёбер |
| Дискретное пространство | Top | Топология всех подмножеств |
Свободные объекты - это «канонические представители» без лишних соотношений. Свободная группа над двумя элементами {a, b} содержит все слова вида aab⁻¹a..., без каких-либо тождеств, кроме тех, что следуют из аксиом группы. Любая группа - это образ некоторой свободной группы по гомоморфизму (то есть задаётся порождающими и соотношениями).
Почему достаточно задать функцию f: S → U(M), чтобы определить гомоморфизм групп F(S) → M?
Связь Галуа
Одним из первых исторических примеров сопряжения была теория Галуа - задолго до того, как её так назвали. Связь Галуа между подгруппами группы Галуа и подполями расширения поля - это сопряжение между категориями, упорядоченными включением. В 1940-х Биркгоф назвал это «galois connection» - галуа-связью.
**Галуа-связь** между двумя частично упорядоченными множествами (P, ≤) и (Q, ≤) - это пара монотонных функций f: P → Q и g: Q → P таких, что f(a) ≤ b ⟺ a ≤ g(b). Это ровно сопряжение в категориях Pos. Такие пары называются «антитонными галуа-связями», если порядок один обращается.
Галуа-связи встречаются в программировании: в **абстрактной интерпретации** (метод статического анализа) - пара «конкретизация / абстракция». Конкретный домен (программные состояния) и абстрактный домен (интервалы, знаки чисел) связаны галуа-связью. Это позволяет строить звуковые (sound) статические анализаторы.
| Пример | f (левый) | g (правый) | Биекция |
|---|---|---|---|
| Теория Галуа | F ↦ Aut(L/F) | H ↦ L^H | F ⊆ g(H) ⟺ f(F) ⊇ H |
| Абстрактная интерп. | Абстракция α | Конкретизация γ | α(c) ≤ a ⟺ c ≤ γ(a) |
| Концептуальный анализ | Предметы ↦ признаки | Признаки ↦ предметы | Замыкание Галуа |
Сопряжённые функторы - это то же самое, что взаимно обратные функторы
Обратные функторы дают изоморфизм категорий (G ∘ F ≅ Id, F ∘ G ≅ Id). Сопряжение слабее: только η: Id → G∘F и ε: F∘G → Id без требования быть изоморфизмами
Классический пример: свободная группа F(S) и забывающий функтор U. U ∘ F(S) - это носитель свободной группы над S, что намного больше S. Обратного изоморфизма нет, но сопряжение есть. Изоморфизм - частный случай эквивалентности категорий, которая сильнее сопряжения.
Галуа-связь f ⊣ g между Pos - это частный случай чего?
Ключевые идеи
- **Сопряжение** F ⊣ G - естественная биекция Hom(F(A), B) ≅ Hom(A, G(B)); левый сопряжённый «строит», правый «забывает»
- **Единица** η: Id → G∘F и **коединица** ε: F∘G → Id задают сопряжение через треугольные тождества
- **Свободный ⊣ забывающий** - главный пример: задать гомоморфизм из свободного объекта = задать функцию на порождающих
- **Галуа-связь** - сопряжение в Pos-категориях; встречается в теории полей, абстрактной интерпретации, концептуальном анализе
Связанные темы
Сопряжения - фундамент для многих конструкций:
- Монады — Каждое сопряжение F ⊣ G порождает монаду T = G∘F. Обратно - каждая монада происходит из сопряжения (Клейсли или Эйленберг-Мур)
- Пределы и копределы — Правый сопряжённый сохраняет пределы; левый - копределы. Это следствие сопряжения
Вопросы для размышления
- Curry/uncurry - это сопряжение (A×-) ⊣ (A→-). Напишите явно единицу η и коединицу ε этого сопряжения и проверьте треугольные тождества.
- Почему правый сопряжённый функтор сохраняет пределы? Попробуйте вывести это из определения сопряжения через биекцию Hom-множеств.
- Найдите сопряжение в своём любимом языке программирования. Подсказка: ищите пары операций, где одна «упрощает», а другая «обогащает».