User:Jshflynn/Null Language is Identity of Language Product

Theorem

Let $\Sigma$ be an alphabet.

Let $\mathcal{P}(\Sigma^{*})$ be the $P$-star of $\Sigma$, $\circ$ denote concatenation and $\circ_L$ denote the language product operation.

Then the null language $\{\lambda\}$ is a two-sided identity of $\mathcal{P}(\Sigma^{*})$ under $\circ_L$.

Proof

Let $V$ be a formal language over $\Sigma$ (i.e. an element of $\mathcal{P}(\Sigma^{*})$).

We will show $\{\lambda\}\circ_L V = V$.

Let $x \in V$.

Then $\lambda \circ x \in \{\lambda\}\circ_L V$

Then from Empty Word is Two-sided Identity:

$x \in \{\lambda\}\circ_L V$

Hence $V \subseteq \{\lambda\}\circ_L V$

Now let $x \in \{\lambda\}\circ_L V$

By the definition of language product, there exists some $y$ in $V$ such that:

$x= \lambda \circ y$ and $\lambda \circ y \in \{\lambda\}\circ_L V$

From Empty Word is Two-sided Identity, $\lambda \circ y = y$ and $y = x$

Hence $x \in \{\lambda\}\circ_L V \implies x \in V$ and so $\{\lambda\}\circ_L V \subseteq V$

By the definition of set equality then:

$\{\lambda\}\circ_L V = V$.

So $\{\lambda\}$ is a left identity.

The proof that $\{\lambda\}$ is a right identity follows similarly.

$\blacksquare$