Power Set with Intersection 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, \cap}$ is a commutative monoid whose identity is $S$.


The only invertible element of this structure is $S$.

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


Proof

From Power Set is Closed under Intersection:

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


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


From Identity of Power Set with Intersection, we have that $S$ acts as the identity.


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

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

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


The result follows by definition of commutative monoid.

$\blacksquare$


Also see


Sources