Articulo de referencia

Á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 de F -álgebras reciente...

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 de F -álgebras recientemente definida.

En matemáticas , específicamente en 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 functor 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 la construcción dual F -coalgebras .

Definición

Sido{\displaystyle C}es una categoría yF:dodo{\displaystyle F:C\rightarrow C}es un endofunctor dedo{\displaystyle C}, entonces unF{\displaystyle F}- El álgebra es una tupla(A,α){\displaystyle (A,\alpha )}, dóndeA{\displaystyle A}es un objeto dedo{\displaystyle C}yα{\displaystyle \alpha }es undo{\displaystyle C}- morfismoF(A)A{\displaystyle F(A)\rightarrow A}. El objetoA{\displaystyle A}Se le 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.

Un homomorfismo de unF{\displaystyle F}-álgebra(A,α){\displaystyle (A,\alpha )}a unF{\displaystyle F}-álgebra(B,β){\displaystyle (B,\beta )}es undo{\displaystyle C}-morfismoF:AB{\displaystyle f:A\rightarrow B}de tal manera queFα=βF(F){\displaystyle f\circ \alpha =\beta \circ F(f)}, según el siguiente diagrama conmutativo :

Equipados con estos morfismos,F{\displaystyle F}Las álgebras constituyen una categoría.

La construcción doble esF{\displaystyle F}-coalgebras, que son objetosA{\displaystyle A^{*}}junto con un morfismoα:AF(A){\displaystyle \alpha ^{*}:A^{*}\rightarrow F(A^{*})}.

Ejemplos

Grupos

Clásicamente, un grupo es un conjuntoGRAMO{\displaystyle G}con una ley de grupometro:GRAMO×GRAMOGRAMO{\displaystyle m:G\times G\rightarrow G}, conmetro(incógnita,y)=incógnitay{\displaystyle m(x,y)=x\cdot y}, que satisfacen tres axiomas: la existencia de un elemento neutro, la existencia de un inverso para cada elemento del grupo y la asociatividad.

Para poner esto en un marco categórico, primero definamos la identidad y la inversa como funciones (morfismos del conjuntoGRAMO{\displaystyle G}) pormi:1GRAMO{\displaystyle e:1\rightarrow G}conmi()=1{\displaystyle e(*)=1}, yi:GRAMOGRAMO{\displaystyle i:G\rightarrow G}coni(incógnita)=incógnita1{\displaystyle i(x)=x^{-1}}. Aquí1{\displaystyle 1}denota el conjunto con un elemento1={}{\displaystyle 1=\left\{*\right\}}, lo que permite identificar elementosincógnitaGRAMO{\displaystyle x\in G}con morfismos1GRAMO{\displaystyle 1\rightarrow G}.

Entonces es posible escribir los axiomas de un grupo en términos de funciones (nótese la ausencia del cuantificador existencial):

  • incógnitaGRAMO,yGRAMO,zGRAMO,metro(metro(incógnita,y),z)=metro(incógnita,metro(y,z)){\displaystyle \forall x\in G,\forall y\in G,\forall z\in G,m(m(x,y),z)=m(x,m(y,z))},
  • incógnitaGRAMO,metro(mi(),incógnita)=metro(incógnita,mi())=incógnita{\displaystyle \forall x\in G,m(e(*),x)=m(x,e(*))=x},
  • incógnitaGRAMO,metro(i(incógnita),incógnita)=metro(incógnita,i(incógnita))=mi(){\displaystyle \forall x\in G,m(i(x),x)=m(x,i(x))=e(*)}.

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

Diagrama conmutativo que demuestra la propiedad de asociación.            Diagrama conmutativo que demuestra la propiedad de invertibilidad.            Diagrama conmutativo que demuestra la propiedad de identidad.            

Ahora usa el coproducto (la unión disjunta de conjuntos) para pegar los tres morfismos en uno solo:α=mi+i+metro{\displaystyle \alpha =e+i+m}de acuerdo a

α:1+GRAMO+GRAMO×GRAMOGRAMO,1,incógnitaincógnita1,(incógnita,y)incógnitay.{\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 unF{\displaystyle F}-álgebra dondeF{\displaystyle F}es el functorF(GRAMO)=1+GRAMO+GRAMO×GRAMO{\displaystyle F(G)=1+G+G\times G}Sin embargo, lo contrario no es necesariamente cierto. AlgunosF{\displaystyle F}-álgebra dondeF{\displaystyle F}es el functorF(GRAMO)=1+GRAMO+GRAMO×GRAMO{\displaystyle F(G)=1+G+G\times G}no son grupos.

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

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 functor F ( G ) = 1 + G + G × G que para los grupos, con un axioma adicional para la conmutatividad: mt = 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 . De la misma forma, los semigrupos son F -álgebras de signatura F ( S ) = S × S

Los anillos , dominios y cuerpos también son F -álgebras con una signatura 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 elemento -: R R. Como todas estas funciones comparten el mismo codominio R, se pueden unir en una única función de signatura 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 signatura 1 + 1 + R + R × R + R × R.

Alternativamente, podemos considerar el functor F ( R ) = 1 + R × R en la categoría de grupos abelianos . En ese contexto, la multiplicación es un homomorfismo, lo que significa que 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 álgebra F 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 los espacios vectoriales y módulos , el functor de signatura incluye una multiplicación escalar k × E E , y la signatura F ( E ) = 1 + E + k × E está parametrizada por k sobre la categoría de cuerpos 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 parcialmente ordenado P puede definirse en términos categóricos con un morfismo s : P × P Ω, sobre un clasificador de subobjetos (Ω = {0,1} en la categoría de conjuntos y s ( x , y )=1 precisamente cuando xy ). Los axiomas que restringen el morfismo s para definir un conjunto parcialmente ordenado 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, los retículos , que son órdenes parciales en los que cada par de elementos tiene un supremo y un ínfimo, y en particular los órdenes totales , son F -álgebras. Esto se debe a que pueden definirse de forma equivalente en términos de las operaciones algebraicas: xy = inf( x , y ) y xy = 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ículos se basa tanto en la teoría del orden como en el álgebra universal.

Reaparición

Consideremos el functorF:SmitSmit{\displaystyle F:\mathrm {\bf {Set}} \to \mathrm {\bf {Set}} }que envía un conjuntoincógnita{\displaystyle X}a1+incógnita{\displaystyle 1+X}. Aquí,Smit{\displaystyle \mathrm {\bf {Set}} }denota la categoría de conjuntos,+{\displaystyle +}denota el coproducto usual dado por la unión disjunta , y1{\displaystyle 1}es un objeto terminal (es decir, cualquier conjunto unitario ). Entonces, el conjunto norte{\displaystyle \mathbb {N} }de números naturales junto con la función[zmiro,sdodo]:1+nortenorte{\displaystyle [\mathrm {zero} ,\mathrm {succ} ]:1+\mathbb {N} \to \mathbb {N} }—que es el coproducto de las funcioneszmiro:10{\displaystyle \mathrm {zero} :1\mapsto 0}ysdodo:nortenorte+1{\displaystyle \mathrm {succ} :n\mapsto n+1}—es un álgebra F.

Álgebra F inicial

Si la categoría de F -álgebras para un endofunctor F dado tiene un objeto inicial , se llama álgebra inicial .(norte,[zmiro,sdodo]){\displaystyle (\mathbb {N} ,[\mathrm {zero} ,\mathrm {succ} ])}En el ejemplo anterior, se trata de un álgebra inicial. Diversas estructuras de datos finitas utilizadas en programación , como listas y árboles , pueden obtenerse como álgebras iniciales de endofuntores específicos.

Los tipos definidos mediante la construcción de punto fijo mínimo con functor F pueden considerarse como un álgebra F inicial, siempre que se cumpla la parametricidad para el tipo. [ 3 ]

Véase también Álgebra universal .

Terminal F - álgebra

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

Véase también

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. 1 2 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 ( ps Archivado el 29/12/2020 en Wayback Machine y ps.gz Archivado el 29/12/2020 en Wayback Machine )

Referencias

  • Pierce, Benjamin C. (1991). « F -Álgebras». Teoría básica de categorías para científicos informáticos . MIT Press. ISBN 0-262-66071-7.
  • Barr, Michael; Wells, Charles (1990). Teoría de categorías para la informática . Nueva York: Prentice Hall. pág.  355. ISBN 0131204866OCLC 19126000 .​ 
  • Programación categórica con tipos inductivos y coinductivos ( Archivado el 30/11/2020 en Wayback Machine ) por Varmo Vene
  • Philip Wadler: ¡ Tipos recursivos gratis! ( Archivado el 30/11/2020 en Wayback Machine ) Universidad de Glasgow, junio de 1990. Borrador.
  • Álgebra y coalgebra ( Archivado el 27/04/2019 en Wayback Machine ) de CLiki
  • B. Jacobs, J. Rutten: Un tutorial sobre (co)álgebras e (co)inducción. Boletín de la Asociación Europea de Ciencias de la Computación Teórica , 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