Monoide

En álgebra abstracta , un monoide es un conjunto dotado de una operación binaria asociativa y un elemento neutro . Por ejemplo, los números naturales, junto con la suma, forman un monoide, cuyo elemento neutro es 0 .

Los monoides son semigrupos con identidad. Este tipo de estructuras algebraicas aparecen en diversas ramas de las matemáticas.

Las funciones de un conjunto en sí mismo forman un monoide con respecto a la composición de funciones. De forma más general, en teoría de categorías , los morfismos de un objeto en sí mismo forman un monoide y, a la inversa, un monoide puede considerarse una categoría con un único objeto.

En informática y programación , el conjunto de cadenas construidas a partir de un conjunto dado de caracteres es un monoide libre . Los monoides de transición y los monoides sintácticos se utilizan para describir máquinas de estados finitos . Los monoides de traza y los monoides de historial proporcionan la base para los cálculos de procesos y la computación concurrente .

En la informática teórica , el estudio de los monoides es fundamental para la teoría de autómatas ( teoría de Krohn-Rhodes ) y la teoría de lenguajes formales ( problema de la altura de la estrella ).

Consulte la sección sobre semigrupos para conocer la historia del tema y otras propiedades generales de los monoides.

Un conjunto S equipado con una operación binaria S × S → S , que denotaremos • , es un monoide si satisface los dos axiomas siguientes:

Asociatividad

Para todos los a , b y c en S , se cumple la ecuación ( a • b ) • c = a • ( b • c ) .

Elemento de identidad

Existe un elemento e en S tal que para cada elemento a en S , se cumplen las igualdades e • a = a y a • e = a .

En otras palabras, un monoide es un semigrupo con un elemento identidad . También puede pensarse como un magma con asociatividad e identidad. El elemento identidad de un monoide es único. ^{[ a ]} ​​Por esta razón, la identidad se considera una operación constante , es decir, 0 -aria (o nula). Por lo tanto, el monoide se caracteriza por la especificación de la tripleta ( S , • , e ) .

Dependiendo del contexto, el símbolo de la operación binaria puede omitirse, de modo que la operación se denota por yuxtaposición ; por ejemplo, los axiomas del monoide pueden escribirse ( ab ) c = a ( bc ) y ea = ae = a . Esta notación no implica que se trate de números que se multiplican.

Un grupo es un caso especial de monoide en el que cada elemento tiene un inverso.

• De los 16 operadores booleanos binarios posibles , cuatro poseen una identidad bilateral que además es conmutativa y asociativa. Estos cuatro operadores hacen que el conjunto {Falso, Verdadero} sea un monoide conmutativo. Según las definiciones estándar, AND y XNOR tienen como identidad Verdadero , mientras que XOR y OR tienen como identidad Falso . Los monoides de AND y OR son idempotentes, a diferencia de los de XOR y XNOR.
• El conjunto de los números naturales N = {0, 1, 2, ...} es un monoide conmutativo bajo la suma (elemento neutro 0 ) o la multiplicación (elemento neutro 1 ). Un submonoide de N bajo la suma se denomina monoide numérico .
• El conjunto de enteros positivos N ∖ {0} es un monoide conmutativo bajo la multiplicación (elemento identidad 1 ).
• Dado un conjunto A , el conjunto de subconjuntos de A es un monoide conmutativo bajo la intersección (el elemento identidad es el propio A ).
• Dado un conjunto A , el conjunto de subconjuntos de A es un monoide conmutativo bajo la unión (el elemento identidad es el conjunto vacío ).
• Generalizando el ejemplo anterior, todo semirretículo acotado es un monoide conmutativo idempotente .
  • En particular, cualquier retículo acotado puede dotarse de una estructura monoide de intersección y de una de unión . Los elementos identidad son, respectivamente, la parte superior e inferior del retículo. Al ser retículos, las álgebras de Heyting y las álgebras booleanas poseen estas estructuras monoides.
• Todo conjunto unitario { x } cerrado bajo una operación binaria • forma el monoide trivial (de un elemento), que también es el grupo trivial .
• Todo grupo es un monoide y todo grupo abeliano es un monoide conmutativo.
• Cualquier semigrupo S puede convertirse en un monoide simplemente adjuntando un elemento e que no pertenezca a S y definiendo e • s = s = s • e para todo s ∈ S. Esta conversión de cualquier semigrupo a monoide se realiza mediante el functor libre entre la categoría de semigrupos y la categoría de monoides. ^{[ 3 ]}
  • Así, un monoide idempotente (a veces conocido como de búsqueda inicial ) puede formarse adjuntando un elemento identidad e al semigrupo cero izquierdo sobre un conjunto S. El monoide opuesto (a veces llamado de búsqueda final ) se forma a partir del semigrupo cero derecho sobre S.
    • Adjunte una identidad e al semigrupo de ceros por la izquierda con dos elementos {lt, gt} . Entonces, el monoide idempotente resultante {lt, e , gt} modela el orden lexicográfico de una secuencia dados los órdenes de sus elementos, donde e representa la igualdad.
• El conjunto subyacente de cualquier anillo , con la suma o la multiplicación como operación. (Por definición, un anillo tiene un elemento neutro multiplicativo 1 ).
  • Los números enteros , racionales , reales o complejos , con la suma o la multiplicación como operación. ^{[ 4 ]}
  • El conjunto de todas las matrices de n por n sobre un anillo dado, donde la operación es la suma o la multiplicación de matrices .
• El conjunto de todas las cadenas finitas sobre un alfabeto fijo Σ forma un monoide cuya operación es la concatenación de cadenas . La cadena vacía actúa como elemento neutro. Este monoide se denota como Σ ^∗ y se denomina monoide libre sobre Σ . No es conmutativo si Σ tiene al menos dos elementos.
• Dado cualquier monoide M , el monoide opuesto M ^op tiene el mismo conjunto portador y elemento neutro que M , y su operación se define por x • ^op y = y • x . Cualquier monoide conmutativo es el monoide opuesto de sí mismo.
• Dados dos conjuntos M y N dotados de estructura monoide (o, en general, cualquier número finito de monoides, M ₁ , ..., M _k ), su producto cartesiano M × N , con la operación binaria y el elemento identidad definidos en las coordenadas correspondientes, llamado producto directo , es también un monoide (respectivamente, M ₁ × ⋅⋅⋅ × M _k ). ^{[ 5 ]}
• Fijemos un monoide M. El conjunto de todas las funciones de un conjunto dado a M también es un monoide. El elemento identidad es una función constante que asigna cualquier valor a la identidad de M ; la operación asociativa se define punto por punto .
• Fijemos un monoide M con la operación • y elemento identidad e , y consideremos su conjunto potencia P ( M ) que consta de todos los subconjuntos de M. Una operación binaria para tales subconjuntos se puede definir por S • T = { s • t  : s ∈ S , t ∈ T } . Esto convierte P ( M ) en un monoide con elemento identidad { e } . De la misma manera, el conjunto potencia de un grupo G es un monoide bajo el producto de subconjuntos del grupo .
• Sea S un conjunto. El conjunto de todas las funciones S → S forma un monoide bajo la composición de funciones . La identidad es simplemente la función identidad . También se le llama monoide de transformación completa de S. Si S es finito con n elementos, el monoide de funciones sobre S es finito con n × ⁿ elementos.
• Generalizando el ejemplo anterior, sea C una categoría y X un objeto de C. El conjunto de todos los endomorfismos de X , denotado End _C ( X ) , forma un monoide bajo la composición de morfismos . Para más información sobre la relación entre la teoría de categorías y los monoides, véase más abajo.
• El conjunto de clases de homeomorfismo de superficies compactas con la suma conexa . Su elemento unitario es la clase de la 2-esfera ordinaria. Además, si a denota la clase del toro , y b denota la clase del plano proyectivo, entonces cada elemento c del monoide tiene una expresión única de la forma c = na + mb donde n es un entero positivo y m = 0, 1 o 2 . Tenemos 3 b = a + b .
• Sea ⟨ f ⟩ un monoide cíclico de orden n , es decir, ⟨ f ⟩ = { f ⁰ , f ¹ , ..., f ^{n −1} } . Entonces f ⁿ = f ^k para algún 0 ≤ k < n . Cada k de este tipo da un monoide distinto de orden n , y cada monoide cíclico es isomorfo a uno de ellos. Además, f puede considerarse como una función en los puntos {0, 1, 2, ..., n −1} dada por

$${\displaystyle {\begin{bmatrix}0&1&2&\cdots &n-2&n-1\\1&2&3&\cdots &n-1&k\end{bmatrix}}}$$o, equivalentemente$${\displaystyle f(i):={\begin{cases}i+1,&{\text{si }}0\leq i<n-1\\k,&{\text{si }}i=n-1.\end{cases}}}$$

La multiplicación de elementos en ⟨ f ⟩ viene dada entonces por la composición de funciones.

Cuando k = 0 , la función f es una permutación de {0, 1, 2, ..., n −1} y da el único grupo cíclico de orden n .

Según los axiomas del monoide, el elemento identidad e es único, ya que si e y f fueran elementos identidad de un monoide, entonces e = ef = f .

Sea M un monoide, con la operación binaria denotada por • y el elemento identidad denotado por e . Entonces, una M -acción (izquierda) (o acción izquierda sobre M ) es un conjunto X junto con una operación ⋅  : M × X → X que es compatible con la estructura del monoide de la siguiente manera:

• para todo x en X : e ⋅ x = x ;
• para todo a , b en M y x en X : a ⋅ ( b ⋅ x ) = ( a • b ) ⋅ x .

Este es el análogo en la teoría de monoides de una acción de grupo (izquierda) . Los actos M derechos se definen de manera similar. Un monoide con un acto también se conoce como monoide operador . Ejemplos importantes incluyen los sistemas de transición de semiautómatas . Un semigrupo de transformación puede convertirse en un monoide operador mediante la adición de la transformación identidad.

Un homomorfismo entre dos monoides ( M , ∗) y ( N , •) es una función f  : M → N tal que

• f ( x ∗ y ) = f ( x ) • f ( y ) para todo x , y en M
• f ( e _M ) = e _N ,

donde e _M y e _N son las identidades en M y N respectivamente. Los homomorfismos de monoides a veces se denominan simplemente morfismos de monoides .

No todo homomorfismo de semigrupo entre monoides es un homomorfismo de monoides, ya que puede que no mapee la identidad a la identidad del monoide objetivo, aunque la identidad sea la identidad de la imagen del homomorfismo. ^{[ d ]} Por ejemplo, consideremos [ Z ] _n , el conjunto de clases de residuos módulo n equipado con la multiplicación. En particular, [1] _n es el elemento identidad. La función f  : [ Z ] ₃ → [ Z ] ₆ dada por [ k ] ₃ ↦ [3 k ] ₆ es un homomorfismo de semigrupo, ya que [3 k ⋅ 3 l ] ₆ = [9 kl ] ₆ = [3 kl ] ₆ . Sin embargo, f ([1] ₃ ) = [3] ₆ ≠ [1] ₆ , por lo que un homomorfismo de monoides es un homomorfismo de semigrupos entre monoides que asigna la identidad del primer monoide a la identidad del segundo monoide y esta última condición no puede omitirse.

En cambio, un homomorfismo de semigrupo entre grupos es siempre un homomorfismo de grupo , ya que necesariamente conserva la identidad (porque, en el grupo objetivo del homomorfismo, el elemento identidad es el único elemento x tal que x ⋅ x = x ).

Un homomorfismo de monoides biyectivo se denomina isomorfismo de monoides . Se dice que dos monoides son isomorfos si existe un isomorfismo de monoides entre ellos.

Se puede dar una presentación a los monoides , de forma similar a como se especifican los grupos mediante una presentación de grupo . Esto se logra especificando un conjunto de generadores Σ y un conjunto de relaciones sobre el monoide libre Σ ^∗ . Para ello, se extienden las relaciones binarias (finitas) sobre Σ ^∗ a congruencias de monoides y, a continuación, se construye el monoide cociente, como se describió anteriormente.

Dada una relación binaria R ⊂ Σ ^∗ × Σ ^∗ , se define su clausura simétrica como R ∪ R ⁻¹ . Esto se puede extender a una relación simétrica E ⊂ Σ ^∗ × Σ ^∗ definiendo x ~ _E y si y solo si x = sut e y = svt para algunas cadenas u , v , s , t ∈ Σ ^∗ con ( u , v ) ∈ R ∪ R ⁻¹ . Finalmente, se toma la clausura reflexiva y transitiva de E , que es entonces una congruencia de monoide.

En la situación típica, la relación R se da simplemente como un conjunto de ecuaciones, de modo que R = { u ₁ = v ₁ , ..., u _n = v _n } . Así, por ejemplo,

${\displaystyle \langle p,q\,\vert \;pq=1\rangle }$

es la presentación ecuacional para el monoide bicíclico , y

${\displaystyle \langle a,b\,\vert \;aba=baa,bba=bab\rangle }$

es el monoide plástico de grado 2 (tiene orden infinito). Los elementos de este monoide plástico se pueden escribir como${\displaystyle a^{i}b^{j}(ba)^{k}}$para los enteros i , j , k , como muestran las relaciones, ba conmuta con a y b .

Los monoides pueden considerarse una clase especial de categorías . De hecho, los axiomas requeridos de una operación monoide son exactamente los requeridos de la composición de morfismos cuando se restringe al conjunto de todos los morfismos cuyo origen y destino es un objeto dado. ^{[ 8 ]} Es decir,

Un monoide es, esencialmente, lo mismo que una categoría con un solo objeto.

Más precisamente, dado un monoide ( M , •) , se puede construir una pequeña categoría con un solo objeto y cuyos morfismos son los elementos de M . La composición de morfismos viene dada por la operación de monoide • . 

Asimismo, los homomorfismos de monoides son simplemente funtores entre categorías de objetos individuales. ^{[ 8 ]} Por lo tanto, esta construcción da una equivalencia entre la categoría de monoides (pequeños) Mon y una subcategoría completa de la categoría de categorías (pequeñas) Cat . De manera similar, la categoría de grupos es equivalente a otra subcategoría completa de Cat .

En este sentido, la teoría de categorías puede considerarse una extensión del concepto de monoide. Muchas definiciones y teoremas sobre monoides pueden generalizarse a categorías pequeñas con más de un objeto. Por ejemplo, un cociente de una categoría con un objeto es simplemente un monoide cociente.

Los monoides, al igual que otras estructuras algebraicas, también forman su propia categoría, Mon , cuyos objetos son monoides y cuyos morfismos son homomorfismos de monoides. ^{[ 8 ]}

También existe la noción de objeto monoide , que es una definición abstracta de lo que es un monoide en una categoría. Un objeto monoide en Set es simplemente un monoide.

En informática, muchos tipos de datos abstractos pueden dotarse de una estructura monoide. Un patrón común consiste en " combinar " o "acumular" una secuencia de elementos de un monoide para obtener un valor final. Por ejemplo, muchos algoritmos iterativos necesitan actualizar un "total acumulado" en cada iteración; este patrón puede expresarse elegantemente mediante una operación monoide. Alternativamente, la asociatividad de las operaciones monoides permite paralelizar la operación empleando una suma de prefijos o un algoritmo similar, para así utilizar eficientemente múltiples núcleos o procesadores.

Dada una secuencia de valores de tipo M con elemento identidad ε y operación asociativa • , la operación de plegado se define de la siguiente manera:  $${\displaystyle \mathrm {fold} :M^{*}\rightarrow M=\ell \mapsto {\begin{cases}\varepsilon &{\text{if }}\ell =\mathrm {nil} \\m\bullet \mathrm {fold} \,\ell '&{\text{if }}\ell =\mathrm {cons} \,m\,\ell '\end{cases}}}$$

Además, cualquier estructura de datos puede "plegarse" de forma similar, dada una serialización de sus elementos. Por ejemplo, el resultado de "plegar" un árbol binario puede variar según se recorra el árbol en preorden o en postorden .

Una aplicación de los monoides en informática es el modelo de programación MapReduce (véase Codificación de MapReduce como un monoide con plegado izquierdo ). En informática, MapReduce consta de dos o tres operaciones. Dado un conjunto de datos, "Map" consiste en asignar datos arbitrarios a elementos de un monoide específico. "Reduce" consiste en plegar esos elementos, de modo que al final se obtenga un único elemento.

Por ejemplo, si tenemos un multiconjunto , en un programa se representa como un mapa de elementos a sus números. En este caso, los elementos se denominan claves. El número de claves distintas puede ser demasiado grande, y en ese caso, el multiconjunto se fragmenta. Para finalizar la reducción correctamente, la etapa de "reorganización" reagrupa los datos entre los nodos. Si no necesitamos este paso, todo el proceso Map/Reduce consiste en mapeo y reducción; ambas operaciones son paralelizable, la primera debido a su naturaleza elemento a elemento, la segunda debido a la asociatividad del monoide.

Un monoide completo es un monoide conmutativo equipado con una operación de suma infinita .${\displaystyle \Sigma _{I}}$para cualquier conjunto de índices I tal que ^{[ 9 ] [ 10 ] [ 11 ] [ 12 ]}$${\displaystyle \sum _{i\in \emptyset }{m_{i}}=0;\quad \sum _{i\in \{j\}}{m_{i}}=m_{j};\quad \sum _{i\in \{j,k\}}{m_{i}}=m_{j}+m_{k}\quad {\text{ for }}j\neq k}$$ y $${\displaystyle \sum _{j\in J}{\sum _{i\in I_{j}}{m_{i}}}=\sum _{i\in I}m_{i}\quad {\text{ if }}\bigcup _{j\in J}I_{j}=I{\text{ and }}I_{j}\cap I_{j'}=\emptyset \quad {\text{ for }}j\neq j'}$$.

Un monoide conmutativo ordenado es un monoide conmutativo M junto con un orden parcial ≤ tal que a ≥ 0 para todo a ∈ M , y a ≤ b implica a + c ≤ b + c para todo a , b , c ∈ M.

Un monoide continuo es un monoide conmutativo ordenado ( M , ≤) en el que cada subconjunto dirigido tiene una cota superior mínima , y ​​estas cotas superiores mínimas son compatibles con la operación de monoide: $${\displaystyle a+\sup S=\sup(a+S)}$$ para cada a ∈ M y subconjunto dirigido S de M .

Si ( M , ≤) es un monoide continuo, entonces para cualquier conjunto de índices I y colección de elementos ( a _i ) _{i ∈ I} , se puede definir $${\displaystyle \sum _{I}a_{i}=\sup _{{\text{finite }}E\subset I}\;\sum _{E}a_{i},}$$ y M junto con esta operación de suma infinita es un monoide completo. ^{[ 12 ]}

• monoide cartesiano
• Relaciones de Green
• Mónada (programación funcional)
• Semianillo y álgebra de Kleene
• Problema de altura de las estrellas
• Plaza védica
• Frobenioide

• "Monoide" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Weisstein, Eric W. "Monoide" . MathWorld .
• Monoide en PlanetMath .