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 se pueden unir en términos de un solo funtor F , la firma .
Las F -algebras también se pueden utilizar para representar estructuras de datos utilizadas en la programación , como listas y árboles .
Los principales conceptos relacionados son F -algebras iniciales que pueden servir para encapsular el principio de inducción, y la construcción dual F -coalgebras .
Definición
Si C es una categoría y F : C → C es un endofunctor de C , entonces un F - álgebra es una tupla ( A , α), donde A es un objeto de C y α es un C - morfismo F ( A ) → A . El objeto A se llama portador del álgebra. Cuando está permitido por el contexto, las álgebras a menudo se refieren a su portador solo en lugar de la tupla.
Un homomorfismo de una F -álgebra ( A , α) a una F -álgebra ( B , β) es un C -morfismo f : A → B tal que f ∘ α = β ∘ F ( f ), de acuerdo con el siguiente conmutativo diagrama :
Equipadas con estos morfismos, las F -álgebras constituyen una categoría.
La construcción dual son F -coalgebras, que son objetos A * junto con un morfismo α * : A * → F ( A * ).
Ejemplos de
Grupos
Clásicamente, un grupo en un conjunto G con un grupo de leyes m : G x G → G , con m ( x , y ) = x • y , satisface tres axiomas: la existencia de un elemento de identidad, la existencia de un inverso para cada elemento del grupo y asociatividad.
Para poner esto en un marco categórico, primero defina la identidad y la inversa como funciones (morfismos del conjunto G ) por e : 1 → G con e (*) = 1, ei : G → G con i ( x ) = x −1 . Aquí 1 denota el conjunto con un elemento 1 = {*}, que permite identificar elementos x∈ G con morfismos 1 → G .
Entonces es posible escribir los axiomas de un grupo en términos de funciones (observe cómo el cuantificador existencial está ausente):
- ∀ x∈ G , ∀ y∈ G , ∀ z∈ G , m ( m ( x , y ), z ) = m ( x , m ( y , z )),
- ∀ x∈ G , m ( e (*), x ) = m ( x , e (*)) = x ,
- ∀ x∈ G , m ( i (x), x ) = m ( x , i (x)) = e (*).
Luego, elimine las referencias a los elementos de G (que también eliminarán los cuantificadores universales):
- m ∘ ( m , Id ) = m ∘ ( Id , m ),
- m ∘ ( e , Id ) = m ∘ ( Id , e ) = Id ,
- m ∘ ( i , Id ) = m ∘ ( Id , i ) = e .
Que es lo mismo que reclamar conmutatividad para los siguientes diagramas: [1]
Ahora use el coproducto (la unión disjunta de conjuntos) para pegar los tres morfismos en uno: α = e + i + m según
Esto define un grupo como un F -algebra donde F es el funtor F ( G ) = 1 + G + G × 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 F -álgebras. Por ejemplo, los grupos finitos son F -álgebras en la categoría de conjuntos finitos y los grupos de Lie son F -álgebras en la categoría de variedades suaves con mapas suaves .
Estructuras algebraicas
Yendo un paso por delante 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 .
Monoides son F -álgebras de la 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 una aditiva inversa para cada uno. elemento -: R → R . Como todas estas funciones comparten el mismo codominio R, se pueden pegar en una sola función de firma 1 + 1 + R + R × R + R × R → R , con axiomas para expresar asociatividad, distributividad , etc. Esto hace los anillos F -álgebras en la categoría de conjuntos con la 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 ) ym ( 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 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 functor 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 se pueden ver 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 multiplicación interna), y de firma k × A sobre la categoría de anillos (un anillo con 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 ys ( x , y ) = 1 precisamente cuando x ≤ y ). Los axiomas que restringen morfismo 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 celosías en las que cada dos elementos tienen un supremum y un infimum, y en particular órdenes totales , son F -álgebras. Esto se debe a que se pueden definir de manera equivalente en términos de las operaciones algebraicas: x ∨ y = inf ( x , y ) yx ∧ y = sup ( x , y ), sujeto a ciertos axiomas (conmutatividad, asociatividad, absorción e idempotencia). . Por lo tanto son F -álgebras de la firma P x P + P x P . A menudo se dice que la teoría de la celosía se basa tanto en la teoría de órdenes como en el álgebra universal.
Reaparición
Considere el functor que manda un set a . Aquí, denota la categoría de conjuntos, denota el coproducto habitual dado por la unión disjunta , yes un objeto terminal (es decir, cualquier conjunto singleton ). Entonces, el setde números naturales junto con la función—Que es el coproducto de las funciones y —Es una F -álgebra.
F- álgebra inicial
Si la categoría de F -álgebras para un endofunctor F dado tiene un objeto inicial , se llama álgebra inicial . El álgebraen el ejemplo anterior es un álgebra inicial. Varias estructuras de datos finitas utilizadas en programación , como listas y árboles , se pueden obtener como álgebras iniciales de endofunctores específicos.
Los tipos definidos mediante el uso de la construcción de punto mínimo fijo con el functor F pueden considerarse como un F- álgebra inicial , siempre que la parametricidad sea válida para el tipo. [2]
Véase también Álgebra universal .
Terminal F -coalgebra
De manera dual , existe una relación similar entre las nociones de punto fijo mayor y F -coalgebra terminal . Estos pueden usarse para permitir objetos potencialmente infinitos mientras se mantiene una fuerte propiedad de normalización . [2] En el lenguaje de programación Charity fuertemente normalizado (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 tan “fuertes” como la función de Ackermann . [3]
Ver también
- Álgebras para una mónada
- Tipo de datos algebraicos
- Catamorfismo
- Dialgebra
Notas
- ^ Las flechas verticales sin etiquetas en el tercer diagrama deben ser únicas ya que * es terminal.
- ^ a b Philip Wadler: ¡ Tipos recursivos gratis! Archivado el 16 de octubre de 2007 en la Universidad Wayback Machine de Glasgow, junio de 1990. Borrador.
- ^ Robin Cockett: Charitable Thoughts ( 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, Benjamin C. (1991). " F -Álgebras". Teoría de categorías básica para informáticos . ISBN 0-262-66071-7.
- Barr, Michael; Wells, Charles (1990). Teoría de categorías para ciencias de la computación . Nueva York: Prentice Hall. pag. 355. ISBN 0131204866. OCLC 19126000 .
enlaces externos
- Programación categórica con tipos inductivos y coinductivos ( Archivado 2020-11-30 en Wayback Machine ) por Varmo Vene
- Philip Wadler: ¡ Tipos recursivos gratis! ( Archivado el 30 de noviembre de 2020 en la Wayback Machine ) Universidad de Glasgow, junio de 1990. Borrador.
- Álgebra y coalgebra ( Archivado el 27 de abril de 2019 en la 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 la Wayback Machine.
- Entendiendo las F-Algebras ( Archivado el 4 de agosto de 2020 en la Wayback Machine ) por Bartosz Milewski