Power Set with Union is Commutative Monoid

From ProofWiki
Jump to: navigation, search

Theorem

Let $S$ be a set and let $\powerset S$ be its power set.

Then $\struct {\powerset S, \cup}$ is a commutative monoid whose identity is $\O$.


The only invertible element of this structure is $\O$.

Thus (except in the degenerate case $S = \O$) $\struct {\powerset S, \cup}$ cannot be a group.


Proof

From Power Set is Closed under Union:

$\forall A, B \in \powerset S: A \cup B \in \powerset S$


From Set System Closed under Union is Commutative Semigroup, $\struct {\powerset S, \cup}$ is a commutative semigroup.


From Identity of Power Set with Union, $\O$ acts as the identity of $\struct {\powerset S, \cup}$.


It remains to be shown that only $\O$ has an inverse:

For $T \subseteq S$ to have an inverse under $\cup$, we require $T^{-1} \cup T = \O$.

From this it follows that $T = \O = T^{-1}$.


The result follows by definition of commutative monoid.

$\blacksquare$


Also see


Sources