¿El conjunto de todas las cadenas de letras forma un grupo?

Question

Esto está relacionado con un curso que estoy haciendo de teoría de la informática.

Dejemos que $\sum$ sea un alfabeto. Entonces el conjunto de todas las cadenas sobre $\sum$ , denotado como $\sum^*$ tiene la operación de concatenación (unir dos cadenas de texto de extremo a extremo). Es evidente que la concatenación es asociativa, $\sum^*$ es cerrado bajo concatenación, y el elemento de identidad es la cadena vacía. También estoy tomando un curso de álgebra moderna, así que naturalmente pregunto puede $\sum^*$ ¿se formará un grupo? Se cumplen tres de los cuatro axiomas de grupo.

Answer 1

No es un grupo, es un monoide que es esencialmente un grupo sin inversos. Lo natural si se quiere un grupo es permitir arbitrariamente los inversos. Así que se considerarían las cadenas cuyas letras son de la forma $a$ o $a^{-1}$ donde $a \in \Sigma$ . Se dice que dos cadenas son equivalentes si se puede pasar de una a otra añadiendo o eliminando pares de la forma $aa^{-1}$ o $a^{-1}a$ . Entonces el conjunto de clases de equivalencia de cadenas es un grupo bajo concatenación.

Esta construcción se denomina grupo libre sobre $\Sigma$ .

Answer 2

No, $\Sigma^*$ no es un grupo (a menos que $\Sigma = \emptyset $ , en cuyo caso $\Sigma ^*$ es un grupo trivial con un elemento). La razón es que el único elemento que tiene un inverso es la palabra vacía. Por lo tanto, si $a\in \Sigma$ entonces $a$ como elemento de $\Sigma ^*$ no tiene inversa (en rigor, nótese que la longitud de las palabras nunca disminuye al concatenarlas).

Qué $\Sigma ^*$ es un ejemplo de monoide. Un monoide es una estructura algebraica que satisface todos los axiomas de un grupo excepto el requisito de las identidades. De hecho, $\Sigma ^*$ es el monoide libre en el conjunto $\Sigma$ . También existe la noción obvia de un monoide conmutativo, y un cierto cociente de $\Sigma^*$ que se obtiene permitiendo la conmutación de elementos, da lugar al monoide libre conmutativo $\Sigma ^+$ .