Одним из главных достижений теории категорий стало понимание того, что информацию об абстрактных математических объектах можно получать, не расщепляя и анализируя сами объекты, а изучая структуру отношений между ними, особенно таких отношений, которые можно комбинировать между собой. Их называют морфизмами. В математике этот корень встречается во многих терминах, которые образуют своеобразный зоопарк: гомоморфизмы, эпиморфизмы, мономорфизмы, эндоморфизмы, автоморфизмы и прочие...
По просьбе читателя @Deza я кратко перечислю те виды морфизмов, которые вспомнил, пока 8 часов летел в самолёте из Москвы на Камчатку. Быть может, в литературе встречаются и другие морфизмы-шморфизмы, но я ограничусь тем, что помню.
Поехали!
Мы будем говорить об отношениях между объектами, множествами, алгебраическими структурами и типами данных. Многие из этих отношений имеют синонимы в разных контекстах: в теории категорий, в теории множеств, в алгебре, в программировании. Я постараюсь приводить примеры из разных контекстов, по возможности простые.
Морфизм
Самый общий из морфизмов — просто морфизм — это базовое отношение между объектами в теории категорий. В теории множеств это отображение — отношение между элементами множеств или самими множествами. В программировании морфизм — это функция, как отношение между типами.
Морфизм можно показать стрелкой, которая исходит из одного объекта и указывает на другой, либо формально описать его действие в виде программы, либо обозначить в символах: f: A → B. Здесь A называется доменом или прообразом морфизма, а B — его образом.
Главное свойство морфизма, отличающее его от произвольного отношения, состоит в том, что морфизмы объединяются с помощью композиции. Для двух морфизмов f: A→B и g: B→C должен существовать морфизм (g◦f): A→C. Никаких других дополнительных свойств от этого отношения пока не требуется.
Примеры морфизмов и отображений:
- Отношение "меньше либо равно" над числами,
- отношение "быть подмножеством" для множеств,
- функции над элементами множеств,
- рёбра в полном направленном графе,
- программная функция show: Int -> String, представляющая число в виде строки.
Привести не очень искусственный пример математического отношения, не являющегося морфизмом, непросто. В программировании с этим проще. Если мы допустим побочные эффекты, то две программы, как функции, отображающие состояние вычислительной системы на себя, могут запросто не комбинироваться в композицию. Например, функция rm, удаляющая указанный файл с диска, и программа cat, его читающая или открывающая, не смогут быть выполнены в композиции (применены последовательно). В функциональном программировании побочные эффекты строго регламентированы и формализованы, и в этой парадигме программы как чистые функции всегда могут образовывать композиции, если это позволяют их типы.
Гомоморфизм
В алгебре важную роль играют такие морфизмы между алгебраическими структурами (группами, кольцами, полями и т. д.), которые согласованно переносят алгебраические операции из одного объекта в другой. Они называются гомоморфизмами. Это значит, что любой операции (⋆), определённой в алгебре A, гомоморфизм φ: А→B однозначно ставит в соответствие некую операцию (⋄) из алгебры B, при этом φ(a ⋆ b) = φ(a) ⋄ φ(b). Важно, чтобы особые элементы (в частности, нейтральные элементы или нули) имели образы с такими же свойствами.
Особую роль играют прообразы нулей, которые называют ядром гомоморфизма. С ядрами связано много важных универсальных теорем в самых разных областях математики, поскольку они отражают свойства морфизмов как таковых.
Примеры гомоморфизмов:
- Показательная функция является гомоморфизмом между сложением чисел и их умножением (аддитивной и мультипликативной группами поля). Ядром этого морфизма будет подмножество {0}, поскольку оно отображается в 1 — нейтральный элемент для умножения.
- Операция вычисления остатков от деления целых чисел на число n образует гомоморфизм между кольцом целых чисел Z и кольцом вычетов Zₙ.
- Корректную программную функцию, вычисляющую длину списка, можно рассматривать, как гомоморфизмом между полугруппами с единицей List a (список элементов произвольного типа a) и ℕ⁺, при этом она переносит операцию конкатенации списков в операцию сложения их длин. Её ядром будет пустой список.
Моно- и эпиморфизм
Если структура A (множество, алгебра, тип и т. п.) отображается морфизмом в структуру B, сохраняя принцип "разные входы → разные выходы", то он называется мономорфизмом. В теории множеств ему соответствует инъективное отображение или вложение.
В теории категорий используются более формальные определения мономорфизма и эпиморфизма, отражающие их факторизационные свойства. Они важны, но не интуитивны, и я не буду их здесь приводить.
Примеры мономорфизма
- Функция x ↦ exp(ix) инъективно отображает всё множество ℝ в часть множества ℂ. [Тут у меня косяк, см. комментарии]
- Программная функция show : Int -> String.
- Идеальная хеш-функция должна быть инъективной.
- Программная функция isEven: Int -> Bool из множества целых чисел в булево множество {True, False}, отвечающая на вопрос "чётно ли число?" не является мономорфизмом, поскольку разным входным аргументам может соответствовать один результат.
- Сопряжение с элементом группы (x↦axa⁻¹) является мономорфизмом из подгруппы в группу.
Эпиморфизм
Если образом морфизма между комплексными объектами является вся структура B (множество, алгебра, тип и т. п.), тот есть, каждый элемент образа домттжим, то он называется эпиморфизмом. В теории множест ему соответствует сюръективное отображение.
Примеры эпиморфизма
- Логарифмическая функция сюръективно отображает интервал (0, ∞) на всё множество ℝ и при этом является эпиморфизмом из мультипликативной группы положительных вещественных чисел в аддитивную группу всех вещественных чисел. Так работают логарифмическая линейка и таблицы Брадиса.
- Функция x↦x mod 5 является эпиморфизмом из кольца целых чисел Z в кольцо Z₅.
- Сопряжение с фактор-группой является эпиморфизмом на группу её нормальной подгруппы (это чистый выпендрёж, но звучит красиво).
- Программная функция isEven: Int -> Bool из множества целых чисел в булево множество {True, False}, отвечающая на вопрос "чётно ли число?" является эпиморфизмом,
- Программа mod5: Int -> Int, вычисляющая остаток от деления целого числа на 5, не является эпиморфизмом, поскольку образом всех возможных целых чисел является лишь их подмножество {0, 1, 2, 3, 4}.
Биморфизм
Если морфизм, соединяющий комплексные объекты A и B (множества, алгебры, типы), является одновременно мономорфизмом и эпиморфизмом, то он называется биморфизмом (биективным отображением в теории множеств). Если биморфизм обратим, то он является изоморфизмом и задаëт отношение эквивалентности между объектами.
Примеры:
- Интервал (0, 1] изоморфен интервалу [1, ∞), поскольку существует обратимая на этих интервалах функция x↦1/x, строящая биективное отображение между этими множествами.
- Программная функция length: List a -> Int задаёт биморфизм между типом для списка и натуральными числами, но не является изоморфизмом.
- Все группы из пяти элементов изоморфны простой циклической группе C₅. Изоморфизм строится тривиальным взаимно однозначным отображением множеств элементов групп.
Гомеоморфизм
Особняком стоит упомянуть гомеоморфизм — морфизм в категории топологических пространств и объектов, представляющий непрерывное преобразование одного в другое. При этом кроме отображения точек пространств гомеоморфизм переносит топологию (структуру открытых подмножеств) пространства и такие характеристики, как связность, род и т. п.
В топологии гомеоморфизм используется как отношение эквивалентности.
Примеры гомеоморфизма
- Знаменитый и уже изрядно надоевший гомеоморфизм между кофейной чашкой и бубликом.
- Менее известный гомеоморфизм между обычными штанами и штанами, у которых штанины сшиты друг с другом по краям.
- Мыльная плёнка на проволочном кольце и оторвавшийся от него мыльный пузырь гомеоморфны.
- Изоморфизм (не гомеоморфизм!) между топологией пространства вещественных чисел Rⁿ и топологией n-мерного евклидова пространства Rⁿ позволяет нам использовать числовые оси и координатный метод, применяя алгебраические методы в геометрии и геометрические методы в алгебре.
Эндоморфизм
Если морфизм соединяет объект с самим собой, то он называется эндоморфизмом. Композиция любых двух эндоморфизмов, естественно, тоже будет эндоморфизмом.
В теории категорий с этим типом морфизмов связана важная структура с единственным объектом и набором эндоморфизмов, которая называется моноид. Важным примером служит формализация арифметики натуральных чисел аксиоматикой Пеано, которая строит свободный моноид с морфизмом Succ: ℕ→ℕ, указывающий на следующее число в индуктивном множестве. Моноидальная структура арифметики широко используется, например, в теории типов и лямбда-исчислении.
Примеры эндоморфизмов:
- Любые целочисленные или вещественные функции являются эндоморфизмами.
- Действие элемента группы (результат умножения на этот элемент всей группы) является эндоморфизмом.
- Программные функции reverse, sort, slice, filter p и другие преобразователи списков с типом List a -> List a являются эндоморфизмами.
Автоморфизм
Если эндоморфизм является изоморфизмом, то он называется автоморфизмом.
Примеры:
- Тождественное отображение является тривиальным автоморфизмом. Это не пустое дело, а нейтральный элемент для композиции, который необходим и для теории категорий, и для теории типов, и для функционального программирования.
- -Функция x↦5x является автоморфизмом над аддитивной группой Z⁺, поскольку Z⁺ и (5Z)⁺ изоморфны друг другу.
- Циклическая перестановка образует автоморфизм над любой циклической группой.
- Если на тип a нет никаких ограничений, то чистая функция с типом a -> a может быть только автоморфизмом, причём тривиальным, то есть тождественным отображением.
Функторы
Наконец, сами морфизмы тоже могут стать объектами для морфизмов более высокого уровня. Такие "супер-морфизмы" принято называть функторами. Это гомоморфизмы между различными категориями, переносящие, кроме объектов, структуру морфизмов в категории.
Примеры
- Теория Галуа строит функторы из категории групп в категорию алгебры полей и их расширений.
- Программная функция map: (a -> b) -> (List a -> List b) — это эндофунктор из категории типов в категорию типов, отображающий морфизмы между типами на морфизмы между списками.
- Алгебраическая топология занята построением функторов из категории топологических объектов в категорию групп.
Ката- и анаморфизмы
В теории алгебраических типов и в функциональном програмиировпнии выделяют дополнительные виды морфизмов:
Катаморфизм (свёртка, reduce, fold): отображение сложного типа (списка, дерева, графа и т. п.) в простой тип (число, булево значение, синглтон и т. п.).
Примеры:
- Функции, возвращающие длину списка, сумму элементов дерева, максимальный элемент рекурсивной структуры и т. п.
- Функция, которая список цифр в заданной системе счисления превращает в число.
- Интерпретатор абстрактного синтаксического дерева, представляющего арифметическое выражение.
Анаморфизм (развёртка, expand, unfold): отображение простого типа в сложный.
Примеры:
- Функция, возвращающая список цифр числа.
- Лексический или синтаксический анализаторы, развёртывающие строки в поток лексем или в абстрактное синтаксическое дерево (в лексическом анализе строка является простым типом, лексемой).
- Построение арифметики с аксиоматикой Пеано в виде моноида тоже можно считать анаморфизмом из тривиального кольца 0 в полукольцо натуральных чисел.
Гиломорфизм: композиция анаморфизма и катаморфизма, то есть превращение одного простого типа в другой с промежуточным сложным типом (в случае ленивых вычислений — неявным).
Примеры:
- Функция, возвращающая сумму цифр числа, цифровой корень (число разворачивается в список цифр, а потом сворачивается в их сумму).
- Калькулятор, вычисляющий арифметическое выражение, заданное строкой: строка разворачивается в абстрактное синтаксическое дерево, а потом интерпретируется в строку, представляющую числовой результат.
Зигоморфизм: композиция катаморфизма и анаморфизма, то есть преобразование одного сложного типа в другой сложный через создание промежуточного простого.
Примеры:
- Функция, переводящая целое число из одной системы счисления в другую. Список цифр из одной системы счисления сворачивается в число типа Int, а потом разворачивается в список цифр в другой системе.
- Высокоуровневые программы, например трансляторы, которые из нескольких файлов с кодом создают один объектный файл (например, байт-код), а потом выполняют его на виртуальной машине и создают последовательность побочных эффектов или файлов. Поскольку современная теория алгебраических типов стала очень продвинутой, то и самые разнообразные побочные эффекты (в том числе обработка исключений, управление потоком выполнения через ограниченные продолжения и т. п.) тоже становятся объектами математического анализа.
* * *
Напоследок стоит заметить, что не все математические слова с корнем "морф" относятся к отображениям. Например, в геометрии говорят об энантоморфных фигурах, то есть о равных фигурах, несовместимых правильными изометриями, сохраняющими ориентацию пространства (как, например, правая и левая перчатки). Но нельзя говорить об "энантоморфизме" как о преобразовании пространства или фигуры.