Power Set is Complete Lattice

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set.

Let $\struct {\powerset S, \subseteq}$ be the relational structure defined on $\powerset S$ by the relation $\subseteq$.

Then $\struct {\powerset S, \subseteq}$ is a complete lattice.


Proof

From Subset Relation on Power Set is Partial Ordering, we have that $\subseteq$ is a partial ordering.


We note in passing that for any set $S$:

From Supremum of Power Set, $\powerset S$ has a supremum, that is, $S$ itself
From Infimum of Power Set, $\powerset S$ has an infimum, that is, $\O$.

These are also the maximal and minimal elements of $\powerset S$.


Let $\mathbb S$ be a subset of $\powerset S$.

Then from Union is Smallest Superset:

$\paren {\forall X \in \mathbb S: X \subseteq T} \iff \bigcup \mathbb S \subseteq T$

and from Intersection is Largest Subset:

$\paren {\forall X \in \mathbb S: T \subseteq X} \iff T \subseteq \bigcap \mathbb S$

So $\bigcap \mathbb S$ is the infimum and $\bigcup \mathbb S$ is the supremum of $\struct {\mathbb S, \subseteq}$.

Hence by definition $\powerset S$ is a complete lattice.

$\blacksquare$


Also see


Sources