F -coalgebra - F-coalgebra

Em matemática , especificamente na teoria das categorias , um -coálgebra é uma estrutura definida de acordo com um functor , com propriedades específicas conforme definidas abaixo. Para álgebras e coalgebras , um functor é uma maneira conveniente e geral de organizar uma assinatura . Isso tem aplicações em ciência da computação : exemplos de coalgebras incluem estruturas de dados infinitas e preguiçosas , como fluxos , e também sistemas de transição . ${\ displaystyle F}$ ${\ displaystyle F}$

${\ displaystyle F}$ -coalgebras são duplas para -algebras . Assim como a classe de todas as álgebras para uma determinada assinatura e teoria equacional forma uma variedade , o mesmo acontece com a classe de todas as álgebras que satisfazem uma dada teoria equacional forma uma covariedade, onde a assinatura é dada por . ${\ displaystyle F}$${\ displaystyle F}$${\ displaystyle F}$

Definição

Deixei

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

ser um endofunctor em uma categoria . Um -coalgebra é um objeto de junto com um morfismo${\ displaystyle {\ mathcal {C}}}$${\ displaystyle F}$${\ displaystyle A}$${\ displaystyle {\ mathcal {C}}}$

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

de , geralmente escrito como . ${\ displaystyle {\ mathcal {C}}}$${\ displaystyle (A, \ alpha)}$

Um homomorfismo -coalgebra de para outro -coalgebra é um morfismo ${\ displaystyle F}$${\ displaystyle (A, \ alpha)}$${\ displaystyle F}$${\ displaystyle (B, \ beta)}$

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

em tal que ${\ displaystyle {\ mathcal {C}}}$

${\ displaystyle Ff \ circ \ alpha = \ beta \ circ f}$ .

Assim, as coálgebras de um dado functor F constituem uma categoria. ${\ displaystyle F}$

Exemplos

Considere o endofunctor que envia um conjunto para sua união disjunta com o conjunto singleton . Uma coalgebra deste endofunctor é dada por , onde são os chamados números conaturais, consistindo nos inteiros não negativos e também infinito, e a função é dada por , para e . Na verdade, é o carvão terminal deste endofunctor. ${\ 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 \ alpha (0) = \ ast}$${\ displaystyle \ alpha (n) = n-1}$${\ displaystyle n = 1,2, \ ldots}$${\ displaystyle \ alpha (\ infty) = \ infty}$${\ displaystyle ({\ overline {\ mathbb {N}}}, \ alpha)}$

De forma mais geral, corrija algum conjunto e considere o functor que envia para . Então, um -coalgebra é um fluxo finito ou infinito sobre o alfabeto , onde é o conjunto de estados e é a função de transição de estado. Aplicar a função de transição de estado a um estado pode produzir dois resultados possíveis: um elemento de junto com o próximo estado do fluxo ou o elemento do singleton definido como um "estado final" separado, indicando que não há mais valores em o riacho. ${\ displaystyle A}$${\ displaystyle F: \ mathbf {Set} \ longrightarrow \ mathbf {Set}}$${\ displaystyle X}$${\ displaystyle (X \ vezes A) \ xícara \ {1 \}}$${\ displaystyle F}$${\ displaystyle \ alpha: X \ longrightarrow (X \ times A) \ xícara \ {1 \} = FX}$ ${\ displaystyle A}$${\ displaystyle X}$${\ displaystyle \ alpha}$${\ displaystyle A}$${\ displaystyle \ {1 \}}$

Em muitas aplicações práticas, a função de transição de estado de tal objeto coalescente pode ter a forma , que prontamente é fatorada em uma coleção de "seletores", "observadores", "métodos" . Casos especiais de interesse prático incluem observadores gerando valores de atributos e métodos modificadores da forma tomando parâmetros adicionais e estados produtivos. Esta decomposição é dual para a decomposição das -álgebras iniciais em somas de 'construtores'. ${\ 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}$

Seja P a construção do conjunto de potência na categoria dos conjuntos, considerada como um functor covariante. Os P- coálgebras estão em correspondência bijetiva com conjuntos com uma relação binária. Agora fixe um outro conjunto, A . Então coalgebras para o endofunctor P ( A × (-)) estão em correspondência bijetiva com sistemas de transição rotulados , e homomorfismos entre coalgebras correspondem a bissimulações funcionais entre sistemas de transição rotulados.

Formulários

Na ciência da computação , o coalgebra surgiu como uma maneira conveniente e adequadamente geral de especificar o comportamento de sistemas e estruturas de dados que são potencialmente infinitos, por exemplo, classes em programação orientada a objetos , fluxos e sistemas de transição . Enquanto a especificação algébrica lida com o comportamento funcional, normalmente usando tipos de dados indutivos gerados por construtores, a especificação coalgébrica se preocupa com o comportamento modelado por tipos de processos coindutivos que são observáveis ​​por seletores, muito no espírito da teoria dos autômatos . Um papel importante é desempenhado aqui pelos coalgebras finais , que são conjuntos completos de comportamentos possivelmente infinitos, como riachos. A lógica natural para expressar propriedades de tais sistemas é a lógica modal coalgébrica .

Veja também

• Álgebra inicial
• Coindução
• Coalgebra

Referências

• B. Jacobs e J. Rutten, A Tutorial on (Co) Algebras and (Co) Induction. EATCS Bulletin 62, 1997, p.222-259 .
• Jan JMM Rutten: Universal coalgebra: a theory of systems. Theor. Comput. Sci. 249 (1): 3-80 (2000) .
• J. Adámek, Introdução ao coalgebra. Teoria e aplicações das categorias 14 (2005), 157-199
• B. Jacobs, Introdução ao Coalgebra. Rumo à Matemática dos Estados e Observações (rascunho do livro)
• Yde Venema: Autômatos e Lógica de Ponto Fixo: uma Perspectiva Coalgébrica. Information and Computation, 204 (2006) 637-678 .

links externos

• CALCO 2009: Conferência sobre Álgebra e Coálgebra em Ciência da Computação
• CALCO 2011