Monóide

Na álgebra abstrata , um monóide é uma estrutura algébrica que consiste em um conjunto com uma ligação associativa e um elemento neutro . Um exemplo são os números naturais com adição e o número 0 como elemento neutro. Um monóide em que cada elemento pode ser invertido é chamado de grupo .

definição

Um monóide é um triplo que consiste em um conjunto , um link interno de dois dígitos ${\ displaystyle \ left (M, *, e \ right)}$ ${\ displaystyle M}$

{\ displaystyle * \ dois pontos M \ times M \ a M, \ quad (a, b) \ mapsto a * b}

e um excelente elemento com as seguintes propriedades em relação à ligação especificada: ${\ displaystyle e \ in M}$

Associatividade do link:
${\ displaystyle \ forall a, b, c \ in M \ dois pontos (a * b) * c = a * (b * c)}$
${\ displaystyle e}$ é um elemento neutro :
${\ displaystyle \ forall a \ in M \ dois pontos e * a = a * e = a}$

Um monóide é um semigrupo com um elemento neutro. Cada grupo é um monóide, mas ao contrário do grupo, um monóide não tem necessariamente elementos inversos.

Notas na notação

A associatividade (parte 1 da definição) justifica a omissão de colchetes: Para o operador binário , o termo é inicialmente ambíguo. No entanto, como o resultado é invariável em relação à sequência de avaliação especificada entre parênteses, os parênteses podem ser omitidos aqui. ${\ displaystyle *}$ ${\ displaystyle a * b * c}$

Em um monóide, o elemento neutro é claramente definido. Se ficar claro a partir do contexto qual é o elemento neutro, um monóide também é frequentemente escrito na forma abreviada como um par . No entanto, isso não corresponde à forma normal para álgebras (heterogêneas e) universais , uma vez que o axioma para o elemento neutro requer então um quantificador existencial - a ser evitado . ${\ displaystyle \ left (M, * \ right)}$

O símbolo é freqüentemente usado para o link ; então, fala-se de um monóide escrito multiplicativamente. O elemento neutro é então chamado de elemento de unidade e é simbolizado por. Como é normal na multiplicação normal , o ponto de pintura pode ser omitido em muitas situações. ${\ displaystyle *}$ ${\ displaystyle \ cdot}$ ${\ displaystyle 1}$

Um monóide também pode ser notado aditivamente usando o símbolo para o link . O elemento neutro é então chamado de elemento zero e é simbolizado por. Monóides escritos aditivamente são geralmente comutativos. ${\ displaystyle *}$ ${\ displaystyle +}$ ${\ displaystyle 0}$

Exemplos e contra-exemplos

${\ displaystyle \ left (\ mathbb {N} _ {0}, +, 0 \ right)}$	é um monóide.
${\ displaystyle (\ mathbb {N}, \ cdot, 1)}$	é um monóide. Este é um meio anel (avaliação) . ${\ displaystyle (\ mathbb {N} _ {0}, +, 0, \ cdot, 1)}$
${\ displaystyle (\ mathbb {N}, \ div, 1)}$	não é um monóide porque a divisão não é fechada e a divisão não é associativa. ${\ displaystyle \ mathbb {N}}$
${\ displaystyle (\ mathbb {Z}, +, 0)}$	(o conjunto de números inteiros com adição) é um monóide.
${\ displaystyle (\ mathbb {Z}, -, 0)}$	não é um monóide porque a subtração não é associativa.
${\ displaystyle \ left (\ mathbb {R} ^ {n \ times n}, \ cdot, E \ right)}$	(o conjunto de matrizes n × n com a multiplicação usual da matriz e a matriz unitária E ) é um monóide não comutativo .
${\ displaystyle \ left (\ mathbb {R} ^ {3}, \ times, {\ vec {0}} \ right)}$	(o espaço real tridimensional com o produto vetorial ) não é um monóide, uma vez que a lei associativa é violada: vamos denotar com o i- ésimo vetor unitário , então é , mas . ${\ displaystyle e_ {i}}$ ${\ displaystyle (e_ {1} \ times e_ {1}) \ times e_ {2} = 0}$ ${\ displaystyle e_ {1} \ times (e_ {1} \ times e_ {2}) = - e_ {2}}$
${\ displaystyle (n \ mathbb {Z}, +, 0)}$	(o conjunto de múltiplos do inteiro n com adição) é um monóide (até mesmo um grupo ).
${\ displaystyle \ left (\ mathbb {Q} _ {+}, +, 0 \ right)}$	(o conjunto de números racionais não negativos com adição) é um monóide.
${\ displaystyle (\ mathbb {Q} _ {+} ^ {*}, \ cdot, 1)}$	(o conjunto de números racionais positivos com multiplicação) é um monóide. Portanto, há um meio anel (mesmo meio corpo ). ${\ displaystyle (\ mathbb {Q} _ {+}, +, 0, \ cdot, 1)}$
${\ displaystyle \ left ({\ mathcal {P}} (X), \ cap, X \ right)}$	(o conjunto de potência de um conjunto X com o operador de interseção) é um monóide comutativo.
${\ displaystyle (\ Sigma ^ {*}, \ cdot, \ varepsilon)}$	as palavras acima do alfabeto formam a chamada palavra monóide com a concatenação e a palavra vazia . ${\ displaystyle \ Sigma}$ ${\ displaystyle \ cdot}$ ${\ displaystyle \ varepsilon}$
${\ displaystyle (\ operatorname {End} _ {\ mathtt {C}} (A), \ circ, \ operatorname {id} _ {A})}$	os endomorfismos de um objeto em qualquer categoria , d. H. os morfismos . Cada monóide pode ser entendido como uma categoria com exatamente um (qualquer) objeto. ${\ displaystyle A}$ ${\ displaystyle {\ mathtt {C}}}$ ${\ displaystyle A {\ underset {\ mathtt {C}} {\ longrightarrow}} A}$

Sub-monóide

Um subconjunto de um monóide que o elemento neutro que contém e relativa à ligação de é terminado (i. E., Por tudo está bem ) é submonoid de . ${\ displaystyle U \ subseteq M}$ ${\ displaystyle (M, *, e)}$ ${\ displaystyle e}$ ${\ displaystyle *}$ ${\ displaystyle M}$ ${\ displaystyle u, v \ in U}$ ${\ displaystyle u * v \ in U}$ ${\ displaystyle M}$

Homomorfismo monóide

Um homomorfismo monóide é definido como um mapeamento entre dois monóides , para os quais vale: ${\ displaystyle f \ dois pontos A \ a B}$ ${\ displaystyle \ left (A, * _ {A}, e_ {A} \ right)}$ ${\ displaystyle \ left (B, * _ {B}, e_ {B} \ right)}$

${\ displaystyle \ forall x, y \ in A \ colon f (x * _ {A} y) = f (x) * _ {B} f (y)}$ ,
${\ displaystyle f \ left (e_ {A} \ right) = e_ {B}}$ .

Este é um mapeamento compatível com os links em e e mapeia o elemento neutro de para o elemento neutro de . Em termos de álgebra abstrata, um homomorfismo monóide é um homomorfismo entre monóides. ${\ displaystyle A}$ ${\ displaystyle B}$ ${\ displaystyle A}$ ${\ displaystyle B}$

A imagem de um homomorfismo monóide é um submonóide dos monoides alvo . ${\ displaystyle f \ left (A \ right)}$ ${\ displaystyle f \ dois pontos A \ a B}$ ${\ displaystyle B}$

Se o homomorfismo monóide for bijetivo , então é denominado isomorfismo monóide e os monoides e isomórfico. ${\ displaystyle f \ dois pontos A \ a B}$ ${\ displaystyle A}$ ${\ displaystyle B}$

Monóide grátis

Um monóide é chamado de livre se houver um subconjunto de modo que cada elemento possa ser representado exclusivamente como um produto finito de elementos . é então chamada de base (produtora) do monóide. ${\ displaystyle (M, *, e)}$ ${\ displaystyle A \ subset M}$ ${\ displaystyle M}$ ${\ displaystyle A}$ ${\ displaystyle A}$

Se for qualquer quantidade, então a quantidade forma de todas as sequências finitas na concatenação, escrevendo as sequências como combinação multiplicativa e a sequência vazia como um elemento neutro , o monóide . Este monóide é denominado monóide livre gerado por . Se o conjunto for finito, geralmente se fala do alfabeto e de palavras ou palavras acima desse alfabeto; obtém-se a já mencionada palavra monóide. ${\ displaystyle A}$ ${\ displaystyle A ^ {*}}$ ${\ displaystyle A}$ ${\ displaystyle \ cdot}$ ${\ displaystyle \ varepsilon}$ ${\ displaystyle (A ^ {*}, \ cdot, \ varepsilon)}$ ${\ displaystyle A}$ ${\ displaystyle A}$ ${\ displaystyle A}$

O monóide livre sobre um conjunto desempenha um papel em muitas áreas da ciência da computação teórica (por exemplo, linguagem formal , expressão regular , teoria dos autômatos ). Consulte também o artigo sobre o shell Kleenesche para um termo relacionado. ${\ displaystyle A ^ {*}}$ ${\ displaystyle A}$

O monoid livre sobre cumpre a seguinte propriedade universal : Se um monoid e qualquer função, então não é exatamente um Monoid- homomorphism com para todos . Esses homomorfismos são usados na ciência da computação teórica para definir linguagens formais (como subconjuntos de ). ${\ displaystyle A ^ {*}}$ ${\ displaystyle A}$ ${\ displaystyle M}$ ${\ displaystyle f \ dois pontos A \ a M}$ ${\ displaystyle T \ dois pontos A ^ {*} \ a M}$ ${\ displaystyle T (a) = f \ left (a \ right)}$ ${\ displaystyle a \ in A}$ ${\ displaystyle A ^ {*}}$

Se um monóide tem um subconjunto , de modo que cada elemento pode ser representado como um produto de elementos de forma inequívoca até a ordem dos fatores , então chama-se livremente comutativo com o produtor . Esse monóide é necessariamente comutativo. neste caso, é o conjunto de multisets que contém os elementos de . Um monóide livre com pelo menos um gerador de dois elementos não é comutativo. ${\ displaystyle (M, *, e)}$ ${\ displaystyle A}$ ${\ displaystyle M}$ ${\ displaystyle A}$ ${\ displaystyle M}$ ${\ displaystyle A}$ ${\ displaystyle M}$ ${\ displaystyle A}$

O monóide livre, como o grupo livre, é um exemplo de objeto livre na teoria das categorias .

Exemplos

O monóide é livre e livremente comutativo com o produtor . ${\ displaystyle (\ mathbb {N} _ {0}, +, 0)}$ ${\ displaystyle \ {1 \}}$
Para um conjunto , o conjunto de todos os mapeamentos de inteiros não negativos, que só têm um valor diferente de 0 em muitos lugares finitos, é um monóide comutativo com a adição de componentes. É livremente comutativo com as funções elementares de geradores (existe um delta de Kronecker ). ${\ displaystyle A}$ ${\ displaystyle \ operatorname {Abb_ {fin}} (A, \ mathbb {N} _ {0})}$ ${\ displaystyle A}$ ${\ displaystyle \ chi _ {a} (x) = \ delta _ {a, x}}$ ${\ displaystyle \ delta _ {a, x}}$
O monóide nulo é livre assim como comutativo livre com o conjunto vazio como produtor. ${\ displaystyle (\ {0 \}, +, 0)}$
O monóide é livremente comutativo em relação ao conjunto de números primos , mas não é um monóide livre. ${\ displaystyle (\ mathbb {N}, \ cdot, 1)}$
O envelope de Kleen é o monóide gerado livremente pelo alfabeto em relação à concatenação . ${\ displaystyle \ Sigma ^ {*}}$ ${\ displaystyle \ Sigma}$