F-коалгебра - F-coalgebra

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

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

Определение

Позволять

{ Displaystyle F: { mathcal {C}} longrightarrow { mathcal {C}}}

быть эндофунктор по категории ${ Displaystyle { mathcal {C}}}$ .An ${ displaystyle F}$ -коалгебра это объект ${ displaystyle A}$ из ${ Displaystyle { mathcal {C}}}$ вместе с морфизм

{ displaystyle alpha: A longrightarrow FA}

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

An ${ displaystyle F}$ -коалгебра гомоморфизм из ${ Displaystyle (А, альфа)}$ другому ${ displaystyle F}$ -коалгебра ${ displaystyle (B, beta)}$ это морфизм

{ displaystyle f: A longrightarrow B}

в ${ Displaystyle { mathcal {C}}}$ такой, что

{ Displaystyle Ff circ alpha = beta circ f}

.

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

Примеры

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

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

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

Приложения

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

F-коалгебра - F-coalgebra

Содержание

Определение

Примеры

Приложения

Смотрите также

Рекомендации

внешняя ссылка