Power Set is Complete Lattice

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set.

Let $\left({\mathcal P \left({S}\right), \subseteq}\right)$ be the relational structure defined on $\mathcal P \left({S}\right)$ by the relation $\subseteq$.

Then $\left({\mathcal P \left({S}\right), \subseteq}\right)$ 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, $\mathcal P \left({S}\right)$ has a supremum, that is, $S$ itself
From Infimum of Power Set, $\mathcal P \left({S}\right)$ has an infimum, that is, $\varnothing$.

These are also the maximal and minimal elements of $\mathcal P \left({S}\right)$.


Let $\mathbb S$ be a subset of $\mathcal P \left({S}\right)$.

Then from Union is Smallest Superset:

$\left({\forall X \in \mathbb S: X \subseteq T}\right) \iff \bigcup \mathbb S \subseteq T$

and from Intersection is Largest Subset:

$\left({\forall X \in \mathbb S: T \subseteq X}\right) \iff T \subseteq \bigcap \mathbb S$

So $\bigcap \mathbb S$ is the infimum and $\bigcup \mathbb S$ is the supremum of $\left({\mathbb S, \subseteq}\right)$.

Hence by definition $\mathcal P \left({S}\right)$ is a complete lattice.

$\blacksquare$


Also see


Sources