En matemáticas, un semigrupo es una estructura algebraica que consta de un conjunto junto con una operación binaria interna asociativa sobre él.
La operación binaria de un semigrupo suele denotarse multiplicativamente (solo notación, no necesariamente la multiplicación aritmética elemental ): x ⋅ y , o simplemente xy , denota el resultado de aplicar la operación de semigrupo al par ordenado ( x , y ) . La asociatividad se expresa formalmente como ( x ⋅ y ) ⋅ z = x ⋅ ( y ⋅ z ) para todos los x , y y z en el semigrupo.
Los semigrupos pueden considerarse un caso especial de magmas , donde la operación es asociativa, o como una generalización de grupos , sin que se requiera la existencia de un elemento identidad o inversos. [a] Como en el caso de grupos o magmas, la operación de semigrupo no necesita ser conmutativa , por lo que x ⋅ y no es necesariamente igual a y ⋅ x ; un ejemplo bien conocido de operación asociativa pero no conmutativa es la multiplicación de matrices . Si la operación del semigrupo es conmutativa, entonces el semigrupo se llama semigrupo conmutativo o (con menos frecuencia que en el caso análogo de los grupos ) se le puede llamar semigrupo abeliano .
Un monoide es una estructura algebraica intermedia entre semigrupos y grupos, y es un semigrupo que tiene un elemento de identidad , por lo que obedece a todos menos uno de los axiomas de un grupo: no se requiere la existencia de inversos de un monoide. Un ejemplo natural son las cadenas con concatenación como operación binaria y la cadena vacía como elemento de identidad. Restringir a cadenas no vacías da un ejemplo de un semigrupo que no es un monoide. Los enteros positivos con suma forman un semigrupo conmutativo que no es un monoide, mientras que los enteros no negativos sí forman un monoide. Un semigrupo sin un elemento de identidad se puede convertir fácilmente en un monoide simplemente agregando un elemento de identidad. En consecuencia, los monoides se estudian en la teoría de semigrupos más que en la teoría de grupos. No deben confundirse los semigrupos con los cuasigrupos , que son una generalización de grupos en una dirección diferente; la operación en un cuasigrupo no tiene por qué ser asociativa, pero los cuasigrupos preservan de los grupos una noción de división . En general, la división en semigrupos (o en monoides) no es posible.
El estudio formal de los semigrupos se inició a principios del siglo XX. Los primeros resultados incluyen un teorema de Cayley para semigrupos que realiza cualquier semigrupo como semigrupo de transformación , en el que funciones arbitrarias reemplazan el papel de las biyecciones de la teoría de grupos. Un resultado profundo en la clasificación de semigrupos finitos es la teoría de Krohn-Rhodes , análoga a la descomposición de Jordan-Hölder para grupos finitos. Algunas otras técnicas para estudiar semigrupos, como las relaciones de Green , no se parecen en nada a la teoría de grupos.
La teoría de los semigrupos finitos ha sido de particular importancia en la informática teórica desde la década de 1950 debido al vínculo natural entre los semigrupos finitos y los autómatas finitos a través del monoide sintáctico . En teoría de la probabilidad , los semigrupos están asociados con procesos de Markov . [1] En otras áreas de las matemáticas aplicadas , los semigrupos son modelos fundamentales para sistemas lineales invariantes en el tiempo . En las ecuaciones diferenciales parciales , se asocia un semigrupo a cualquier ecuación cuya evolución espacial sea independiente del tiempo.
Existen numerosas clases especiales de semigrupos , semigrupos con propiedades adicionales, que aparecen en aplicaciones particulares. Algunas de estas clases se acercan aún más a los grupos al exhibir algunas propiedades adicionales, pero no todas, de un grupo. De estos mencionamos: semigrupos regulares , semigrupos ortodoxos , semigrupos con involución , semigrupos inversos y semigrupos canceladores . También hay clases interesantes de semigrupos que no contienen ningún grupo excepto el grupo trivial ; ejemplos de este último tipo son las bandas y su subclase conmutativa: las semiredes , que también son estructuras algebraicas ordenadas .
Un semigrupo es un conjunto S junto con una operación binaria ⋅ (es decir, una función ⋅ : S × S → S ) que satisface la propiedad asociativa :
De manera más sucinta, un semigrupo es un magma asociativo .
Una identidad izquierda de un semigrupo S (o más generalmente, magma ) es un elemento e tal que para todo x en S , e ⋅ x = x . De manera similar, una identidad correcta es un elemento f tal que para todo x en S , x ⋅ f = x . Las identidades de izquierda y derecha se denominan identidades unilaterales . Un semigrupo puede tener una o más identidades de izquierda pero ninguna de derecha, y viceversa.
Una identidad bilateral (o simplemente identidad ) es un elemento que es tanto una identidad de izquierda como de derecha. Los semigrupos con identidad bilateral se denominan monoides . Un semigrupo puede tener como máximo una identidad bilateral. Si un semigrupo tiene una identidad bilateral, entonces la identidad bilateral es la única identidad unilateral en el semigrupo. Si un semigrupo tiene tanto una identidad izquierda como una identidad derecha, entonces tiene una identidad bilateral (que por lo tanto es la identidad unilateral única).
Un semigrupo S sin identidad puede estar incrustado en un monoide formado uniendo un elemento e ∉ S a S y definiendo e ⋅ s = s ⋅ e = s para todos los s ∈ S ∪ { e } . [2] [3] La notación S 1 denota un monoide obtenido a partir de S añadiendo una identidad si es necesario ( S 1 = S para un monoide). [3]
De manera similar, cada magma tiene como máximo un elemento absorbente , que en la teoría de semigrupos se llama cero . De manera análoga a la construcción anterior, para cada semigrupo S , se puede definir S 0 , un semigrupo con 0 que incluye S.
La operación de semigrupo induce una operación sobre la colección de sus subconjuntos: dados los subconjuntos A y B de un semigrupo S , su producto A · B , escrito comúnmente como AB , es el conjunto { ab | a en A y b en B }. (Esta noción se define de manera idéntica a la de los grupos ). En términos de esta operación, un subconjunto A se llama
Si A es a la vez un ideal de izquierda y un ideal de derecha, entonces se le llama ideal (o ideal de dos colas ).
Si S es un semigrupo, entonces la intersección de cualquier colección de subsemigrupos de S también es un subsemigrupo de S. Entonces los subsemigrupos de S forman una red completa .
Un ejemplo de semigrupo sin ideal mínimo es el conjunto de números enteros positivos bajo la suma. El ideal mínimo de un semigrupo conmutativo , cuando existe, es un grupo.
Las relaciones de Green , un conjunto de cinco relaciones de equivalencia que caracterizan los elementos en términos de los principales ideales que generan, son herramientas importantes para analizar los ideales de un semigrupo y las nociones de estructura relacionadas.
El subconjunto que tiene la propiedad de que cada elemento conmuta con cualquier otro elemento del semigrupo se llama centro del semigrupo. [4] El centro de un semigrupo es en realidad un subsemigrupo. [5]
Un homomorfismo de semigrupo es una función que preserva la estructura de semigrupo. Una función f : S → T entre dos semigrupos es un homomorfismo si la ecuación
se cumple para todos los elementos a , b en S , es decir, el resultado es el mismo al realizar la operación de semigrupo después o antes de aplicar el mapa f .
Un homomorfismo de semigrupo entre monoides preserva la identidad si es un homomorfismo monoide . Pero hay homomorfismos de semigrupos que no son homomorfismos monoides, por ejemplo, la incrustación canónica de un semigrupo S sin identidad en S 1 . Las condiciones que caracterizan los homomorfismos monoides se analizan más a fondo. Sea f : S 0 → S 1 un homomorfismo de semigrupo. La imagen de f también es un semigrupo. Si S 0 es un monoide con un elemento de identidad e 0 , entonces f ( e 0 ) es el elemento de identidad en la imagen de f . Si S 1 es también un monoide con un elemento de identidad e 1 y e 1 pertenece a la imagen de f , entonces f ( e 0 ) = e 1 , es decir, f es un homomorfismo monoide. En particular, si f es sobreyectiva , entonces es un homomorfismo monoide.
Se dice que dos semigrupos S y T son isomorfos si existe un homomorfismo de semigrupo biyectivo f : S → T . Los semigrupos isomórficos tienen la misma estructura.
Una congruencia de semigrupo ~ es una relación de equivalencia que es compatible con la operación de semigrupo. Es decir, un subconjunto ~ ⊆ S × S que es una relación de equivalencia y x ~ y y u ~ v implica xu ~ yv para cada x , y , u , v en S . Como cualquier relación de equivalencia, una congruencia de semigrupo ~ induce clases de congruencia
y la operación de semigrupo induce una operación binaria ∘ en las clases de congruencia:
Debido a que ~ es una congruencia, el conjunto de todas las clases de congruencia de ~ forma un semigrupo con ∘, llamado semigrupo cociente o semigrupo factorial , y denotado S /~ . La aplicación x ↦ [ x ] ~ es un homomorfismo de semigrupo, llamado aplicación del cociente , sobreyección o proyección canónica ; si S es un monoide, entonces el semigrupo cociente es un monoide con identidad [1] ~ . Por el contrario, el núcleo de cualquier homomorfismo de semigrupo es una congruencia de semigrupo. Estos resultados no son más que una particularización del primer teorema del isomorfismo en álgebra universal . Las clases de congruencia y los monoides factoriales son objetos de estudio en los sistemas de reescritura de cadenas .
Una congruencia nuclear en S es aquella que es el núcleo de un endomorfismo de S. [6]
Un semigrupo S satisface la condición máxima de congruencias si cualquier familia de congruencias en S , ordenadas por inclusión, tiene un elemento máximo. Según el lema de Zorn , esto equivale a decir que se cumple la condición de la cadena ascendente : no existe una cadena infinita estrictamente ascendente de congruencias en S. [7]
Cada ideal I de un semigrupo induce un semigrupo factorial, el semigrupo factorial de Rees , a través de la congruencia ρ definida por x ρ y si x = y , o tanto x como y están en I.
Las siguientes nociones [8] introducen la idea de que un semigrupo está contenido en otro.
Un semigrupo T es un cociente de un semigrupo S si existe un morfismo de semigrupo sobreyectivo de S a T. Por ejemplo, ( Z /2 Z , +) es un cociente de ( Z /4 Z , +) , utilizando el morfismo consistente en tomar el resto módulo 2 de un número entero.
Un semigrupo T divide un semigrupo S , denotado T ≼ S si T es un cociente de un subsemigrupo S. En particular, los subsemigrupos de S dividen a T , mientras que no es necesariamente el caso que haya un cociente de S .
Ambas relaciones son transitivas.
Para cualquier subconjunto A de S existe un subsemigrupo más pequeño T de S que contiene A , y decimos que A genera T. Un solo elemento x de S genera el subsemigrupo { x n | norte ∈ Z + } . Si este es finito, entonces se dice que x es de orden finito , en caso contrario es de orden infinito . Se dice que un semigrupo es periódico si todos sus elementos son de orden finito. Un semigrupo generado por un solo elemento se dice que es monogénico (o cíclico ). Si un semigrupo monogénico es infinito entonces es isomorfo al semigrupo de enteros positivos con la operación de suma. Si es finito y no vacío, entonces debe contener al menos un idempotente . De ello se deduce que todo semigrupo periódico no vacío tiene al menos un idempotente.
Se llama subgrupo a un subsemigrupo que también es un grupo . Existe una estrecha relación entre los subgrupos de un semigrupo y sus idempotentes. Cada subgrupo contiene exactamente un idempotente, es decir, el elemento de identidad del subgrupo. Para cada idempotente e del semigrupo hay un subgrupo máximo único que contiene e . Cada subgrupo máximo surge de esta manera, por lo que existe una correspondencia uno a uno entre idempotentes y subgrupos máximos. Aquí el término subgrupo máximo difiere de su uso estándar en la teoría de grupos.
A menudo se puede decir más cuando el orden es finito. Por ejemplo, todo semigrupo finito no vacío es periódico y tiene un ideal mínimo y al menos un idempotente. El número de semigrupos finitos de un tamaño determinado (mayor que 1) es (obviamente) mayor que el número de grupos del mismo tamaño. Por ejemplo, de las dieciséis "tablas de multiplicar" posibles para un conjunto de dos elementos {a, b }, ocho forman semigrupos [b] , mientras que sólo cuatro de ellos son monoides y sólo dos forman grupos. Para más información sobre la estructura de semigrupos finitos, consulte la teoría de Krohn-Rhodes .
Existe un teorema de estructura para semigrupos conmutativos en términos de semiredes . [10] Una semired (o más precisamente una semired) ( L , ≤) es un conjunto parcialmente ordenado donde cada par de elementos a , b ∈ L tiene un límite inferior máximo , denotado a ∧ b . La operación ∧ convierte a L en un semigrupo que satisface la ley de idempotencia adicional a ∧ a = a .
Dado un homomorfismo f : S → L de un semigrupo arbitrario a una semired, cada imagen inversa S a = f −1 { a } es un semigrupo (posiblemente vacío). Además, S pasa a ser calificado por L , en el sentido de que S a S b ⊆ S a ∧ b .
Si f es sobre, la semired L es isomorfa al cociente de S por la relación de equivalencia ~ tal que x ~ y si y sólo si f ( x ) = f ( y ) . Esta relación de equivalencia es una congruencia de semigrupo, como se definió anteriormente.
Siempre que tomamos el cociente de un semigrupo conmutativo por una congruencia, obtenemos otro semigrupo conmutativo. El teorema de la estructura dice que para cualquier semigrupo conmutativo S , existe una congruencia más fina, tal que el cociente de S por esta relación de equivalencia es una semired. Denotando esta semired por L , obtenemos un homomorfismo f de S a L. Como se mencionó, S se clasifica por esta semired.
Además, los componentes S a son todos semigrupos de Arquímedes . Un semigrupo de Arquímedes es aquel en el que dado cualquier par de elementos x , y , existe un elemento z y n > 0 tal que x n = yz .
La propiedad de Arquímedes se sigue inmediatamente del ordenamiento en la semired L , ya que con este ordenamiento tenemos f ( x ) ≤ f ( y ) si y sólo si x n = yz para algunos z y n > 0 .
El grupo de fracciones o compleción de grupo de un semigrupo S es el grupo G = G ( S ) generado por los elementos de S como generadores y todas las ecuaciones xy = z que se cumplen en S como relaciones . [11] Existe un homomorfismo de semigrupo obvio j : S → G ( S ) que envía cada elemento de S al generador correspondiente. Esto tiene una propiedad universal para morfismos de S a un grupo: [12] dado cualquier grupo H y cualquier homomorfismo de semigrupo k : S → H , existe un homomorfismo de grupo único f : G → H con k = fj . Podemos pensar en G como el grupo "más general " que contiene una imagen homomórfica de S.
Una cuestión importante es caracterizar aquellos semigrupos para los cuales este mapa es una incrustación. Este no tiene por qué ser siempre el caso: por ejemplo, tome S como el semigrupo de subconjuntos de algún conjunto X con intersección teórica de conjuntos como operación binaria (este es un ejemplo de semired). Desde un . A = A es válido para todos los elementos de S , esto debe ser cierto también para todos los generadores de G ( S ), que por lo tanto es el grupo trivial . Es claramente necesario para la integrabilidad que S tenga la propiedad de cancelación . Cuando S es conmutativo esta condición también es suficiente [13] y el grupo de Grothendieck del semigrupo proporciona una construcción del grupo de fracciones. El problema de los semigrupos no conmutativos se remonta al primer artículo importante sobre semigrupos. [14] [15] Anatoly Maltsev dio las condiciones necesarias y suficientes para la integrabilidad en 1937. [16]
La teoría de semigrupos se puede utilizar para estudiar algunos problemas en el campo de las ecuaciones diferenciales parciales . En términos generales, el enfoque de semigrupos consiste en considerar una ecuación diferencial parcial dependiente del tiempo como una ecuación diferencial ordinaria en un espacio funcional. Por ejemplo, considere el siguiente problema de valor inicial/límite para la ecuación de calor en el intervalo espacial (0, 1) ⊂ R y multiplicado por t ≥ 0 :
Sea X = L 2 ((0, 1) R ) el espacio L p de funciones de valores reales integrables al cuadrado con dominio en el intervalo (0, 1) y sea A el operador de segunda derivada con dominio
donde H 2 es un espacio de Sobolev . Entonces, el problema de valor inicial/límite anterior se puede interpretar como un problema de valor inicial para una ecuación diferencial ordinaria en el espacio X :
A nivel heurístico, la solución a este problema "debería" ser u ( t ) = exp( tA ) u 0 . Sin embargo, para un tratamiento riguroso, se debe dar un significado a la exponencial de tA . En función de t , exp( tA ) es un semigrupo de operadores de X hacia sí mismo, tomando el estado inicial u 0 en el momento t = 0 al estado u ( t ) = exp( tA ) u 0 en el momento t . Se dice que el operador A es el generador infinitesimal del semigrupo.
El estudio de semigrupos iba por detrás del de otras estructuras algebraicas con axiomas más complejos como grupos o anillos . Varias fuentes [17] [18] atribuyen el primer uso del término (en francés) a J.-A. de Séguier en Élements de la Théorie des Groupes Abstraits (Elementos de la teoría de grupos abstractos) en 1904. El término se utiliza en inglés en 1908 en la Teoría de grupos de orden finito de Harold Hinton .
Anton Sushkevich obtuvo los primeros resultados no triviales sobre semigrupos. Su artículo de 1928 "Über die endlichen Gruppen ohne das Gesetz der eindeutigen Umkehrbarkeit" ("Sobre grupos finitos sin la regla de invertibilidad única") determinó la estructura de semigrupos simples finitos y demostró que el ideal mínimo (o las relaciones de clase J de Green ) de un semigrupo finito es simple. [18] A partir de ese momento, David Rees , James Alexander Green , Evgenii Sergeevich Lyapin , Alfred H. Clifford y Gordon Preston sentaron las bases de la teoría de semigrupos . Los dos últimos publicaron una monografía en dos volúmenes sobre la teoría de semigrupos en 1961 y 1967 respectivamente. En 1970, una nueva revista llamada Semigroup Forum (actualmente editada por Springer Verlag ) se convirtió en una de las pocas revistas matemáticas dedicadas enteramente a la teoría de semigrupos.
La teoría de la representación de semigrupos fue desarrollada en 1963 por Boris Schein utilizando relaciones binarias en un conjunto A y composición de relaciones para el producto de semigrupos. [19] En una conferencia algebraica en 1972, Schein examinó la literatura sobre B A , el semigrupo de relaciones en A . [20] En 1997, Schein y Ralph McKenzie demostraron que todo semigrupo es isomorfo a un semigrupo transitivo de relaciones binarias. [21]
En los últimos años, los investigadores en el campo se han especializado más con monografías dedicadas que aparecen sobre clases importantes de semigrupos, como semigrupos inversos , así como monografías que se centran en aplicaciones en la teoría de autómatas algebraicos, particularmente para autómatas finitos, y también en análisis funcional .
Si se elimina el axioma de asociatividad de un semigrupo, el resultado es un magma , que no es más que un conjunto M equipado con una operación binaria cerrada M × M → M.
Generalizando en una dirección diferente, un semigrupo n -ario (también n -semigrupo , semigrupo poliádico o semigrupo multiario ) es una generalización de un semigrupo a un conjunto G con una operación n -aria en lugar de una operación binaria. [22] La ley asociativa se generaliza de la siguiente manera: la asociatividad ternaria es ( abc ) de = a ( bcd ) e = ab ( cde ) , es decir, la cadena abcde con tres elementos adyacentes cualesquiera entre corchetes. La asociatividad n -aria es una cadena de longitud n + ( n − 1) con n elementos adyacentes entre corchetes. Un semigrupo biario es solo un semigrupo. Otros axiomas conducen a un grupo n -ario .
Una tercera generalización es la semigrupoide , en la que se elimina el requisito de que la relación binaria sea total. Como las categorías generalizan los monoides de la misma manera, un semigrupoide se comporta de manera muy parecida a una categoría pero carece de identidades.
En ocasiones, varios autores han considerado infinitas generalizaciones de semigrupos conmutativos. [C]