Monoide

En álgebra abstracta , una rama de las matemáticas , un monoide es un conjunto dotado de una operación binaria asociativa y un elemento identidad . Por ejemplo, los números enteros no negativos con suma forman un monoide, siendo el elemento identidad el 0 .

Los monoides son semigrupos con identidad. Estas estructuras algebraicas aparecen en varias ramas de las matemáticas.

Las funciones de un conjunto sobre sí mismo forman un monoide con respecto a la composición de funciones. De manera más general, en la teoría de categorías , los morfismos de un objeto sobre sí mismo forman un monoide y, a la inversa, un monoide puede considerarse como 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 históricos proporcionan una base para los cálculos de procesos y la computación concurrente .

En 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 del lenguaje formal ( problema de la altura de las estrellas ).

Consulte semigrupo para conocer la historia del tema y algunas otras propiedades generales de los monoides.

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

Asociatividad

Para todos a , b y c en S , la ecuación ( a • b ) • c = a • ( b • c ) es válida.

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 considerarse 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 nularia). 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 monoides 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 monoide en el que cada elemento tiene un inverso es un grupo .

Un submonoide de un monoide ( M , •) es un subconjunto N de M que está cerrado bajo la operación monoide y contiene el elemento identidad e de M . ^{[1] [b]} Simbólicamente, N es un submonoide de M si e ∈ N ⊆ M , y x • y ∈ N siempre que x , y ∈ N . En este caso, N es un monoide bajo la operación binaria heredada de M .

Por otra parte, si N es un subconjunto de un monoide que está cerrado bajo la operación monoide, y es un monoide para esta operación heredada, entonces N no siempre es un submonoide, ya que los elementos identidad pueden diferir. Por ejemplo, el conjunto singleton {0} está cerrado bajo la multiplicación, y no es un submonoide del monoide (multiplicativo) de los enteros no negativos .

Se dice que un subconjunto S de M genera M si el submonoide más pequeño de M que contiene a S es M . Si hay un conjunto finito que genera M , entonces se dice que M es un monoide finitamente generado .

Un monoide cuya operación es conmutativa se llama monoide conmutativo (o, menos comúnmente, monoide abeliano ). Los monoides conmutativos a menudo se escriben de forma aditiva. Cualquier monoide conmutativo está dotado de su preordenamiento algebraico ≤ , definido por x ≤ y si existe z tal que x + z = y . ^[2] Una unidad de orden de un monoide conmutativo M es un elemento u de M tal que para cualquier elemento x de M , existe v en el conjunto generado por u tal que x ≤ v . Esto se usa a menudo en caso de que M sea el cono positivo de un grupo abeliano parcialmente ordenado G , en cuyo caso decimos que u es una unidad de orden de G .

Un monoide cuya operación es conmutativa para algunos, pero no todos los elementos, es un monoide de traza ; los monoides de traza ocurren comúnmente en la teoría de computación concurrente .

• De los 16 operadores booleanos binarios posibles , cuatro tienen una identidad bilateral que también es conmutativa y asociativa. Estos cuatro hacen que el conjunto {Falso, Verdadero} sea un monoide conmutativo. Según las definiciones estándar, AND y XNOR tienen la identidad Verdadero mientras que XOR y OR tienen la identidad Falso . Los monoides de AND y OR también son idempotentes mientras que los de XOR y XNOR no lo son.
• El conjunto de números naturales N = {0, 1, 2, ...} es un monoide conmutativo bajo la adición (elemento identidad 0 ) o la multiplicación (elemento identidad 1 ). Un submonoide de N bajo la adición se denomina monoide numérico .
• El conjunto de números 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 intersección (el elemento identidad es el propio A ).
• Dado un conjunto A , el conjunto de subconjuntos de A es un monoide conmutativo bajo unión (el elemento identidad es el conjunto vacío ).
• Generalizando el ejemplo anterior, cada semirretículo acotado es un monoide conmutativo idempotente .
  • En particular, cualquier red acotada puede estar dotada de una estructura monoide de encuentro y de unión . Los elementos de identidad son la parte superior y la parte inferior de la red, respectivamente. Al ser redes, las álgebras de Heyting y las álgebras de Boole están dotadas de estas estructuras monoides.
• Todo conjunto singleton { x } cerrado bajo una operación binaria • forma el monoide trivial (de un elemento), que también es el grupo trivial .
• Cada grupo es un monoide y cada grupo abeliano un monoide conmutativo.
• Cualquier semigrupo S puede convertirse en un monoide simplemente añadiendo un elemento e que no esté en S y definiendo e • s = s = s • e para todo s ∈ S . Esta conversión de cualquier semigrupo en monoide se realiza mediante el funtor libre entre la categoría de semigrupos y la categoría de monoides. ^[3]
  • Por lo tanto, un monoide idempotente (a veces conocido como find-first ) se puede formar al unir un elemento identidad e al semigrupo cero izquierdo sobre un conjunto S. El monoide opuesto (a veces llamado find-last ) 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 adición o multiplicación como operación. (Por definición, un anillo tiene una identidad multiplicativa 1 ).
  • Los números enteros , números racionales , números reales o números complejos , con adición o multiplicación como operación. ^[4]
  • El conjunto de todas las matrices n por n sobre un anillo dado, con suma de matrices o multiplicación de matrices como operación.
• 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 sirve como elemento identidad. Este monoide se denota Σ ^∗ 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 de portadores y elemento identidad que M , y su operación está definida 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]
• Fijar un monoide M . El conjunto de todas las funciones desde un conjunto dado hasta 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 puntualmente .
• Fijemos un monoide M con la operación • y elemento identidad e , y consideremos su conjunto potencia P ( M ) que consiste en 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 a 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 los 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 denomina monoide de transformación completa de S . Si S es finito con n elementos, el monoide de funciones en 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, consulte a continuación.
• El conjunto de clases de homeomorfismo de superficies compactas con la suma conexa . Su elemento unidad 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 en 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 uno de estos k da un monoide distinto de orden n , y cada monoide cíclico es isomorfo a uno de estos.
  Además, f puede considerarse como una función en los puntos {0, 1, 2, ..., n −1} dados 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 entonces dada por la composición de funciones.

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

Los axiomas monoides implican que el elemento identidad e es único: si e y f son elementos identidad de un monoide, entonces e = ef = f .

Para cada entero no negativo n , se puede definir el producto de cualquier secuencia ( a ₁ , ..., a _n ) de n elementos de un monoide recursivamente: sea p ₀ = e y sea p _m = p _{m −1} • a _m para 1 ≤ m ≤ n . ${\displaystyle p_{n}=\textstyle \prod_{i=1}^{n}a_{i}}$

Como caso especial, se pueden definir potencias enteras no negativas de un elemento x de un monoide: x ⁰ = 1 y x ⁿ = x ^{n −1} • x para n ≥ 1 . Entonces x ^{m + n} = x ^m • x ⁿ para todo m , n ≥ 0 .

Un elemento x se llama invertible si existe un elemento y tal que x • y = e e y • x = e . El elemento y se llama inverso de x . Los inversos, si existen, son únicos: si y y z son inversos de x , entonces por asociatividad y = ey = ( zx ) y = z ( xy ) = ze = z . ^[6]

Si x es invertible, digamos con y inversa , entonces se pueden definir potencias negativas de x fijando x ^{− n} = y ⁿ para cada n ≥ 1 ; esto hace que la ecuación x ^{m + n} = x ^m • x ⁿ sea válida para todo m , n ∈ Z .

El conjunto de todos los elementos invertibles de un monoide, junto con la operación •, forma un grupo .

No todo monoide se encuentra dentro de un grupo. Por ejemplo, es perfectamente posible tener un monoide en el que existan dos elementos a y b de modo que a • b = a se cumpla aunque b no sea el elemento identidad. Un monoide de este tipo no puede estar incluido en un grupo, porque en el grupo, al multiplicar ambos lados por el inverso de a, se obtendría que b = e , lo cual no es cierto.

Un monoide ( M , •) tiene la propiedad de cancelación (o es cancelativo) si para todos a , b y c en M , la igualdad a • b = a • c implica b = c , y la igualdad b • a = c • a implica b = c .

Un monoide conmutativo con la propiedad de cancelación siempre se puede incluir en un grupo mediante la construcción del grupo de Grothendieck . Así es como se construye el grupo aditivo de los números enteros (un grupo con la operación + ) a partir del monoide aditivo de los números naturales (un monoide conmutativo con la operación + y la propiedad de cancelación). Sin embargo, un monoide cancellativo no conmutativo no necesita ser integrable en un grupo.

Si un monoide tiene la propiedad de cancelación y es finito , entonces es de hecho un grupo. ^[c]

Los elementos cancelativos por derecha e izquierda de un monoide forman, a su vez, un submonoide (es decir, están cerrados bajo la operación y, obviamente, incluyen la identidad). Esto significa que los elementos cancelativos de cualquier monoide conmutativo pueden extenderse a un grupo.

La propiedad cancelatoria en un monoide no es necesaria para realizar la construcción de Grothendieck – la conmutatividad es suficiente. Sin embargo, si un monoide conmutativo no tiene la propiedad cancelatoria, el homomorfismo del monoide en su grupo de Grothendieck no es inyectivo. Más precisamente, si a • b = a • c , entonces b y c tienen la misma imagen en el grupo de Grothendieck, incluso si b ≠ c . En particular, si el monoide tiene un elemento absorbente , entonces su grupo de Grothendieck es el grupo trivial .

Un monoide inverso es un monoide en el que para cada a en M , existe un único a ⁻¹ en M tal que a = a • a ⁻¹ • a y a ⁻¹ = a ⁻¹ • a • a ⁻¹ . Si un monoide inverso es cancelativo, entonces es un grupo.

En la dirección opuesta, un monoide libre de suma cero es un monoide escrito de forma aditiva en el que a + b = 0 implica que a = 0 y b = 0 : ^[7] equivalentemente, que ningún elemento distinto de cero tiene un inverso aditivo.

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 como sigue:

• para todo x en X : e ⋅ x = x ;
• para todos 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 M -actos de la derecha se definen de manera similar. Un monoide con un acto también se conoce como monoide operador . Ejemplos importantes incluyen sistemas de transición de semiautómatas . Un semigrupo de transformación se puede convertir en un monoide operador mediante la unió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 todos los 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 monoides a veces se denominan simplemente morfismos monoides .

No todo homomorfismo de semigrupo entre monoides es un homomorfismo de monoide, ya que puede no mapear la identidad a la identidad del monoide objetivo, incluso aunque la identidad sea la identidad de la imagen del homomorfismo. ^[d] Por ejemplo, considere [ Z ] _n , el conjunto de clases de residuos módulo n equipado con 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 monoide es un homomorfismo de semigrupo entre monoides que asigna la identidad del primer monoide a la identidad del segundo monoide y la última condición no se puede omitir.

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

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

Se puede dar una presentación a los monoides , de la misma manera que se pueden especificar grupos por medio de una presentación de grupo . Esto se hace especificando un conjunto de generadores Σ y un conjunto de relaciones en el monoide libre Σ ^∗ . Esto se hace extendiendo las relaciones binarias (finitas) en Σ ^∗ a congruencias de monoides y luego construyendo el monoide cociente, como se indicó 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 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áctico de grado 2 (tiene orden infinito). Los elementos de este monoide pláctico pueden escribirse como para los números enteros i , j , k , ya que las relaciones muestran que ba conmuta tanto con a como con b . ${\displaystyle a^{i}b^{j}(ba)^{k}}$

Los monoides pueden considerarse como una clase especial de categorías . De hecho, los axiomas requeridos para una operación monoide son exactamente los requeridos para 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 está dada por la operación monoide  • .

De la misma manera, 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 como 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 el concepto de objeto monoide , que es una definición abstracta de lo que es un monoide en una categoría. Un objeto monoide en un conjunto es simplemente un monoide.

En informática, muchos tipos de datos abstractos pueden dotarse de una estructura monoide. En un patrón común, una secuencia de elementos de un monoide se " pliega " o "acumula" para producir un valor final. Por ejemplo, muchos algoritmos iterativos necesitan actualizar algún tipo de "total acumulado" en cada iteración; este patrón puede expresarse elegantemente mediante una operación monoide. Alternativamente, la asociatividad de las operaciones monoides garantiza que la operación pueda paralelizarse empleando una suma de prefijo o un algoritmo similar, para utilizar varios núcleos o procesadores de manera eficiente.

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 &{\mbox{if }}\ell =\mathrm {nil} \\m\bullet \mathrm {fold} \,\ell '&{\mbox{if }}\ell =\mathrm {cons} \,m\,\ell '\end{cases}}}$

Además, cualquier estructura de datos se puede "plegar" de manera similar, dada una serialización de sus elementos. Por ejemplo, el resultado de "plegar" un árbol binario puede diferir según el recorrido del árbol en preorden o en posorden .

Una aplicación de los monoides en informática es el llamado modelo de programación MapReduce (véase Codificación de Map-Reduce como un monoide con plegado a la izquierda). MapReduce, en informática, 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 produzcamos solo un elemento.

Por ejemplo, si tenemos un multiset , en un programa se representa como un mapa de elementos a sus números. Los elementos se denominan claves en este caso. El número de claves distintas puede ser demasiado grande y, en este caso, el multiset se está fragmentando. Para finalizar la reducción correctamente, la etapa de "Reordenamiento" reagrupa los datos entre los nodos. Si no necesitamos este paso, todo el Map/Reduce consiste en mapear y reducir; ambas operaciones son paralelizables, la primera debido a su naturaleza elemento por elemento, la segunda debido a la asociatividad del monoide.

Un monoide completo es un monoide conmutativo equipado con una operación de suma infinitaria para cualquier conjunto de índices I tal que ^{[9] [10] [11] [12]}${\displaystyle \Sigma _{I}}$

${\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 ordenamiento parcial ≤ tal que a ≥ 0 para cada 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 un límite superior mínimo , y estos límites superiores mínimos son compatibles con la operación del 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 infinitaria es un monoide completo. ^[12]

• Monoide cartesiano
• Las relaciones de Green
• Mónada (programación funcional)
• Álgebra de Semiring y Kleene
• Problema de altura de las estrellas
• Plaza védica
• Frobenioide

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