Теория категорий
Пределы и копределы
PostgreSQL JOIN - это pullback. Git merge - это pushout. Ядро линейного отображения - это equalizer. Пределы и копределы - не абстракция ради абстракции. Это единый язык для операций, которые независимо появились в реляционных базах данных, системах контроля версий и линейной алгебре. Понять пределы - начать видеть одну структуру там, где раньше было три несвязанных инструмента.
- PostgreSQL JOIN: SELECT * FROM A JOIN B ON A.key = B.key - pullback таблиц над общим ключом
- Git merge: слияние двух веток над общим предком - pushout диаграммы A <- ancestor -> B
- TypeScript: A & B = pullback над терминальным объектом, Either<A,B> = копроизведение (coproduct)
- GraphQL: schema composition и query planning - вычисление пределов в категории схем
- Free monads: алгебраические эффекты в Haskell/Koka - копределы диаграмм функторов
Предварительные знания
Предел: универсальный сборщик диаграмм
1950е. Гротендик. Вместо изучения конкретных объектов - изучение диаграмм и их пределов. Создаёт язык, на котором написана половина современной алгебраической геометрии - и треть функционального программирования.
**Диаграмма** в категории C - это функтор F: J -> C из некоторой малой категории J. **Конус** над F - объект N с морфизмами psi_j: N -> F(j), согласованными со всеми морфизмами диаграммы. **Предел** lim F - терминальный конус: конус (L, phi_j), через который единственным образом факторизуется любой другой.
| Диаграмма J | Предел в Set | Название |
|---|---|---|
| Пустая | Одноэлементное множество {*} | Терминальный объект |
| Дискретная {*, *} | A x B (декартово произведение) | Произведение |
| A => B (два морфизма) | {a in A | f(a) = g(a)} | Уравнитель (equalizer) |
| A -> C <- B (cospan) | {(a,b) | f(a) = g(b)} | Расслоённое произведение (pullback) |
| Башня A0 <- A1 <- A2 <- ... | lim_{n} A_n | Проективный предел |
**Полнота**: категория полная (complete), если в ней существуют пределы всех малых диаграмм. Set, Grp, Top, Ab - все полные. Достаточно иметь произведения и уравнители: все остальные пределы строятся из них. Это теорема о полноте: completeness <=> (products + equalizers).
Equalizer морфизмов f, g: A -> B - это предел какой диаграммы?
Копредел: двойственность через переворот стрелок
Произведение, pullback, equalizer - три разные операции. Все три - частные случаи одного понятия: предела диаграммы. Теория категорий находит одну абстракцию там, где конкретная математика видит три несвязанных конструкции. Копредел - та же история, но с перевёрнутыми стрелками.
**Кококонус** над F: J -> C - объект N с морфизмами psi_j: F(j) -> N, согласованными с диаграммой. **Копредел** colim F - инициальный кококонус: любой другой кококонус единственным образом принимает морфизм из colim F. Предел собирает диаграмму 'сверху', копредел - 'снизу'.
| Диаграмма J | Копредел в Set | Название |
|---|---|---|
| Пустая | Пустое множество | Инициальный объект |
| Дискретная {*, *} | A ⊔ B (дизъюнктное объединение) | Копроизведение |
| A => B | B / (f(a) ~ g(a)) | Коуравнитель (coequalizer) |
| A <- C -> B (span) | A ⊔_C B (склейка вдоль C) | Pushout |
| Башня A0 -> A1 -> A2 -> ... | colim_{n} A_n | Индуктивный предел |
**Git merge как pushout**: два коммита A и B над общим предком C. Merge = pushout диаграммы A <- C -> B. Общий предок - подпространство C, ветви A и B - пространства с изменениями. Pushout 'склеивает' их, отождествляя изменения, пришедшие из одного источника. Конфликт слияния - когда склейка неоднозначна.
Категория кополная, если в ней существуют:
Вычисление пределов и применения
**Формула для пределов в Set**: lim F = { (x_j)_{j in J} | x_j in F(j), и F(alpha)(x_i) = x_j для всех alpha: i -> j }. Это согласованные семейства: выбираем элемент из каждого объекта диаграммы так, чтобы все морфизмы их 'связывали'. Pullback A x_C B - частный случай: согласованные пары (a, b) с f(a) = g(b).
**GraphQL как вычисление пределов**: query planning - это нахождение предела в категории схем данных. Каждое поле запроса - проекция из предела. Resolver - морфизм конуса. GraphQL schema composition буквально вычисляет pullback схем над общим типом.
| Система | Категорная конструкция | Объяснение |
|---|---|---|
| PostgreSQL JOIN | Pullback | Пары строк, совпадающих по ключу |
| Git merge | Pushout | Склейка двух веток над общим предком |
| ker(f) в линейной алгебре | Equalizer | Равенство f и нулевого морфизма |
| TypeScript A & B | Pullback над 1 | Тип в обоих A и B одновременно |
| Free monad | Копредел | colim(1 + F + F^2 + ...) |
| GraphQL composition | Предел схем | Согласованные проекции из запроса |
Пределы и копределы - это разные версии одной и той же операции
Копредел в C - это предел в противокатегории C^{op}
Двойственность - переворот всех стрелок. Предел (конус сходится к вершине) -> копредел (кококонус расходится из вершины). Каждая теорема о пределах автоматически даёт двойственную теорему о копределах. Это главный инструмент теории категорий: доказать для пределов, получить для копределов бесплатно.
Pullback A x_C B - это предел какой диаграммы?
Ключевые идеи
- Предел = терминальный конус над диаграммой. Обобщает произведения, equalizers, pullbacks
- Копредел = инициальный кококонус. Обобщает копроизведения, coequalizers, pushouts
- Equalizer: {a | f(a) = g(a)} - выделяет точки совпадения; всегда мономорфизм
- Pullback A x_C B: пары (a,b) с f(a)=g(b) - 'пересечение' над C
- Pushout A ⊔_C B: склейка A и B вдоль C - 'объединение' с отождествлением
- Копредел в C = предел в C^{op}: двойственность даёт теоремы о копределах бесплатно
Что дальше
Сопряжённые функторы объясняют, почему правый сопряжённый сохраняет пределы - фундаментальный факт теории категорий.
- Сопряжённые функторы — Правый сопряжённый сохраняет пределы; левый - копределы. Следует из определений
- Произведения и копроизведения — Произведение = предел дискретной диаграммы; копроизведение - её копредел
Вопросы для размышления
- Как выразить пересечение A cap B подмножеств C через pullback? Построить диаграмму включений A -> C <- B и описать её предел.
- Git merge как pushout: что такое 'общий предок' категорно? Что происходит при конфликте - когда pushout неоднозначен?
- Почему теорема 'правый сопряжённый сохраняет пределы' следует из определений, а не требует отдельного доказательства?
Связанные уроки
- ct-04 — Произведение и копроизведение - частные случаи пределов
- ct-06 — Правый сопряжённый сохраняет пределы, левый - копределы
- aa-04-rings — Ядро и образ в кольцах - equalizer и coequalizer
- db-02-relational-model — JOIN в реляционных БД - pullback таблиц над общим ключом
- la-01-vectors-intro — Ядро линейного отображения - equalizer с нулевым морфизмом
- aa-12-modules
- ml-07