Álgebra F

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

En matemáticas , específicamente en la teoría de categorías , las F - álgebras 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 entonces unirse en términos de un único funtor F , la signatura .

Las F -álgebras 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 encapsular 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 una - álgebra es una tupla , donde es un objeto de y es un - morfismo . El objeto se denomina 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 -coálgebras, que son objetos juntos 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 definamos la identidad y la inversa como funciones (morfismos del conjunto ) por con , y con . Aquí 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}$

Es posible entonces escribir los axiomas de un grupo en términos de funciones (nótese cómo 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 usemos el coproducto (la unión disjunta de conjuntos) para pegar 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 lo tanto, un grupo es una -álgebra donde es el funtor . Sin embargo, lo inverso no es necesariamente cierto. Algunas -álgebras donde es 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 de 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 funciones suaves . ${\displaystyle 1}$ ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle F}$

Estructuras algebraicas

Yendo un paso más allá del álgebra universal , la mayoría de las estructuras algebraicas son F -álgebras. 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 signatura F ( M ) = 1 + M × M . En la misma línea, los semigrupos son F -álgebras de signatura F ( S ) = S × S

Los anillos , dominios y cuerpos 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 una inversa aditiva para cada elemento -: R → R . Como todas estas funciones comparten el mismo codominio R , pueden ser pegadas en una única función de firma 1 + 1 + R + R × R + R × R → R , con axiomas para expresar asociatividad, distributividad , etc. Esto hace que los anillos sean F -álgebras en la categoría de conjuntos con firma 1 + 1 + R + R × R + R × R .

Alternativamente, podemos considerar el funtor F ( R ) = 1 + R × R en la categoría de grupos abelianos . En ese contexto, la multiplicación es un homomorfismo, es decir, 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 una F -álgebra de signatura 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 cuerpo pueden verse como F -álgebras de signatura 1 + 1 + A + A × A + A × A + k × A sobre la categoría de conjuntos, de signatura 1 + A × A sobre la categoría de módulos (un módulo con una multiplicación interna), y de signatura k × A sobre la categoría de anillos (un anillo con una multiplicación escalar), cuando son asociativas y unitarias.

Enrejado

No todas las estructuras matemáticas son F -álgebras. Por ejemplo, un conjunto parcial 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 el morfismo s para definir un conjunto parcial pueden reescribirse en términos de morfismos. Sin embargo, como el codominio de s es Ω y no P , no es una F -álgebra.

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

Reaparición

Consideremos el funtor que envía un conjunto a . Aquí, denota la categoría de conjuntos, denota el coproducto usual dado por la unión disjunta , y es un objeto terminal (es decir, cualquier conjunto singleton ). Entonces, el conjunto de 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}$

InicialF-álgebra

Si la categoría de F -álgebras para un endofunctor dado F tiene un objeto inicial , se denomina á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 la construcción del punto mínimo fijo con el funtor F pueden considerarse como un F -álgebra inicial, siempre que se cumpla la parametricidad para el tipo. ^[3]

Véase también Álgebra universal .

TerminalF-coálgebra

De manera dual , existe una relación similar entre las nociones de máximo punto fijo y F -coálgebra terminal. Estas pueden usarse para permitir objetos potencialmente infinitos mientras se mantiene la propiedad de normalización fuerte . ^[3] En el lenguaje de programación Charity, que es fuertemente normalizador (es decir, cada programa termina en él), los tipos de datos coinductivos pueden usarse para lograr resultados sorprendentes, lo que permite la definición de construcciones de búsqueda para implementar funciones tan “fuertes” como la función de Ackermann . ^[4]

Véase 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 se "diagonalizan" primero.
3. Philip Wadler: ¡Tipos recursivos gratis! Archivado el 16 de octubre de 2007 en Wayback Machine. Universidad de Glasgow, junio de 1990. Borrador.
4. Robin Cockett : Pensamientos caritativos (psArchivado el 29 de diciembre de 2020 en Wayback Machine y ps.gzArchivado el 29 de diciembre de 2020 en Wayback Machine )

Referencias

• Pierce, Benjamin C. (1991). " F -Álgebras". Teoría de categorías básicas para científicos informáticos . ISBN 0-262-66071-7.
• Barr, Michael; Wells, Charles (1990). Teoría de categorías para la ciencia informática . Nueva York: Prentice Hall. p. 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: Un tutorial sobre (co)álgebras y (co)inducción. Boletín de la Asociación Europea de Ciencias Informáticas Teóricas, vol. 62, 1997, archivado el 12 de febrero de 2021 en Wayback Machine.
• Comprensión de las F-álgebras (archivado el 4 de agosto de 2020 en Wayback Machine ) por Bartosz Milewski