What is the identity in the power set of $\Sigma^*$ as a monoid?

Question

Given an alphabet $\Sigma$, $P (\Sigma^*)$, the power set of $\Sigma^*$, is a monoid, with language concatenation as morphism.

1. What is the identity: the empty language, or the language consisting of only the empty string?

2. What is the difference between concatenating a language with the empty language and with the language consisting of only the empty string?

Thanks.

Answer 1

For languages $L_1$ and $L_2$, the concatenation of $L_1$ with $L_2$ is defined elmentwise as:

$$L_1L_2=\{s_1s_2\mid s_1\in L_1\land s_2\in L_2\}$$

(at least in every case that I have seen)

The concatenation of a language $L$ with the empty languae is thus:

$$L\emptyset = \{s_1s_2\mid s_1\in L\land s_2\in\emptyset\}$$

By definition, $x\notin\emptyset$ for all $x$, so $(s_1\in L)\land (s_2\in \emptyset) \equiv (s_1\in L)\land \bot \equiv \bot$. Hence $L\emptyset=\{s_1s_2\mid\bot\}=\emptyset$ for any language $L$.

It stands to reason that the identity element of $\mathcal{P}(\Sigma^*)$ would be $E=\{\varepsilon\}$, where $\varepsilon$ is the empty string. This follows from $LE=EL=L$ for all $L\in\mathcal{P}(\Sigma^*)$.

---

For a more "mathy" take, consider the following:

Claim: If $\mathcal{P}(\Sigma^*)$ with language concatenation is a monoid, then $E=\{\varepsilon\}$ is the identity element.

proof-sketch: By definition, if $M$ is a monoid, then $M$ contains a unique identity element $e$ satisfying $xe=ex=x$ for all $x\in M$. Observe that for all $s\in\Sigma$, $s\varepsilon=\varepsilon s=s$ where $\varepsilon$ is the empty string.

If $E=\{\varepsilon\}$ is the language containing the empty string, then for all $L\in\mathcal{P}(\Sigma^*)$...

$$LE=\{le\mid l\in L\land e\in E\}=\{l\varepsilon\mid l\in L\}=\{l\mid l\in L\}=L$$

...and...

$$EL=\{el\mid e\in E\land l\in L\}=\{\varepsilon l\mid l\in L\}=\{l\mid l\in L\}=L$$

Whence...

$$LE=EL=L$$

Thus, $E$ is the unique identity of the monoid $P(\Sigma^*)$. Q.E.D.

Answer 2

This is not a specific property of free monoids, it holds for any monoid. More precisely, take a monoid $M$ with identity $1$. Then ${\cal P}(M)$, the power set of $M$ is a monoid under the product defined, for each $S,T \in {\cal P}(M)$ by $$ ST = \{st \mid s \in S, t \in T\} $$ The identity of ${\cal P}(M)$ is the singleton $\{1\}$, since, according to the definition of the product $$ S\{1\} = \{st \mid s \in S, t \in \{1\} \} = \{s1 \mid s \in S\} = S $$ and $\{1\}S = S$ by a dual argument. The empty set is a zero of the monoid ${\cal P}(M)$. Indeed $$ S \emptyset = \{st \mid s \in S, t \in \emptyset\} = \emptyset $$ and $\emptyset S = \emptyset$ by a dual argument.