Proving that the set of languages over an alphabet Σ is a monoid regarding concatenation

Question

I'm practicing proofs and would like to prove that the set of languages over an alphabet $\Sigma$ is a monoid regarding concatenation by showing that the following statements are true:

1. There is a neutral element $E$, so that for all languages $A$ over $\Sigma$: $$A\circ{}E=E\circ{}A=A$$
2. The concatenation is associative.
3. The monoid is generally not commutative.

This is my suggested solution:

1. Let $\epsilon$ be the empty string, $E=\lbrace{\epsilon}\rbrace$ and $A=\lbrace{u}\rbrace$ a language over $\Sigma$ with $u\in{}\Sigma^{*}$, so:

$$A\circ{}E=\lbrace{u}\rbrace\circ\lbrace{\epsilon}\rbrace=\lbrace{u}\rbrace=A=\lbrace{u}\rbrace=\lbrace{\epsilon}\rbrace\circ{}A=E\circ{}A$$

$\Rightarrow\epsilon$ is the neutral element.

2. Let $A=\lbrace{u}\rbrace$, $B=\lbrace{v}\rbrace$, $C=\lbrace{w}\rbrace$ be languages over $\Sigma$ with $u,v,w\in{}\Sigma^{*}$, so:

$$(A\circ{}B)\circ{}C=(\lbrace{u}\rbrace\circ\lbrace{v}\rbrace)\circ\lbrace{w}\rbrace=\lbrace{uv}\rbrace\circ\lbrace{w}\rbrace=\lbrace{uvw}\rbrace=\lbrace{u}\rbrace\circ\lbrace{vw}\rbrace=\lbrace{u}\rbrace\circ(\lbrace{v}\rbrace\circ\lbrace{w}\rbrace)=A\circ{}(B\circ{}C)$$

$\Rightarrow$ The concatenation is associative and $(\Sigma^{*},\circ,\epsilon)$ is a monoid.

3. Let $A=\lbrace{u}\rbrace$, $B=\lbrace{v}\rbrace$ be languages over $\Sigma$ with $u,v\in{}\Sigma^{*}$, so:

$$A\circ{}B=\lbrace{u}\rbrace\circ\lbrace{v}\rbrace=\lbrace{uv}\rbrace\neq\lbrace{vu}\rbrace=\lbrace{v}\rbrace\circ\lbrace{u}\rbrace=B\circ{}A$$

$\Rightarrow$ The concatenation is not commutative.

Is that a correct way to prove these three statements? If not, what would be the correct way?

Answer 1

It seems that everything works.

Just a remark: for non commutativity, you need your alphabet to have at least two different letters. Indeed, if $\Sigma = \{ a\}$ then you get a monoid isomorphic to $(\Bbb{N} , +)$ which is commutative.

Answer 2

Your proof is uncomplete. You need to prove the results for all languages, not only for languages reduced to a single word. For instance, $\{1\}$ is indeed the neutral element, but you need to prove that $\{1\}L = L\{1\} = L$ for each language $L$. You can write $$ \{1\}L = \{1u \mid u \in L\} = \{u \mid u\in L\} = L =\{u1 \mid u \in L \} = \{1\}L $$ and you have to use a similar argument for associativity.

To prove non commutativity, you have to give an explicit counterexample, for instance $\{a\}\{ab\} \not= \{ab\}\{a\}$. Indeed, if you take arbitrary words $u$ and $v$, it may happen that $uv = vu$ (this is actually the case if and only if $u$ and $v$ are powers of the same word, that is $u = w^n$ and $v = w^m$ for some word $w$).