15 подписчиков

Галактика знаний - 1005 - Категории – первые шаги по гравитационной сети

27 апреля27 апр

32 мин

«Категория — это граф, в котором у каждой стрелки есть имя, и стрелки можно склеивать, если голова одной совпадает с хвостом другой.»

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

Оглавление

0. Зачем нам категории? (мотивационное вступление)
1. Что такое категория? (определение частями)
1.1 Объекты и стрелки

«Категория — это граф, в котором у каждой стрелки есть имя, и стрелки можно склеивать, если голова одной совпадает с хвостом другой.»
— вольный пересказ определений

В качестве приложения к этой статье я добавляю её полный исходный текст с разметкой. Поскольку платформа Дзен не поддерживает сложные формулы, я вынужден вставлять их в виде картинок, что может затруднять чтение. Вы можете скопировать этот исходник в любой современный ИИ и задавать любые вопросы, адаптировать изложение под свой уровень или просто прояснять непонятные места. Используйте эту возможность, чтобы сделать изучение материала максимально комфортным и персонализированным.

0. Зачем нам категории? (мотивационное вступление)

Представьте, что вы строите единую карту всех научных знаний. Вы замечаете, что связи между объектами в физике, программировании и логике устроены удивительно похоже: везде можно идти по цепочкам преобразований и всегда есть способ «остаться на месте». Теория категорий даёт универсальный язык для описания таких карт — это гравитация, удерживающая вместе галактику идей. На предыдущих уроках мы собрали три кита: множества (объекты), функции (связи между ними) и логику (правила истинности). Пришло время объединить их в единую структуру — категорию.

Категория не заменяет математику, а служит её связующим каркасом. Она позволяет переносить интуицию из одной области в другую: например, композиция функций в программировании и логический вывод — это одно и то же с категориальной точки зрения. Этот урок откроет вам базовую грамматику языка категорий, после чего вы сможете описывать системы любой природы. Мы начнём с простого определения, разберём ключевой пример Set, а затем научимся рисовать и программировать маленькие категории.

Сегодня вы узнаете, что любая научная дисциплина порождает свою категорию, и это не абстракция, а практический способ видеть общее в разном. Мы сделаем первый шаг по гравитационной сети, которая свяжет всё, что вы уже знаете, с тем, что узнаете в будущем. В следующих разделах мы аккуратно соберём определение из кирпичиков, рассмотрим примеры и сразу опробуем идеи в коде. А также затронем такие понятия, как изоморфизм, группа и коммутативные диаграммы, которые станут для нас главным инструментом мышления.

1. Что такое категория? (определение частями)

Прежде чем дать полное определение, разберём его на составляющие. Каждая часть важна сама по себе, и понимание приходит через аналогии.

1.1 Объекты и стрелки

В любой категории есть объекты — это «вещи», «сущности», «позиции». В категории множеств Set объектами являются множества. В других категориях объектами могут быть группы, векторные пространства, типы данных в программе или состояния физической системы. Объекты сами по себе статичны; жизнь категории создают связи между ними.

Представьте объекты как площади города, а стрелки — как дороги, по которым можно проехать с одной площади на другую. Одна и та же пара площадей может быть соединена несколькими разными дорогами — именно поэтому в категории может быть много стрелок между двумя объектами. Эта множественность связей чрезвычайно важна для моделирования реальных ситуаций, где одно и то же превращение можно осуществить разными способами.

1.2 Композиция стрелок

Продолжая дорожную аналогию: если вы доедете от A до B по одной дороге и от B до C по другой, то всегда получите путь от A до C, независимо от того, будете ли вы мысленно группировать отрезки. Именно ассоциативность позволяет нам думать о сложных преобразованиях как о последовательности простых шагов, не заботясь о скобках. Это фундаментальное свойство, которое мы позже проверим в программной модели.

1.3 Тождественные стрелки

Без тождественных стрелок мы не смогли бы говорить об объектах как о самостоятельных сущностях. Каждый объект обязан иметь такую петлю самовозвращения. В наших моделях мы всегда будем явно указывать или подразумевать их наличие.

1.4 Полное определение

При этом должны выполняться две аксиомы: ассоциативность композиции и нейтральность тождественных стрелок, как описано выше. Заметим, что в этом курсе мы работаем с локально малыми категориями: стрелки между любыми двумя объектами образуют множество, а совокупность всех объектов может быть классом (слишком большой, чтобы быть множеством). Это избавляет нас от теоретико‑множественных парадоксов, но для практики достаточно интуитивного понимания.

2. Первый и главный пример: категория Set

Каждый раз, когда вы пишете программу, преобразующую данные, или рассуждаете о функциях, вы неявно находитесь внутри Set. Понимание того, что это категория, даёт нам право использовать геометрические и алгебраические интуиции. Например, коммутативные диаграммы в Set — это просто утверждения о равенстве композиций функций. Мы будем постоянно возвращаться к этому примеру.

Важно, что в Set между двумя множествами может быть очень много разных функций. Это оправдывает общее определение категории, где стрелок больше одной. Именно множественность связей отражает богатство математических и реальных ситуаций.

3. Дискретная категория

Зачем нужна такая бедная структура? Она моделирует ситуации, где есть отдельные независимые сущности без какого‑либо взаимодействия. Например, в базе данных можно рассматривать таблицы как объекты, и до реализации связей база представляет собой дискретную категорию. В будущем функторы из дискретной категории будут соответствовать выбору набора объектов.

Проверьте себя: если в дискретной категории пять объектов, сколько всего в ней стрелок? (Ответ: пять тождественных.) Это простейший, но концептуально важный случай. Позже мы увидим, что функтор из дискретной категории в Set — это просто выбор множеств, индексированных объектами, без каких-либо дополнительных условий на стрелки.

4. Категория-порядок (предпорядок) и транзитивные отношения

5. Моноид как категория с одним объектом

Более близкий программистам пример — строки с операцией конкатенации. Объект по‑прежнему один, а стрелки — строки. Композиция строк — их склеивание, нейтральный элемент — пустая строка. Мы уже видели моноиды в уроке про логику: операции И и ИЛИ с True/False — это тоже моноиды, но теперь мы понимаем, что они являются категориями с одним объектом.

6. Группа как категория, где все стрелки — изоморфизмы

7. Изоморфизмы: не просто стрелки туда-обратно

8. Коммутативные диаграммы

Коммутативные диаграммы — не просто иллюстрация, а формальный язык утверждений. Аксиома ассоциативности выражается коммутативностью четырёхугольника (или пятиугольника) для любых трёх совместимых стрелок. Изображая диаграмму, мы можем не выписывать громоздкие равенства, а полагаться на визуальную интуицию.

На практике, когда мы строим категорию вручную (как в нашем классе Category), мы тем самым объявляем некоторые диаграммы коммутативными. Задавая set_composition("f", "g", "h"), мы утверждаем коммутативность треугольника. Если позже добавляем стрелки и новые композиции, мы расширяем набор коммутативных диаграмм. Таким образом, категория может быть описана как набор образующих стрелок и соотношений (равенств композиций), что в точности соответствует заданию коммутативных диаграмм.

Коммутативные диаграммы удобны ещё и тем, что они сохраняются функторами. Если функтор отображает одну категорию в другую, коммутативная диаграмма переходит в коммутативную. Поэтому многие универсальные конструкции (произведения, копроизведения) определяются как требования коммутативности определённых диаграмм. Мы вернёмся к этому в следующих уроках.

9. Категории вокруг нас (первые примеры из науки)

Теперь, вооружённые определением, мы можем заглянуть в разные науки и мгновенно опознать там категории. Это первый взгляд, который мы развернём в следующих уроках. В физике объектами могут выступать состояния системы, а стрелками — переходы между ними за определённый промежуток времени. Композиция двух переходов за секунду и за две секунды даёт переход за три секунды, а тождественная стрелка — нулевой промежуток времени без изменений. Такая категория кодирует динамику.

В программировании типы данных являются объектами, а чистые функции — стрелками. Композиция функций — это просто последовательный вызов, тождественная функция — x => x. Эта категория известна как Hask (с оговорками про ленивость и undefined, но для нас это полноценный пример). Когда вы пишете конвейер преобразований в функциональном стиле, вы строите стрелки в этой категории.

Лингвистика предлагает категорию, где слова — это объекты особого вида (грамматические типы), а связи — синтаксические и семантические преобразования. Например, в модели DisCoCat предложение собирается как композиция стрелок, соответствующих словам. Мы ещё не раз убедимся, что категории повсюду, и это главная сила нашего нового языка.

Обратите внимание: каждая из этих областей привносит свои особенности, но структура взаимодействия одна и та же. Именно это и позволяет переносить интуицию: то, что вы поняли про композицию в программировании, будет работать и в физических рассуждениях. Теория категорий делает связи видимыми.

10. Программирование: моделируем маленькую категорию вручную

Теперь создадим работающий класс, который представляет категорию с конечным числом объектов и стрелок, задаваемых явно. Мы не будем пытаться автоматически замыкать стрелки — как показала практика, для циклических графов это может привести к бесконечному циклу. Вместо этого мы будем руками добавлять все необходимые композиции и тождественные стрелки, в точности следуя аксиомам.

Построим конкретную маленькую категорию с тремя объектами и стрелками:

Этот код наглядно показывает, что категория требует явного задания всех композиций и тождеств. Так мы строим категорию с соотношениями, избегая бесконечных замыканий. Если мы захотим добавить циклические стрелки, как в категории с двумя объектами True и False и стрелками not и const True, мы можем добавить их и вручную назначить композиции. Это полностью контролируемый процесс.

11. Задания для самообучения

Каждое задание снабжено подсказкой, чтобы вы могли справиться даже в затруднительной ситуации. Выполнение этих упражнений закрепит ваше понимание и подготовит к следующему уроку о функторах.

12. Резюме

Категория состоит из объектов и стрелок с операцией композиции, которая ассоциативна и имеет тождественные стрелки для каждого объекта. Это минимальный каркас для описания любых направленных связей.
Set — категория множеств и функций, наш первый и главный пример. Дискретная категория лишена связей между разными объектами, категория-порядок содержит не более одной стрелки между парой (предпорядок). Антитранзитивные отношения дают диаграммы Хассе.
Моноид — категория с одним объектом, где композицией служит ассоциативная операция с единицей. Примеры: числа со сложением, строки с конкатенацией. Группа — моноид, в котором каждая стрелка является изоморфизмом (имеет двусторонний обратный). Примеры: целые числа, вычеты, свободная группа.
Изоморфизм — это не просто две стрелки в противоположных направлениях, а пара, для которой обе композиции дают тождества. Односторонние обратные не делают морфизм изоморфизмом.
Коммутативные диаграммы — язык визуализации равенств композиций. Мы используем их, чтобы задавать и понимать соотношения между морфизмами.
Python-код с ручным заданием композиций позволяет строить конечные категории, явно контролируя все аксиомы и избегая бесконечных замыканий.
Теория категорий — это гравитация нашей галактики знаний: она описывает, как объекты разных наук соединяются стрелками и как эти стрелки можно компоновать.
Что дальше? Следующий урок проведёт нас к функторам — отображениям между категориями. Если категория — гравитационная сеть одного города, то функтор — это картографический перевод, сохраняющий все улицы и перекрёстки. Вы узнаете, как связывать категории и переносить знания между мирами.

Это был пятый урок. Поздравляю: вы официально вошли в мир теории категорий и теперь владеете универсальным языком структур!

Приложение. Исходник урока 1005.

---

> *«Категория — это граф, в котором у каждой стрелки есть имя, и стрелки можно склеивать, если голова одной совпадает с хвостом другой.»*

> — вольный пересказ определений

## 0. Зачем нам категории? (мотивационное вступление)

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

Категория не заменяет математику, а служит её связующим каркасом. Она позволяет переносить интуицию из одной области в другую: например, композиция функций в программировании и логический вывод — это одно и то же с категориальной точки зрения. Этот урок откроет вам базовую грамматику языка категорий, после чего вы сможете описывать системы любой природы. Мы начнём с простого определения, разберём ключевой пример **Set**, а затем научимся рисовать и программировать маленькие категории.

---

## 1. Что такое категория? (определение частями)

### 1.1 Объекты и стрелки

В любой категории есть **объекты** — это «вещи», «сущности», «позиции». В категории множеств **Set** объектами являются множества. В других категориях объектами могут быть группы, векторные пространства, типы данных в программе или состояния физической системы. Объекты сами по себе статичны; жизнь категории создают связи между ними.

**Стрелки** (или **морфизмы**) — это направленные переходы от одного объекта к другому. Запись \( f: A \to B \) означает, что стрелка \( f \) ведёт из домена \( A \) в кодомен \( B \). В категории **Set** стрелки — это обычные функции. Важно, что стрелки всегда имеют начало и конец; они ориентированы, как улицы с односторонним движением в городе.

### 1.2 Композиция стрелок

Если из \( A \) в \( B \) ведёт стрелка \( f \), а из \( B \) в \( C \) — стрелка \( g \), то мы можем проехать сначала по \( f \), а потом по \( g \). В категории этому соответствует **композиция** — новая стрелка \( g \circ f: A \to C \). Читается это как «\( g \) после \( f \)»; порядок справа налево — традиция, идущая от записи функций.

Композиция обязана быть **ассоциативной**: неважно, в каком порядке расставлять скобки при склеивании трёх последовательных стрелок. Для любых \( f: A \to B \), \( g: B \to C \), \( h: C \to D \) выполняется \( (h \circ g) \circ f = h \circ (g \circ f) \). Это свойство гарантирует, что длинные цепочки переходов однозначно определены.

### 1.3 Тождественные стрелки

Для каждого объекта \( A \) существует особая **тождественная стрелка** \( \text{id}_A: A \to A \). Она ведёт из объекта в него самого и ничего не меняет. В дорожной аналогии это «оставаться на месте», нулевое перемещение.

Тождественная стрелка должна быть нейтральным элементом композиции: для любой \( f: A \to B \) верно \( f \circ \text{id}_A = f \) и \( \text{id}_B \circ f = f \). Это означает, что если вы сначала постоите на месте, а потом пойдёте, или наоборот, ваш маршрут не изменится. Логически это — очевидное требование, но оно формально закрепляет существование «ничего-не-делания» у каждого объекта.

### 1.4 Полное определение

Теперь соберём всё воедино. **Категория** \( \mathcal{C} \) состоит из:

- Класса объектов \( \text{Ob}(\mathcal{C}) \).

- Для каждой пары объектов \( A, B \) — набора стрелок \( \text{Hom}_{\mathcal{C}}(A, B) \) (множества морфизмов из \( A \) в \( B \)).

- Операции композиции \( \circ \), ставящей в соответствие паре \( f: A \to B, g: B \to C \) стрелку \( g \circ f: A \to C \).

- Для каждого объекта \( A \) — выделенной стрелки \( \text{id}_A: A \to A \).

При этом должны выполняться две аксиомы: **ассоциативность** композиции и **нейтральность** тождественных стрелок, как описано выше. Заметим, что в этом курсе мы работаем с локально малыми категориями: стрелки между любыми двумя объектами образуют множество, а совокупность всех объектов может быть классом (слишком большой, чтобы быть множеством). Это избавляет нас от теоретико‑множественных парадоксов, но для практики достаточно интуитивного понимания.

---

## 2. Первый и главный пример: категория Set

Важнейшей категорией для нас будет **Set**. Её объекты — все малые множества (например, все подмножества натуральных чисел или конечные множества, с которыми мы работаем). Стрелками служат все функции между этими множествами. Композиция стрелок — обычная композиция функций: \( (g \circ f)(x) = g(f(x)) \). Тождественная стрелка для множества \( A \) — функция \( \text{id}_A(a) = a \) для всех \( a \in A \).

Проверим аксиомы непосредственно. Для любых функций \( f: A \to B \), \( g: B \to C \), \( h: C \to D \) и любого \( x \in A \) имеем:

\( ((h \circ g) \circ f)(x) = (h \circ g)(f(x)) = h(g(f(x))) = h((g \circ f)(x)) = (h \circ (g \circ f))(x) \).

Ассоциативность выполняется. Нейтральность также очевидна:

\( f(\text{id}_A(x)) = f(x) \) и \( \text{id}_B(f(x)) = f(x) \).

Таким образом, **Set** — полноценная категория, и она станет нашей базовой картой, на которую мы будем проецировать остальные категории.

Каждый раз, когда вы пишете программу, преобразующую данные, или рассуждаете о функциях, вы неявно находитесь внутри **Set**. Понимание того, что это категория, даёт нам право использовать геометрические и алгебраические интуиции. Например, коммутативные диаграммы в **Set** — это просто утверждения о равенстве композиций функций. Мы будем постоянно возвращаться к этому примеру.

Важно, что в **Set** между двумя множествами может быть очень много разных функций. Это оправдывает общее определение категории, где стрелок больше одной. Именно множественность связей отражает богатство математических и реальных ситуаций.

---

## 3. Дискретная категория

Возьмём любое множество объектов и оставим только тождественные стрелки. Других стрелок нет. Композиция определена единственным возможным образом: \( \text{id} \circ \text{id} = \text{id} \). Такая категория называется **дискретной**. В ней нет никаких связей между разными объектами — это как архипелаг необитаемых островов, каждый из которых соединён только сам с собой.

Проверьте себя: если в дискретной категории пять объектов, сколько всего в ней стрелок? (Ответ: пять тождественных.) Это простейший, но концептуально важный случай. Позже мы увидим, что функтор из дискретной категории в **Set** — это просто выбор множеств, индексированных объектами, без каких-либо дополнительных условий на стрелки.

---

## 4. Категория-порядок (предпорядок) и транзитивные отношения

Пусть между некоторыми объектами есть не более одной стрелки. Правило: если есть стрелка \( A \to B \) и \( B \to C \), то обязана существовать стрелка \( A \to C \). Тождественная стрелка есть у каждого. Так мы получаем категорию, соответствующую **предпорядку** — рефлексивному и транзитивному отношению.

Проиллюстрируем это шкалой уровней тревожности: объекты — числа от 1 до 5, а стрелка \( a \to b \) означает «уровень \( a \) не выше уровня \( b \)». Тогда для любых \( a \le b \) и \( b \le c \) мы знаем, что \( a \le c \), и композиция замыкается автоматически. Тождественная стрелка оправдана тем, что любой уровень не выше самого себя.

Такие категории описывают иерархии, вложенности и шкалы. Когда вы строите генеалогическое древо или классификацию видов, вы фактически рисуете категорию-порядок. Обратите внимание: требование «не более одной стрелки» не означает, что стрелок между \( A \) и \( B \) не может быть: она либо одна, либо ни одной, задавая направление порядка.

**Транзитивные отношения и их количество.** На конечном множестве из \( n \) элементов бинарное отношение можно задать матрицей \( n \times n \). Общее количество таких отношений — \( 2^{n^2} \). Транзитивных (без рефлексивности) значительно меньше: для \( n=1,2,3,4,5 \) их соответственно 1, 2, 13, 171, 3994. Если добавить рефлексивность, получаем число предпорядков: 1, 4, 29, 355, 6942. Рост сверхэкспоненциален.

**Антитранзитивность и диаграммы Хассе.** Противоположное свойство — антитранзитивность: если есть стрелки \( A \to B \) и \( B \to C \), то **не** должно быть прямой стрелки \( A \to C \). Матрично это означает, что в позициях, соответствующих композиции, стоит 0, когда сомножители — единицы. Такие отношения задают «скелет» порядка, который называют диаграммой Хассе. В ней оставлены только минимальные, покрывающие связи, а все транзитивные замыкания опущены. Именно так мы рисуем порядки без загромождения. Свободная категория, порождённая антитранзитивным графом, автоматически замыкает его до транзитивного отношения при добавлении всех композиций. Это различие мы позже проиллюстрируем кодом.

---

## 5. Моноид как категория с одним объектом

Самая компактная нетривиальная категория имеет ровно один объект \( * \). Тогда все стрелки имеют вид \( * \to * \). Композиция двух стрелок — это бинарная операция на множестве стрелок, а тождественная стрелка служит нейтральным элементом. Такая структура в точности задаёт **моноид** — множество с ассоциативной бинарной операцией и единицей.

Натуральные числа со сложением и нулём — классический пример моноида. Здесь объект один (назовём его \( M \)), каждая стрелка — неотрицательное целое число, а композиция двух стрелок \( a \) и \( b \) даёт \( a + b \). Тождественная стрелка — 0. Ассоциативность композиции сводится к ассоциативности сложения: \( (a+b)+c = a+(b+c) \).

**Моноид как эндоморфизмы на множестве.** Второй взгляд на тот же моноид — представить его не как однообъектную категорию, а как набор эндоморфизмов конкретного объекта в **Set**. Например, возьмём множество натуральных чисел \( \mathbb{N} \) как объект, а каждому числу \( k \) сопоставим функцию сдвига \( +k : \mathbb{N} \to \mathbb{N} \) (прибавление \( k \)). Композиция таких функций соответствует сложению: \( (+m) \circ (+k) = +(m+k) \). Тождественная функция — \( +0 \). Получаем подкатегорию в **Set** с одним объектом, изоморфную исходному моноиду. Так мы можем видеть моноид либо как чёрный ящик с петлями, либо как знакомые функции на множестве. Обе точки зрения эквивалентны, и выбор зависит от удобства.

---

## 6. Группа как категория, где все стрелки — изоморфизмы

Если в моноиде каждый элемент имеет **двусторонний обратный**, моноид становится **группой**. В однообъектной категории это означает, что для каждой стрелки \( f \) существует стрелка \( f^{-1} \), для которой \( f \circ f^{-1} = \text{id} \) и \( f^{-1} \circ f = \text{id} \). Такие стрелки называются **изоморфизмами**, а сама категория — **группоидом** (в данном случае — с одним объектом, то есть группой).

Пример — целые числа со сложением \( (\mathbb{Z}, +) \). Объект один, стрелки — все целые числа. Композиция — сложение, тождество — 0. Для числа \( k \) обратным является \( -k \). Это группа. В отличие от \( \mathbb{N} \), здесь у каждой стрелки есть двусторонний обратный путь. В представлении на множестве \( \mathbb{Z} \) как объекте **Set**, стрелка \( k \) — функция сдвига \( x \mapsto x+k \), которая является биекцией (изоморфизмом). Обратная ей — сдвиг на \( -k \).

Другой важный пример — **вычеты по модулю \( n \)**. Множество \( \{0, 1, \dots, n-1\} \) со сложением по модулю \( n \) образует циклическую группу порядка \( n \). Однообъектная категория: стрелки — вычеты, композиция — сложение по модулю, тождество — 0. Здесь каждый элемент обратим: обратный к \( k \) есть \( n-k \). В **Set** эту группу можно представить как эндоморфизмы множества \( \mathbb{Z}_n \), где стрелка \( k \) действует как \( x \mapsto (x+k) \bmod n \). Повторение стрелки \( 1 \) \( n \) раз даёт тождественную стрелку, так что \( 1 \) — циклический изоморфизм.

**Свободная группа:** ещё один поучительный пример — строки с формальными обратными. Расширяем алфавит, добавляя для каждой буквы \( x \) обратную \( x^{-1} \), и накладываем правило сокращения: \( x x^{-1} = \varepsilon = x^{-1} x \). Получаем свободную группу, порождённую алфавитом. В однообъектной категории стрелками являются редуцированные слова, а композиция — конкатенация с последующей редукцией. Каждая стрелка имеет обратную (запись слова задом наперёд с заменой букв на обратные). Этот пример обобщает идею моноида строк до группы.

Таким образом, группа — это моноид, в котором каждая стрелка — изоморфизм. Разница с моноидом в том, что в моноиде стрелки могут быть необратимыми (как +1 в \( \mathbb{N} \)), а в группе все они обратимы.

---

## 7. Изоморфизмы: не просто стрелки туда-обратно

Мы уже упомянули, что изоморфизм — это морфизм \( f: A \to B \), для которого существует \( g: B \to A \) с \( g \circ f = \text{id}_A \) и \( f \circ g = \text{id}_B \). Обратите внимание: необходимо **оба** равенства. Если выполнено только одно, \( f \) называется расщепляемым мономорфизмом или эпиморфизмом, но не изоморфизмом. Например, в **Set** инъекция \( \{1\} \hookrightarrow \{1,2\} \) имеет левый обратный (ретракция), но не имеет правого, и не является биекцией.

Как мы видели, в категории с одним объектом изоморфизмы — это в точности обратимые элементы моноида. Если все элементы обратимы, моноид — группа. Таким образом, изоморфизм — свойство не просто «наличия стрелки туда и обратно», а наличия па́ры стрелок, которые при композиции дают тождества. Даже если между \( A \) и \( B \) есть много стрелок в обе стороны, объекты \( A \) и \( B \) изоморфны, если найдётся хотя бы одна такая пара. Остальные стрелки могут вести себя как угодно.

Пример с одноэлементными множествами: \( A = \{\text{True}\} \), \( B = \{\text{False}\} \). Между ними есть ровно одна функция в каждую сторону. Они автоматически являются взаимно обратными, потому что любая функция из одноэлементного множества в себя равна тождественной. Так природа объектов навязывает изоморфизм. В более богатых категориях мы вручную задаём, какие стрелки являются изоморфизмами, накладывая равенства композиций.

---

## 8. Коммутативные диаграммы

Уравнения вроде \( g \circ f = h \) удобно изображать графически в виде **коммутативных диаграмм**. Диаграмма — это ориентированный граф, вершины которого — объекты, а рёбра — морфизмы. Диаграмма коммутирует, если любые два пути с общим началом и концом дают равные композиции. Например, треугольник с вершинами \( A, B, C \) и стрелками \( f: A \to B \), \( g: B \to C \), \( h: A \to C \) коммутирует, если \( h = g \circ f \).

На практике, когда мы строим категорию вручную (как в нашем классе `Category`), мы тем самым объявляем некоторые диаграммы коммутативными. Задавая `set_composition("f", "g", "h")`, мы утверждаем коммутативность треугольника. Если позже добавляем стрелки и новые композиции, мы расширяем набор коммутативных диаграмм. Таким образом, категория может быть описана как набор образующих стрелок и соотношений (равенств композиций), что в точности соответствует заданию коммутативных диаграмм.

---

## 9. Категории вокруг нас (первые примеры из науки)

В программировании типы данных являются объектами, а чистые функции — стрелками. Композиция функций — это просто последовательный вызов, тождественная функция — `x => x`. Эта категория известна как **Hask** (с оговорками про ленивость и `undefined`, но для нас это полноценный пример). Когда вы пишете конвейер преобразований в функциональном стиле, вы строите стрелки в этой категории.

В логике объекты — высказывания, а стрелка \( A \to B \) означает, что \( A \) влечёт \( B \). Композиция соответствует цепочке рассуждений: если из \( A \) следует \( B \), а из \( B \) следует \( C \), то из \( A \) следует \( C \). Тождественная стрелка — тавтология \( A \to A \). Так математическая логика обретает категориальную форму.

---

## 10. Программирование: моделируем маленькую категорию вручную

Теперь создадим работающий класс, который представляет категорию с конечным числом объектов и стрелок, задаваемых явно. Мы не будем пытаться автоматически замыкать стрелки — как показала практика, для циклических графов это может привести к бесконечному циклу. Вместо этого мы будем **руками** добавлять все необходимые композиции и тождественные стрелки, в точности следуя аксиомам.

```python

class Category:

def __init__(self, objects):

self.objects = objects # список имён объектов

self.arrows = {} # словарь (домен, кодомен) -> список имён стрелок

self.composition = {} # словарь (f, g) -> h (где f: A->B, g: B->C)

self.identity = {} # для каждого объекта – имя тождественной стрелки

def add_arrow(self, name, dom, cod):

"""Добавляет стрелку name: dom -> cod"""

self.arrows.setdefault((dom, cod), []).append(name)

def set_identity(self, obj, name):

self.identity[obj] = name

self.add_arrow(name, obj, obj)

def set_composition(self, f, g, result):

"""Задаёт, что g∘f = result"""

self.composition[(f, g)] = result

def compose(self, f, g):

"""Возвращает композицию g∘f, если определена"""

return self.composition.get((f, g), None)

```

Построим конкретную маленькую категорию с тремя объектами и стрелками:

```python

C = Category(objects=["A", "B", "C"])

# Тождественные стрелки

C.set_identity("A", "id_A")

C.set_identity("B", "id_B")

C.set_identity("C", "id_C")

# Добавляем стрелки f: A->B, g: B->C

C.add_arrow("f", "A", "B")

C.add_arrow("g", "B", "C")

# Композиция g∘f = h (создадим новую стрелку h: A->C)

C.add_arrow("h", "A", "C")

C.set_composition("f", "g", "h")

# Явно задаём композиции с тождественными стрелками

C.set_composition("id_A", "f", "f")

C.set_composition("f", "id_B", "f")

C.set_composition("id_B", "g", "g")

C.set_composition("g", "id_C", "g")

C.set_composition("id_A", "h", "h")

C.set_composition("h", "id_C", "h")

print("Композиция f потом g =", C.compose("f", "g")) # h

print("Композиция f потом id_B =", C.compose("f", "id_B")) # f

```

Этот код наглядно показывает, что категория требует явного задания всех композиций и тождеств. Так мы строим категорию с соотношениями, избегая бесконечных замыканий. Если мы захотим добавить циклические стрелки, как в категории с двумя объектами `True` и `False` и стрелками `not` и `const True`, мы можем добавить их и вручную назначить композиции. Это полностью контролируемый процесс.

---

## 11. Задания для самообучения

### Задание 1. Категория из чисел (делимость)

Пусть объекты — натуральные числа от 1 до 6. Стрелка из \( n \) в \( m \) существует, если \( n \) делится на \( m \). Проверьте, что для каждого объекта есть тождественная стрелка (любое число делится само на себя) и что отношение транзитивно. Нарисуйте граф этой категории. Какие стрелки пришлось бы добавить, чтобы получить диаграмму Хассе (антитранзитивный остов)?

*Подсказка:* составьте таблицу, где строки и столбцы — объекты, а в ячейке стоит 1, если делимость есть. Убедитесь, что если есть 1 в \( (n,m) \) и в \( (m,k) \), то есть и в \( (n,k) \). Для диаграммы Хассе оставьте только те единицы, которые нельзя получить как транзитивное замыкание других.

### Задание 2. Категория логических импликаций

Объекты — высказывания \( A, B, C \). Стрелка \( X \to Y \) существует, если формула \( X \Rightarrow Y \) является тавтологией. Какие тождественные стрелки здесь есть? Покажите, что композиция соответствует правилу «из \( X \Rightarrow Y \) и \( Y \Rightarrow Z \) следует \( X \Rightarrow Z \)». Напишите на Python небольшую проверку для трёх конкретных высказываний, перебирая их истинностные значения.

*Подсказка:* используйте `itertools.product` для генерации всех комбинаций истинности и таблицу истинности для импликации.

### Задание 3. Моноид как категория (сложение и строки)

а) Реализуйте класс `MonoidCategory`, где объект один, стрелки — неотрицательные целые числа, а композиция — сложение. Убедитесь, что ассоциативность и нейтральность выполнены.

б) Создайте моноид строк с конкатенацией и пустой строкой. Проверьте законы на нескольких примерах.

*Подсказка:* можете использовать класс `Category`, добавив один объект `"*"` и задав все композиции вручную, как в примере с числами.

### Задание 4. Группа как категория (целые числа, вычеты)

а) Превратите моноид натуральных чисел в группу целых чисел. Для этого в классе `Category` с объектом `"*"` добавьте отрицательные числа и определите композицию \( a \circ b = a + b \). Убедитесь, что у каждой стрелки есть обратная.

б) Постройте категорию вычетов по модулю 5. Выпишите таблицу композиций и проверьте, что каждая стрелка является изоморфизмом.

*Подсказка:* для модуля 5 объект один, стрелки `"0"`.."4", композиция `(i, j) -> (i+j) % 5`. Обратный к `k` — `5-k`.

### Задание 5. Изоморфизмы и односторонние обратные

В категории **Set** найдите пример функции, которая имеет левый обратный, но не имеет правого. Объясните, почему она не является изоморфизмом. Сделайте то же для функции с правым обратным, но без левого. Как эти примеры выглядят в терминах стрелок в однообъектной категории эндоморфизмов?

*Подсказка:* рассмотрите функцию из {1} в {1,2}, или из {1,2} в {1}.

### Задание 6. Свободная категория и антитранзитивность

Возьмите две вершины \( A, B \) и одну стрелку \( f: A \to B \). Свободная категория, порождённая этим графом, содержит ещё и тождественные стрелки. Сколько всего стрелок? Если добавить обратную стрелку \( g: B \to A \), какие новые стрелки появятся? Попробуйте замкнуть их автоматически (реализовав метод `close_under_composition`) и посмотрите, к чему это приведёт. Объясните, почему для циклических графов такое замыкание бесконечно.

*Подсказка:* при автоматическом порождении новые стрелки типа `g∘f`, `f∘g`, `f∘g∘f` и т.д. будут всё длиннее, и их имена не совпадут, если вы не введёте равенств.

---

## 12. Резюме

- **Категория** состоит из объектов и стрелок с операцией композиции, которая ассоциативна и имеет тождественные стрелки для каждого объекта. Это минимальный каркас для описания любых направленных связей.

- **Set** — категория множеств и функций, наш первый и главный пример. **Дискретная категория** лишена связей между разными объектами, **категория-порядок** содержит не более одной стрелки между парой (предпорядок). **Антитранзитивные** отношения дают диаграммы Хассе.

- **Моноид** — категория с одним объектом, где композицией служит ассоциативная операция с единицей. Примеры: числа со сложением, строки с конкатенацией. **Группа** — моноид, в котором каждая стрелка является изоморфизмом (имеет двусторонний обратный). Примеры: целые числа, вычеты, свободная группа.

- **Изоморфизм** — это не просто две стрелки в противоположных направлениях, а пара, для которой обе композиции дают тождества. Односторонние обратные не делают морфизм изоморфизмом.

- **Коммутативные диаграммы** — язык визуализации равенств композиций. Мы используем их, чтобы задавать и понимать соотношения между морфизмами.

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

- Теория категорий — это **гравитация** нашей галактики знаний: она описывает, как объекты разных наук соединяются стрелками и как эти стрелки можно компоновать.

- **Что дальше?** Следующий урок проведёт нас к **функторам** — отображениям между категориями. Если категория — гравитационная сеть одного города, то функтор — это картографический перевод, сохраняющий все улицы и перекрёстки. Вы узнаете, как связывать категории и переносить знания между мирами.

---

*Это был пятый урок. Поздравляю: вы официально вошли в мир теории категорий и теперь владеете универсальным языком структур!*