F-коалгебра

Эта статья может быть слишком технической для понимания большинства читателей . Пожалуйста, помогите улучшить ее, чтобы сделать ее понятной для неспециалистов , не удаляя технические детали. ( Июль 2020 ) ( Узнайте, как и когда удалить это сообщение )

В математике , в частности в теории категорий , -коалгебра — это структура, определяемая в соответствии с функтором , со специфическими свойствами, как определено ниже. Как для алгебр , так и для коалгебр , ^{[ необходимо разъяснение ]} функтор — это удобный и общий способ организации сигнатуры . Это имеет приложения в информатике : примеры коалгебр включают ленивые вычисления , бесконечные структуры данных , такие как потоки , а также системы переходов .${\displaystyle F}$ ${\displaystyle F}$

${\displaystyle F}$-коалгебры двойственны -алгебрам . Так же, как класс всех алгебр для данной сигнатуры и эквациональной теории образуют многообразие , так и класс всех -коалгебр, удовлетворяющих данной эквациональной теории , образует комногообразие, где сигнатура задается как .${\displaystyle F}$${\displaystyle F}$${\displaystyle F}$

Позволять

${\displaystyle F:{\mathcal {C}}\longrightarrow {\mathcal {C}}}$

быть эндофунктором в категории . -Коалгебра является объектом вместе с морфизмом${\displaystyle {\mathcal {C}}}$${\displaystyle F}$${\displaystyle А}$${\displaystyle {\mathcal {C}}}$

${\displaystyle \alpha :A\longrightarrow FA}$

из , обычно пишется как .${\displaystyle {\mathcal {C}}}$${\displaystyle (А,\альфа)}$

Гомоморфизм -коалгебры в другую -коалгебру является морфизмом ${\displaystyle F}$${\displaystyle (А,\альфа)}$${\displaystyle F}$${\displaystyle (B,\бета)}$

${\displaystyle f:A\longrightarrow B}$

в таком виде, что ${\displaystyle {\mathcal {C}}}$

${\displaystyle Ff\circ \альфа =\бета \circ f}$.

Таким образом, -коалгебры для данного функтора F образуют категорию.${\displaystyle F}$

Рассмотрим эндофунктор , который переводит множество в его несвязное объединение с одноэлементным множеством . Коалгебра этого эндофунктора задается как , где — так называемые конатуральные числа, состоящие из неотрицательных целых чисел и бесконечности, а функция задается как , для и . Фактически, — конечная коалгебра этого эндофунктора.${\displaystyle X\mapsto X\sqcup \{*\}:\mathbf {Установить} \to \mathbf {Установить} }$${\displaystyle \{\ast \}}$${\displaystyle ({\overline {\mathbb {N} }},\альфа )}$${\displaystyle {\overline {\mathbb {N} }}=\{0,1,2,\ldots \}\sqcup \{\infty \}}$${\displaystyle \альфа}$${\displaystyle \альфа (0)=\аст}$${\displaystyle \альфа (n)=n-1}$${\displaystyle n=1,2,\ldots}$${\displaystyle \alpha (\infty) =\infty}$${\displaystyle ({\overline {\mathbb {N} }},\альфа )}$

В более общем случае зафиксируем некоторое множество и рассмотрим функтор , который отправляет в . Тогда -коалгебра — это конечный или бесконечный поток над алфавитом , где — множество состояний, а — функция перехода состояний. Применение функции перехода состояний к состоянию может дать два возможных результата: либо элемент из вместе со следующим состоянием потока, либо элемент синглтонного множества как отдельное «конечное состояние», указывающее на то, что в потоке больше нет значений.${\displaystyle А}$${\displaystyle F:\mathbf {Set} \longrightarrow \mathbf {Set} }$${\displaystyle X}$${\displaystyle (X\times A)\чашка \{1\}}$${\displaystyle F}$${\displaystyle \alpha :X\longrightarrow (X\times A)\cup \{1\}=FX}$ ${\displaystyle А}$${\displaystyle X}$${\displaystyle \альфа}$${\displaystyle А}$${\displaystyle \{1\}}$

Во многих практических приложениях функция перехода состояний такого коалгебраического объекта может иметь вид , который легко факторизуется в набор «селекторов», «наблюдателей», «методов» . Особые случаи практического интереса включают наблюдателей, дающих значения атрибутов, и методы-мутаторы вида, принимающие дополнительные параметры и дающие состояния. Это разложение является двойственным разложению исходных -алгебр в суммы «конструкторов».${\displaystyle X\rightarrow f_{1}\times f_{2}\times \ldots \times f_{n}}$${\displaystyle X\rightarrow f_{1},\,X\rightarrow f_{2}\,\ldots \,X\rightarrow f_{n}}$${\displaystyle X\rightarrow X^{A_{1}\times \ldots \times A_{n}}}$${\displaystyle F}$

Пусть P — конструкция множества степеней на категории множеств, рассматриваемая как ковариантный функтор. P -коалгебры находятся в биективном соответствии с множествами с бинарным отношением. Теперь зафиксируем другое множество, A . Тогда коалгебры для эндофунктора P ( A ×(-)) находятся в биективном соответствии с помеченными системами переходов , а гомоморфизмы между коалгебрами соответствуют функциональным бисимуляциям между помеченными системами переходов.

В информатике коалгебра возникла как удобный и достаточно общий способ задания поведения систем и структур данных, которые потенциально бесконечны, например, классов в объектно-ориентированном программировании , потоков и систем переходов . В то время как алгебраическая спецификация имеет дело с функциональным поведением, обычно используя индуктивные типы данных, генерируемые конструкторами, коалгебраическая спецификация касается поведения, моделируемого коиндуктивными типами процессов, которые наблюдаются селекторами, во многом в духе теории автоматов . Важную роль здесь играют конечные коалгебры , которые являются полными наборами возможно бесконечных поведений, таких как потоки. Естественной логикой для выражения свойств таких систем является коалгебраическая модальная логика . ^{[ требуется цитата ]}

• Начальная алгебра
• Коиндукция
• Коалгебра

• Б. Якобс и Дж. Раттен, Учебник по (ко)алгебрам и (ко)индукции. EATCS Bulletin 62, 1997, стр. 222-259.
• Ян Дж. М. М. Раттен: Универсальная коалгебра: теория систем. Теор. вычисл. наук. 249(1): 3-80 (2000).
• J. Adamek, Введение в коалгебру. Теория и приложения категорий 14 (2005), 157-199
• Б. Якобс, Введение в коалгебру. К математике состояний и наблюдений (черновик книги)
• Иде Венема: Автоматы и логика с фиксированной точкой: коалгебраическая перспектива. Информация и вычисления, 204 (2006) 637-678.

• CALCO 2009: Конференция по алгебре и коалгебре в информатике
• КАЛКО 2011