
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
Sies una categoría yes un endofunctor de, entonces un- El álgebra es una tupla, dóndees un objeto deyes un- morfismo. El objetoSe 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 un-álgebraa un-álgebraes un-morfismode tal manera que, según el siguiente diagrama conmutativo :

Equipados con estos morfismos,Las álgebras constituyen una categoría.
La construcción doble es-coalgebras, que son objetosjunto con un morfismo.
Ejemplos
Grupos
Clásicamente, un grupo es un conjuntocon una ley de grupo, con, 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 conjunto) porcon, ycon. Aquídenota el conjunto con un elemento, lo que permite identificar elementoscon morfismos.
Entonces es posible escribir los axiomas de un grupo en términos de funciones (nótese la ausencia del cuantificador existencial):
- ,
- ,
- .
Entonces esto se puede expresar con diagramas conmutativos: [ 1 ] [ 2 ]
Ahora usa el coproducto (la unión disjunta de conjuntos) para pegar los tres morfismos en uno solo:de acuerdo a
- :{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 un-álgebra dondees el functorSin embargo, lo contrario no es necesariamente cierto. Algunos-álgebra dondees el functorno 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.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 grupos de Lie son-á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: 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 . 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 x ≤ y ). 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: 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ículos se basa tanto en la teoría del orden como en el álgebra universal.
Reaparición
Consideremos el functorque envía un conjuntoa. Aquí,denota la categoría de conjuntos,denota el coproducto usual dado por la unión disjunta , yes un objeto terminal (es decir, cualquier conjunto unitario ). Entonces, el conjunto de números naturales junto con la función—que es el coproducto de las funcionesy—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 .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
- ↑ Las flechas verticales sin etiquetas en el segundo diagrama deben ser únicas ya que * es terminal.
- ↑ Estrictamente hablando, (i,id) y (id,i) están etiquetados de manera inconsistente con los otros diagramas ya que estos morfismos se "diagonalizan" primero.
- 1 2 Philip Wadler: ¡ Tipos recursivos gratis! Archivado el 16 de octubre de 2007 en Wayback Machine. Universidad de Glasgow, junio de 1990. Borrador.
- ↑ 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 .
Enlaces externos
- 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
- Teoría de categorías
- Programación funcional