F-coálgebra

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

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

Definición

Dejar

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

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

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

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

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

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

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

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

Por lo tanto, las -coálgebras para un funtor dado F constituyen una categoría. ${\displaystyle F}$

Ejemplos

Consideremos el endofunctor que envía un conjunto a su unión disjunta con el conjunto singleton . Una coalgebra de este endofunctor está dada por , donde es el llamado número connatural, que consiste en los números enteros no negativos y también el infinito, y la función está dada por , para y . De hecho, es la coalgebra terminal de este 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 )}$

En términos más generales, fije un conjunto y considere el funtor que envía a . Entonces, una -coálgebra es un flujo finito o infinito sobre el alfabeto , donde es el conjunto de estados y es la función de transición de estado. La aplicación de la función de transición de estado a un estado puede producir dos resultados posibles: un elemento de junto con el siguiente estado del flujo, o el elemento del conjunto singleton como un "estado final" separado que indica que no hay más valores en el flujo. ${\displaystyle A}$ ${\displaystyle F:\mathbf {Set} \longrightarrow \mathbf {Set} }$ ${\displaystyle X}$ ${\displaystyle (X\times A)\cup \{1\}}$ ${\displaystyle F}$ ${\displaystyle \alpha :X\longrightarrow (X\times A)\cup \{1\}=FX}$ ${\displaystyle A}$ ${\displaystyle X}$ ${\displaystyle \alpha }$ ${\displaystyle A}$ ${\displaystyle \{1\}}$

En muchas aplicaciones prácticas, la función de transición de estado de un objeto coalgebraico de este tipo puede tener la forma , que se factoriza fácilmente en una colección de "selectores", "observadores", "métodos" . Los casos especiales de interés práctico incluyen observadores que producen valores de atributos y métodos mutadores de la forma que toman parámetros adicionales y producen estados. Esta descomposición es dual a la descomposición de álgebras iniciales en sumas de "constructores". ${\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}$

Sea P la construcción del conjunto potencia sobre la categoría de conjuntos, considerada como un funtor covariante. Las P -coálgebras están en correspondencia biyectiva con conjuntos con una relación binaria. Ahora fijemos otro conjunto, A . Entonces las coalgebras para el endofuntor 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.

Aplicaciones

En informática , la coalgebra ha surgido como una forma conveniente y adecuadamente general de especificar el comportamiento de sistemas y estructuras de datos que son potencialmente infinitos, por ejemplo, clases en programación orientada a objetos , flujos y sistemas de transición . Mientras que la especificación algebraica se ocupa del comportamiento funcional, generalmente utilizando tipos de datos inductivos generados por constructores, la especificación coalgebraica se ocupa del comportamiento modelado por tipos de procesos coinductivos que son observables por selectores, en gran medida en el espíritu de la teoría de autómatas . Aquí desempeñan un papel importante las coalgebras finales , que son conjuntos completos de comportamientos posiblemente infinitos, como los flujos. La lógica natural para expresar propiedades de tales sistemas es la lógica modal coalgebraica . ^{[ cita requerida ]}

Véase también

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

Referencias

• 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 coalgebra. Teoría y aplicaciones de categorías 14 (2005), 157-199
• B. Jacobs, Introducción a la coalgebra. Hacia las matemáticas de estados y observaciones (borrador de libro)
• Yde Venema: Autómatas y lógica de punto fijo: una perspectiva coalgebraica. Información y computación, 204 (2006) 637-678.

Enlaces externos

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