F-coálgebra

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

${\displaystyle F}$-coalgebras son duales a -álgebras . Así como la clase de todas las álgebras para una firma dada y la teoría ecuacional forman una variedad , la clase de todas las coalgebras 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 -coalgebra 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 -coalgebra a otro -coalgebra es un morfismo ${\displaystyle F}$ ${\displaystyle (A,\alpha )}$ ${\displaystyle F}$ ${\displaystyle (B,\beta )}$

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

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

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

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

Ejemplos

Considere 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 están los llamados números connaturales, que consisten en 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 )}$

De manera más general, arregle algún conjunto y considere el functor que envía a . Entonces una -coálgebra es una corriente finita o infinita sobre el alfabeto , donde es el conjunto de estados y es la función de transición de estados. La aplicación de la función de transición de estado a un estado puede producir dos resultados posibles: ya sea un elemento de junto con el siguiente estado de la secuencia, o el elemento del conjunto singleton como un "estado final" separado que indica que no hay más valores en la corriente. ${\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 dicho objeto coalgebraico puede tener la forma , que se descompone fácilmente en una colección de "selectores", "observadores", "métodos" . Los casos especiales de interés práctico incluyen observadores que generan 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 de conjuntos potencia sobre la categoría de conjuntos, considerado como un functor covariante. Las P -coalgebras están en correspondencia biyectiva con conjuntos con una relación binaria. Ahora arregle 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.

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, normalmente utilizando tipos de datos inductivos generados por los constructores, la especificación coalgebraica se ocupa del comportamiento modelado por tipos de procesos coinductivos que son observables por los selectores, muy en el espíritu de la teoría de los autómatas . Aquí juegan un papel importante las coalgebras finales , que son conjuntos completos de comportamientos posiblemente infinitos, como las corrientes. La lógica natural para expresar propiedades de tales sistemas es la lógica modal coalgebraica . ^{[ cita necesaria ]}

Ver también

• Álgebra inicial
• Coinducción
• carbongebra

Referencias

• B. Jacobs y J. Rutten, Tutorial sobre (co)álgebras y (co)inducción. Boletín EATCS 62, 1997, páginas 222-259.
• Jan JMM Rutten: Coalgebra universal: una teoría de sistemas. Teor. Computadora. Ciencia. 249(1): 3-80 (2000).
• J. Adámek, Introducción a la coalgebra. Teoría y aplicaciones de las 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 Informática
• CALCO 2011