Теория категорий

Произведения и копроизведения

Как определить «пару объектов» без элементов? Категорная теория говорит: через связи с другими объектами. Произведение - это объект, из которого умеешь доставать компоненты, и других таких нет. Haskell tuples - произведения. Either - копроизведения. Monads - adjunctions. Каждый тип данных в функциональном программировании - категорная конструкция.

  • **Haskell/Rust/Swift алгебраические типы**: product types (record, tuple) и sum types (enum, Either) - это категорные произведения и копроизведения типов
  • **GraphQL query planning**: выполнение запроса соответствует вычислению предела в категории схем. JOIN в реляционных базах - произведение таблиц
  • **Типы данных как неподвижные точки**: наименьшая неподвижная точка функтора - инициальный объект в категории F-алгебр. Это определение List, Tree - через универсальное свойство

Предварительные знания

  • Естественные преобразования

Произведение

Что значит «пара» двух объектов в категории? Без элементов, без множеств, только через стрелки. 1945 год. Эйленберг и Маклейн не изучают объекты - они изучают **связи между объектами**. Произведение A x B - это объект P, из которого умеешь извлекать A и B. И при этом P - единственный такой объект в точности до изоморфизма. Не «содержит пары (a, b)» - а «имеет правильные стрелки».

**Произведение** объектов A и B - это объект P вместе с морфизмами p1: P → A и p2: P → B (проекциями), такими что для любого объекта X и морфизмов f: X → A, g: X → B существует единственный морфизм (f, g): X → P, для которого p1 о (f, g) = f и p2 о (f, g) = g.

КатегорияПроизведение A x BПроекции
**Set**Декартово произведение {(a,b)}p1(a,b)=a, p2(a,b)=b
**Grp**Прямое произведение группГомоморфизмы на компоненты
**Top**Произведение пространств (топология Тихонова)Непрерывные проекции
**Hask**Тип (a, b)fst, snd

Произведение единственно с точностью до **изоморфизма**: если P и P' - оба произведения A x B, то существует единственный изоморфизм P ≅ P'. Это ключевое свойство универсальных конструкций - они определяют объект «вплоть до изоморфизма», а не буквально единственным образом. Поэтому математики говорят: «произведение» как о конкретном объекте, хотя их может быть много - все изоморфны.

Произведение - это всегда декартово произведение множеств

Декартово произведение - лишь один пример. Произведение определяется своим универсальным свойством, и в разных категориях реализуется по-разному

В Grp произведение - прямое произведение групп (не просто множество пар). В Top - произведение топологий. В Pos - покомпонентный порядок. Одна конструкция, разные реализации - потому что определяем через морфизмы, а не элементы.

Что гарантирует универсальное свойство произведения A x B?

Копроизведение

Копроизведение - произведение «вверх ногами»: разворачиваем все стрелки. Произведение отвечает на вопрос «как **получить** компоненты из пары», копроизведение - «как **вложить** компоненты в сумму». В Haskell это Either a b. В REST API это `{ ok: T } | { error: E }`. В логике - дизъюнкция. Одна категорная конструкция, везде.

**Копроизведение** A + B - это объект C вместе с вложениями i1: A → C и i2: B → C, такими что для любого объекта X и морфизмов f: A → X, g: B → X существует единственный [f, g]: C → X, для которого [f, g] о i1 = f и [f, g] о i2 = g.

КатегорияКопроизведение A + BВложения
**Set**Дизъюнктное объединение A ⊔ Bi1(a) = (a,1), i2(b) = (b,2)
**Grp**Свободное произведение A * BКанонические вложения
**Ab**Прямая сумма A ⊕ Bi1(a)=(a,0), i2(b)=(0,b)
**Hask**Тип Either a bLeft, Right конструкторы

Произведение и копроизведение - **двойственные** конструкции. Двойственность в теории категорий: переворачиваем все стрелки (переходим в **противокатегорию** C^op), и одна конструкция становится другой. Каждая теорема о произведениях автоматически даёт теорему о копроизведениях. Это не просто симметрия - это способ доказывать теоремы бесплатно.

Тип Either a b в Haskell соответствует какой категорной конструкции?

Универсальное свойство

Почему одни математические определения «правильные», а другие нет? Теория категорий даёт критерий: правильное определение задаётся **универсальным свойством**. Вместо описания объекта по элементам - описание через связи с другими объектами. Плюс требование существования и единственности некоего морфизма. Это не просто эстетика - это механизм, который гарантирует каноничность конструкции.

**Универсальное свойство** - утверждение вида: «Существует объект U с морфизмами ..., такой что для любого объекта X с такими же данными существует единственный морфизм u: X → U (или U → X), согласованный с данными». Объект U называется **универсальным**.

Универсальное свойство определяет объект **единственно с точностью до единственного изоморфизма**. Если два объекта удовлетворяют одному универсальному свойству, они изоморфны и этот изоморфизм единственен. GraphQL query planning - вычисление пределов в категории схем. Free monads, least fixed points, greatest fixed points - всё это универсальные конструкции.

КонструкцияУниверсальное свойство
Произведение A x BФинальный объект в категории конусов над {A, B}
Копроизведение A + BНачальный объект в категории кококонусов над {A, B}
Терминальный объект 1Финальный объект категории
Инициальный объект 0Начальный объект категории
Уравнитель (Equalizer)Предел диаграммы A => B

Что означает фраза «объект задан универсальным свойством единственно с точностью до изоморфизма»?

Терминальный и инициальный объекты

Два «крайних» случая произведения и копроизведения. **Терминальный объект** - произведение пустого набора объектов: в него ведёт ровно один морфизм из любого объекта. **Инициальный объект** - копроизведение пустого набора: из него ведёт ровно один морфизм в любой объект. В Haskell: `()` (Unit) терминален, `Void` (never) инициален. Это не случайность - это теория категорий, объясняющая почему `absurd :: Void -> a` существует и единственна.

**Терминальный объект** 1 (или T): для любого A существует единственный морфизм !: A → 1. **Инициальный объект** 0 (или I): для любого A существует единственный морфизм: 0 → A. Оба определяются универсальным свойством и единственны с точностью до изоморфизма.

КатегорияТерминальный объектИнициальный объект
**Set**Одноэлементное множество {*}Пустое множество ∅
**Grp**Тривиальная группа {e}Тривиальная группа {e} (совпадают!)
**Ab**Нулевая группа {0}Нулевая группа {0} (нулевой объект)
**Hask**Тип () (Unit)Тип Void (never)

Когда терминальный и инициальный объекты совпадают, он называется **нулевым объектом**. В Grp и Ab тривиальная группа - одновременно инициальна и терминальна. Нулевой объект позволяет определить **нулевые морфизмы**: 0: A → B как композицию A → 0 → B. Элемент a объекта A - это морфизм 1 → A. Так теория категорий говорит об элементах без слова «элемент».

В каждой категории обязательно есть и терминальный, и инициальный объект

Ни терминальный, ни инициальный объект не обязан существовать. Их существование - дополнительное свойство категории

В категории, чьи объекты - натуральные числа > 0 с морфизмами «делители», нет ни инициального (нет числа, делящего все), ни терминального (нет числа, которое делится на все). Наличие этих объектов - свойство конкретной категории, не аксиома.

В категории Set что является инициальным объектом?

Ключевые идеи

  • **Произведение** A x B задаётся проекциями p1, p2 и универсальным свойством: любой «конус» над {A,B} единственным образом факторизуется через A x B
  • **Копроизведение** A + B двойственно произведению: вложения i1, i2 и любой «кококонус» факторизуется через A + B
  • **Универсальное свойство** определяет объект единственно с точностью до единственного изоморфизма - это каноничность конструкции
  • **Терминальный объект** 1 и **инициальный** 0 - крайние случаи произведений/копроизведений. В Haskell: Unit и Void
  • Произведение = product type (tuple, record). Копроизведение = sum type (Either, enum)

Связанные темы

Произведения и копроизведения - специальные случаи более общих конструкций:

  • Пределы и копределы — Произведение - частный случай предела; копроизведение - копредела. Следующий урок обобщает эти конструкции
  • Функторы — Функторы, сохраняющие произведения, называются декартово замкнутыми - фундамент теории типов

Вопросы для размышления

  • Почему в категории Grp копроизведение двух групп - это *свободное* произведение, а не прямое? Чем свободное произведение отличается от прямого?
  • Если 1 - терминальный объект, как через морфизмы 1 → A описать «выбор конкретного элемента» объекта A? Работает ли это в Top?
  • Найдите пример категории, в которой произведение существует, а копроизведение нет (или наоборот).

Связанные уроки

  • ct-03 — Естественные преобразования - язык универсальных свойств
  • ct-05 — Пределы и копределы обобщают произведения
  • ct-02 — Функторы, сохраняющие произведения - декартово-замкнутые категории
  • aa-04-rings — Прямые суммы и произведения колец - частный случай категорных конструкций
  • plt-07-algebraic-types
Произведения и копроизведения

0

1

Войти