F -coálgebra

En matemáticas , específicamente en teoría de categorías , un${\displaystyle F}$-coalgebra es una estructura definida según un functor${\displaystyle F}$, con propiedades específicas como se define a continuación. Tanto para álgebras como para coálgebras , un functor ^{[ 1 ] [ 2 ]} es una forma conveniente y general de organizar una firma . Esto tiene aplicaciones en ciencias de la computación : ejemplos de coálgebras incluyen evaluación perezosa , estructuras de datos infinitas , como flujos , y también sistemas de transición .

${\displaystyle F}$-las coálgebras son duales a${\displaystyle F}$-álgebras . Así como la clase de todas las álgebras para una signatura y teoría ecuacional dada forman una variedad , también lo hace la clase de todas${\displaystyle F}$-las coalgebras que satisfacen una teoría ecuacional dada forman una covariedad, donde la signatura viene dada por${\displaystyle F}$.

Dejar

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

ser un endofunctor en una categoría${\displaystyle {\mathcal {C}}}$. Un${\displaystyle F}$-coalgebra es un objeto${\displaystyle A}$de${\displaystyle {\mathcal {C}}}$junto con un morfismo

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

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

Un${\displaystyle F}$-homomorfismo de coalgebra de${\displaystyle (A,\alpha )}$a otro${\displaystyle F}$-coálgebra ${\displaystyle (B,\beta )}$es un morfismo

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

en${\displaystyle {\mathcal {C}}}$de tal manera que

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

Por lo tanto, el${\displaystyle F}$-Las coalgebras para un functor F dado constituyen una categoría.

Consideremos el endofunctor${\displaystyle X\mapsto X\sqcup \{*\}:\mathbf {Set} \to \mathbf {Set} }$que envía un conjunto a su unión disjunta con el conjunto unitario${\displaystyle \{\ast \}}$. Una coálgebra de este endofunctor viene dada por${\displaystyle ({\overline {\mathbb {N} }},\alpha )}$, dónde${\displaystyle {\overline {\mathbb {N} }}=\{0,1,2,\ldots \}\sqcup \{\infty \}}$son los llamados números conaturales, que consisten en los enteros no negativos y también el infinito, y la función${\displaystyle \alpha }$es dado por${\displaystyle \alpha (0)=\ast }$,${\displaystyle \alpha (n)=n-1}$para${\displaystyle n=1,2,\ldots }$y${\displaystyle \alpha (\infty )=\infty }$. De hecho,${\displaystyle ({\overline {\mathbb {N} }},\alpha )}$es la coalgebra terminal de este endofunctor.

En términos más generales, fije algún conjunto${\displaystyle A}$y consideremos el functor${\displaystyle F:\mathbf {Establecer} \longrightarrow \mathbf {Establecer} }$que envía${\displaystyle X}$a${\displaystyle (X\times A)\cup \{1\}}$. Entonces un${\displaystyle F}$-coálgebra${\displaystyle \alpha :X\longrightarrow (X\times A)\cup \{1\}=FX}$es una secuencia finita o infinita sobre el alfabeto${\displaystyle A}$, dónde${\displaystyle X}$es el conjunto de estados y${\displaystyle \alpha }$es la función de transición de estado. Aplicar la función de transición de estado a un estado puede producir dos resultados posibles: o bien un elemento de${\displaystyle A}$junto con el siguiente estado del flujo, o el elemento del conjunto unitario${\displaystyle \{1\}}$como un "estado final" separado que indica que no hay más valores en el flujo.

En muchas aplicaciones prácticas, la función de transición de estado de dicho objeto coalgebraico puede tener la forma${\displaystyle X\rightarrow f_{1}\times f_{2}\times \ldots \times f_{n}}$, que se factoriza fácilmente en una colección de "selectores", "observadores" y "métodos".${\displaystyle X\rightarrow f_{1},\,X\rightarrow f_{2}\,\ldots \,X\rightarrow f_{n}}$. Entre los casos especiales de interés práctico se incluyen los observadores que producen valores de atributos y los métodos mutadores de la forma${\displaystyle X\rightarrow X^{A_{1}\times \ldots \times A_{n}}}$tomando parámetros adicionales y produciendo estados. Esta descomposición es dual a la descomposición inicial.${\displaystyle F}$-álgebras en sumas de 'constructores'.

Sea P la construcción de conjuntos potencia en la categoría de conjuntos , considerada como un functor covariante. Las P -coalgebras están en correspondencia biyectiva con conjuntos con una relación binaria . Ahora fijemos otro conjunto, A. Entonces las coalgebras para el endofunctor P ( A ×(-)) están en correspondencia biyectiva con sistemas de transición etiquetados , y los homomorfismos entre coalgebras corresponden a bisimulaciones funcionales entre sistemas de transición etiquetados.

En informática , la coalgebra se ha consolidado como una forma conveniente y suficientemente general de especificar el comportamiento de sistemas y estructuras de datos potencialmente infinitos, como las clases en la programación orientada a objetos , los flujos y los sistemas de transición . Mientras que la especificación algebraica se ocupa del comportamiento funcional, generalmente mediante tipos de datos inductivos generados por constructores, la especificación coalgebraica se centra en el comportamiento modelado por tipos de procesos coinductivos observables mediante selectores, siguiendo la línea de la teoría de autómatas . Un papel importante lo desempeñan aquí las coalgebras finales , que son conjuntos completos de comportamientos posiblemente infinitos, como los flujos. La lógica natural para expresar las propiedades de estos sistemas es la lógica modal coalgebraica .

• Álgebra inicial
• Coinducción
• Coálgebra

• B. Jacobs y J. Rutten, Un tutorial sobre (co)álgebras y (co)inducción. Boletín EATCS 62, 1997, págs. 222-259 .
• Jan JMM Rutten: Coalgebra universal: una teoría de sistemas. Theor. Comput. Sci. 249(1): 3-80 (2000) .
• J. Adámek, Introducción a la coálgebra. Teoría y aplicaciones de las categorías 14 (2005), 157-199
• B. Jacobs, Introducción a la Coálgebra. Hacia las Matemáticas de los Estados y las Observaciones (borrador del libro)
• Yde Venema: Autómatas y lógicas de punto fijo: una perspectiva coalgebraica. Information and Computation, 204 (2006) 637-678 .

• CALCO 2009: Conferencia sobre Álgebra y Coálgebra en Ciencias de la Computación
• CALCO 2011