Свойство начальности и терминальности

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

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

Свойства начальных алгебр и терминальных коалгебр делают их особенно подходящими в качестве стандартных моделей (т. е. в качестве стандартных семантик) алгебраических и коалгебраических спецификаций. Они неформально известны как спецификации «без мусора» (для начальных адгебр это означает, что они не содержат объектов, которые невозможно определить в терминах конструкторов) и «без сюрпризов» (для начальных алгебр это означает, что объекты, которые подразумеваются различными, на самом деле различны, а алгебра имеет только те свойства, которые определены). Более того, свойства минимальности и простоты подразумевают, что можно пользоваться индукцией и коиндукцией для доказательства свойств и определения функций над ними. Наконец, полиномиальные функторы всегда имеют начальные алгебры и терминальные коалгебры, которые могут быть построены в терминах стандартных конструкций. (К сожалению, один из наиболее релевантных функторов для коалгебр, используемый для представления бесконечных форм недетерминизма, является степенным функтором $2^\_$, для которого не существует терминальной коалгебры. Если бы она существовала, операция $f : A \longrightarrow 2^{A}$ была бы изоморфизмом, но в стандартной (канторовской) теории множеств) множество не может быть изоморфным множеству всех его подмножеств. Однако, в мире не совсем определённых множеств и классов подобный изоморфизм существует).

Достаточно интересным примером начальной алгебры является начальная алгебра функтора $1 + \_$, которая является алгеброй натуральных чисел с нулём и следующим элементом. Это, скорее всего, искуснейшее определение натуральных чисел, которое имеет все свойства определения Пеано: начальность подразумевает, что операция $\langle 0, S \rangle : 1 + N \longrightarrow N$ является изоморфизмом, т. е. что натуральные числа являются натуральными числами плюс один элемент, имеется нуль, и то, что операция получения следующего элемента $S$ является биекцией на натуральных числах. Это фиксирует первые четыре аксиомы Пеано. Минимальность приносит принцип индукции, который является пятой аксиомой. Функтор $1 + \_$ является почти что простейшим, который только можно представить.

Примером терминальной коалгебры обычно является коалгебра потоков, т. е. бесконечно длинных последовательностей символов из алфавита $S$ (или, эквивалентно, функций $s : N \longrightarrow S$), которая является терминальной коалгеброй функтора $S x \_$.