álgebra F

El diagrama conmutativo, que define una propiedad requerida por los morfismos de la categoría original , de modo que puedan ser morfismos de la categoría recién definida de F -álgebras.

En matemáticas , específicamente en teoría de categorías , las álgebras F generalizan la noción de estructura algebraica . Reescribir las leyes algebraicas en términos de morfismos elimina todas las referencias a elementos cuantificados de los axiomas, y estas leyes algebraicas pueden luego unirse en términos de un único funtor F , la firma .

Las álgebras F también se pueden utilizar para representar estructuras de datos utilizadas en programación , como listas y árboles .

Los principales conceptos relacionados son las F -álgebras iniciales que pueden servir para resumir el principio de inducción y las F -coálgebras de construcción dual .

Definición

Si es una categoría y es un endofunctor de , entonces el análgebra es una tupla , donde es un objeto de y es un morfismo . El objeto se llama portador del álgebra. Cuando el contexto lo permite, a menudo se hace referencia a las álgebras solo por su portador en lugar de por la tupla. ${\displaystyle C}$ ${\displaystyle F:C\rightarrow C}$ ${\displaystyle C}$ ${\displaystyle F}$ ${\displaystyle (A,\alpha )}$ ${\displaystyle A}$ ${\displaystyle C}$ ${\displaystyle \alpha }$ ${\displaystyle C}$ ${\displaystyle F(A)\rightarrow A}$ ${\displaystyle A}$

Un homomorfismo de un -álgebra a un -álgebra es un -morfismo tal que , según el siguiente diagrama conmutativo : ${\displaystyle F}$ ${\displaystyle (A,\alpha )}$ ${\displaystyle F}$ ${\displaystyle (B,\beta )}$ ${\displaystyle C}$ ${\displaystyle f:A\rightarrow B}$ ${\displaystyle f\circ \alpha =\beta \circ F(f)}$

Equipadas con estos morfismos, las álgebras constituyen una categoría. ${\displaystyle F}$

Las construcciones duales son -coalgebras, que son objetos unidos con un morfismo . ${\displaystyle F}$ ${\displaystyle A^{*}}$ ${\displaystyle \alpha ^{*}:A^{*}\rightarrow F(A^{*})}$

Ejemplos

Grupos

Clásicamente, un grupo es un conjunto con una ley de grupo , con , que satisface tres axiomas: la existencia de un elemento identidad, la existencia de una inversa para cada elemento del grupo y la asociatividad. ${\displaystyle G}$ ${\displaystyle m:G\times G\rightarrow G}$ ${\displaystyle m(x,y)=x\cdot y}$

Para poner esto en un marco categórico, primero defina la identidad y la inversa como funciones (morfismos del conjunto ) por con y con . Aquí se denota el conjunto con un elemento , lo que permite identificar elementos con morfismos . ${\displaystyle G}$ ${\displaystyle e:1\rightarrow G}$ ${\displaystyle e(*)=1}$ ${\displaystyle i:G\rightarrow G}$ ${\displaystyle i(x)=x^{-1}}$ ${\displaystyle 1}$ ${\displaystyle 1=\left\{*\right\}}$ ${\displaystyle x\in G}$ ${\displaystyle 1\rightarrow G}$

Entonces es posible escribir los axiomas de un grupo en términos de funciones (obsérvese que el cuantificador existencial está ausente):

• ${\displaystyle \forall x\in G,\forall y\in G,\forall z\in G,m(m(x,y),z)=m(x,m(y,z))}$,
• ${\displaystyle \forall x\in G,m(e(*),x)=m(x,e(*))=x}$,
• ${\displaystyle \forall x\in G,m(i(x),x)=m(x,i(x))=e(*)}$.

Entonces esto se puede expresar con diagramas conmutativos: ^{[1] [2]}

                                    

Ahora use el coproducto (la unión disjunta de conjuntos) para unir los tres morfismos en uno: según ${\displaystyle \alpha =e+i+m}$

${\displaystyle {\begin{matrix}\alpha :{1}+G+G\times G&\to &G,\\*&\mapsto &1,\\x&\mapsto &x^{-1},\\(x,y)&\mapsto &x\cdot y.\end{matrix}}}$

Por tanto, un grupo es un -álgebra donde está el funtor . Sin embargo, lo contrario no es necesariamente cierto. Algunas álgebras donde está el funtor no son grupos. ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle F(G)=1+G+G\times G}$ ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle F(G)=1+G+G\times G}$

La construcción anterior se utiliza para definir objetos de grupo sobre una categoría arbitraria con productos finitos y un objeto terminal . Cuando la categoría admite coproductos finitos , los objetos del grupo son -álgebras. Por ejemplo, los grupos finitos son -álgebras en la categoría de conjuntos finitos y los grupos de Lie son -álgebras en la categoría de variedades suaves con mapas suaves . ${\displaystyle 1}$ ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle F}$

Estructuras algebraicas

Yendo un paso por delante del álgebra universal , la mayoría de las estructuras algebraicas son álgebras F. Por ejemplo, los grupos abelianos son F -álgebras para el mismo funtor F ( G ) = 1 + G + G × G que para los grupos, con un axioma adicional para la conmutatividad: m ∘ t = m , donde t ( x , y ) = ( y , x ) es la transpuesta en G x G .

Los monoides son F -álgebras de firma F ( M ) = 1 + M × M . En la misma línea, los semigrupos son F -álgebras de firma F ( S ) = S × S

Los anillos , dominios y campos también son F -álgebras con una firma que involucra dos leyes +,•: R × R → R, una identidad aditiva 0: 1 → R , una identidad multiplicativa 1: 1 → R y un inverso aditivo para cada uno. elemento -: R → R . Como todas estas funciones comparten el mismo codominio R, se pueden unir en una función de firma única 1 + 1 + R + R × R + R × R → R , con axiomas para expresar asociatividad, distributividad , etc. Esto hace anillos F -álgebras en la categoría de conjuntos con firma 1 + 1 + R + R × R + R × R .

Alternativamente, podemos mirar el funtor F ( R ) = 1 + R × R en la categoría de grupos abelianos . En ese contexto, la multiplicación es un homomorfismo, lo que significa m ( x  +  y , z ) = m ( x , z ) +  m ( y , z ) y m ( x , y  +  z ) = m ( x , y ) +  m ( x , z ), que son precisamente las condiciones de distributividad. Por lo tanto, un anillo es un F -álgebra de firma 1 + R × R sobre la categoría de grupos abelianos que satisface dos axiomas (asociatividad e identidad para la multiplicación).

Cuando llegamos a espacios vectoriales y módulos , el funtor de firma incluye una multiplicación escalar k × E → E , y la firma F ( E ) = 1 + E + k × E está parametrizada por k sobre la categoría de campos o anillos.

Las álgebras sobre un campo pueden verse como F -álgebras de firma 1 + 1 + A + A × A + A × A + k × A sobre la categoría de conjuntos, de firma 1 + A × A sobre la categoría de módulos (a módulo con una multiplicación interna), y de firma k × A sobre la categoría de anillos (un anillo con una multiplicación escalar), cuando son asociativos y unitarios.

Enrejado

No todas las estructuras matemáticas son F -álgebras. Por ejemplo, un poset P puede definirse en términos categóricos con un morfismo s : P × P → Ω, en un clasificador de subobjetos (Ω = {0,1} en la categoría de conjuntos y s ( x , y )=1 precisamente cuando x ≤ y ). Los axiomas que restringen los morfismos s para definir un poset pueden reescribirse en términos de morfismos. Sin embargo, como el codominio de s es Ω y no P , no es un F -álgebra.

Sin embargo, las redes , que son órdenes parciales en las que cada dos elementos tienen un supremo y un mínimo, y en particular los órdenes totales , son F -álgebras. Esto se debe a que pueden definirse de manera equivalente en términos de operaciones algebraicas: x ∨ y = inf( x , y ) y x ∧ y = sup( x , y ), sujeto a ciertos axiomas (conmutatividad, asociatividad, absorción e idempotencia). . Por tanto, son F -álgebras de firma P x P + P x P . A menudo se dice que la teoría de la red se basa tanto en la teoría del orden como en el álgebra universal.

Reaparición

Considere el functor que envía un conjunto a . Aquí, denota la categoría de conjuntos, denota el coproducto habitual dado por la unión disjunta y es un objeto terminal (es decir, cualquier conjunto singleton ). Entonces, el conjunto de los números naturales junto con la función —que es el coproducto de las funciones y— es un F -álgebra. ${\displaystyle F:\mathrm {\bf {Set}} \to \mathrm {\bf {Set}} }$ ${\displaystyle X}$ ${\displaystyle 1+X}$ ${\displaystyle \mathrm {\bf {Set}} }$ ${\displaystyle +}$ ${\displaystyle 1}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle [\mathrm {zero} ,\mathrm {succ} ]:1+\mathbb {N} \to \mathbb {N} }$ ${\displaystyle \mathrm {zero} :1\mapsto 0}$ ${\displaystyle \mathrm {succ} :n\mapsto n+1}$

F inicial -álgebra

Si la categoría de F -álgebras para un endofunctor F dado tiene un objeto inicial , se llama álgebra inicial . El álgebra del ejemplo anterior es un álgebra inicial. Varias estructuras de datos finitos utilizadas en programación , como listas y árboles , se pueden obtener como álgebras iniciales de endofunctores específicos. ${\displaystyle (\mathbb {N} ,[\mathrm {zero} ,\mathrm {succ} ])}$

Los tipos definidos mediante el uso de una construcción de punto mínimo fijo con funtor F pueden considerarse como un álgebra F inicial , siempre que la parametricidad sea válida para el tipo. ^[3]

Véase también Álgebra universal .

Terminal F -coálgebra

De forma dual , existe una relación similar entre las nociones de punto fijo máximo y la coalgebra F terminal . Estos se pueden utilizar para permitir objetos potencialmente infinitos manteniendo al mismo tiempo una fuerte propiedad de normalización . ^[3] En el lenguaje de programación Charity, fuertemente normalizado (es decir, cada programa termina en él), se pueden usar tipos de datos coinductivos para lograr resultados sorprendentes, permitiendo la definición de construcciones de búsqueda para implementar funciones tan "fuertes" como la función de Ackermann . ^[4]

Ver también

• Álgebras para una mónada
• tipo de datos algebraicos
• catamorfismo
• dialgebra

Notas

1. Las flechas verticales sin etiquetas en el segundo diagrama deben ser únicas ya que * es terminal.
2. Estrictamente hablando, (i,id) y (id,i) están etiquetados de manera inconsistente con los otros diagramas ya que estos morfismos "diagonalizan" primero.
3. Philip Wadler: ¡Tipos recursivos gratis! Archivado el 16 de octubre de 2007 en la Universidad Wayback Machine de Glasgow, junio de 1990. Borrador.
4. Robin Cockett : Pensamientos caritativos (ps Archivado el 29 de diciembre de 2020 en Wayback Machine y ps.gz Archivado el 29 de diciembre de 2020 en Wayback Machine )

Referencias

• Pierce, Benjamín C. (1991). " F -Álgebras". Teoría de categorías básicas para informáticos . ISBN 0-262-66071-7.
• Barr, Michael; Pozos, Charles (1990). Teoría de categorías para la informática . Nueva York: Prentice Hall. pag. 355.ISBN _ 0131204866. OCLC  19126000.

enlaces externos

• Programación categórica con tipos inductivos y coinductivos (Archivado el 30 de noviembre de 2020 en Wayback Machine ) por Varmo Vene
• Philip Wadler: ¡Tipos recursivos gratis! (Archivado el 30 de noviembre de 2020 en Wayback Machine ) Universidad de Glasgow, junio de 1990. Borrador.
• Álgebra y coalgebra (Archivado el 27 de abril de 2019 en Wayback Machine ) de CLiki
• B. Jacobs, J. Rutten: Tutorial sobre (co)álgebras y (co)inducción. Boletín de la Asociación Europea de Informática Teórica, vol. 62, 1997, archivado el 12 de febrero de 2021 en la Wayback Machine.
• Comprensión de las álgebras F (archivado el 4 de agosto de 2020 en Wayback Machine ) por Bartosz Milewski