Терминальная коалгебра

Изначально, ровно, как и далее, больше всего мы ссылаемся на (категории) алгебры и коалгебры. В алгебре основой является условие существования ровно одного гомоморфизма в любую другую алгебру. В коалгебре конечным является гомоморфизм в любую другую коалгебру. Основой алгебры и конечной коалгебры, должно быть, является прототип: каждая алгебра содержит “отображение” основной алгебры, а коалгебра отображение каждой коалгебры. It will not be a surprise, therefore, that if some signature has an initial algebra, this is unique (up to isomorphism), and similarly the final coalgebra, if exists for a signature, is unique (up to isomorphism). It will also not be a surprise that an initial algebra is minimal and a final coalgebra is simple (intuitively, if an initial algebra were not minimal, there would be a proper subalgebra of the initial algebra, which also would be contained in all other algebras in a unique way: but a proper subalgebra cannot be isomorphic to the containing one. Dually for final coalgebras). Другой интересной особенностью является факт возможности изоморфизма в пределах стандартной алгебры (и коалгебры).

Особенности стандартной алгебры и конечной коалгебры обычно используются с подходящей стандартной моделью (т.е. определятся необходимой семантикой) и спецификацией отдельной категории алгебры и коалгебры. Эти спецификации известны как “отсутствие мусора” (для базовой алгебры это означает отсутствие объектов, не определяемых с помощью доступных конструкторов), и “отсутствие сюрпризов” (для базовой алгебры это означает, что объекты, которые вы считаете различными и в самом деле различны, а их свойства, заявленные вами, не совместимы с другим свойствами объектов). Более того это упрощение подразумевает то, что вы можете принципы индукции/коиндукции при доказательстве свойств и объявлении функции. Итак, полиномиальные функции всегда имеются в базовой алгебре и конечной коалгебры, какая бы не была требуемая конструкция. (К сожалению, один из наиболее подходящих функторов коалгебры, используемых для представления бесконечных недетерминированных структур, выполняющий перестановку функтор, не является частью конечной коалгебры. Если бы отображение f: A-> 2^A являлось изоморфизмом в стандартной теории категорий Георга Кантора, то множество не может быть изоморфным по отношению к своим подмножествам. Однако, в плохо реализованных последовательностях и классах изоморфизм все же существует.)

Как пример конечной коалгебры приведем потоки, т.е. бесконечно длинные последовательности символов произвольного алфавита S (или иначе функцию s : N -> S), которые, в конечной коалгебре, представляют собой функтор S x_.