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

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.

• I thought that language concatenation is defined pointwise. Shouldn't $L\emptyset=\emptyset$, then? – R. Burton Jun 23 '20 at 23:52
• What is the definition of language concatenation? – Tim Jun 24 '20 at 0:08

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.

• Thanks. Could you find other references which also say that the concatenation of a language 𝐿 with the empty languae is empty? – Tim Jun 24 '20 at 2:09
• – R. Burton Jun 24 '20 at 2:39

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.

• Thanks. Given a monoid M, does the product of two subsets S and T of M belong to P(M)? Is the product the same or different from Cartesian product of two sets? I guess yes, and think that the Cartesian product of two subsets of M doesn't belong to P(M) but to P(M*M). – Tim Jun 24 '20 at 9:45
• Yes, $ST$ belongs to ${\cal P}(M)$ and $S \times T$ to ${\cal P}(M \times M)$. – J.-E. Pin Jun 24 '20 at 9:59