User:Jshflynn/P-star forms Additive Rig with Unity

Theorem

Let $\Sigma$ be an alphabet.

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

Then $(\mathcal{P}(\Sigma^{*}), \cup, \circ_L)$ is an additive rig with unity.

That is to say it satisfies all three of these conditions:

(1) $(\mathcal{P}(\Sigma^{*}), \cup)$ is a commutative monoid.

(2) $\circ_L$ is distributive over $\cup$.

(3) $(\mathcal{P}(\Sigma^{*}), \circ_L)$ is a monoid.

Proof

Condition (1)

Follows directly from P-star is Commutative Monoid under Union.

Condition (2)

Follows directly from Language Product Distributes over Union.

Condition (3)

Follows directly from P-star is Monoid under Language Product.

Hence the result.

$\blacksquare$