Condition for Power Set to be Totally Ordered

From ProofWiki
Jump to: navigation, search

Theorem

Let $\mathcal P \left({S}\right)$ be the power set of a set $S$.

Let $\left({\mathcal P \left({S}\right), \subseteq}\right)$ be the set $\mathcal P \left({S}\right)$ ordered by $\subseteq$.


Then $\left({\mathcal P \left({S}\right), \subseteq}\right)$ is totally ordered iff $S$ is either the empty set or a singleton.


Proof

From Subset Relation on Power Set is Partial Ordering we have that $\left({\mathcal P \left({S}\right), \subseteq}\right)$ is an ordered set.

We now need to show that $\left({\mathcal P \left({S}\right), \subseteq}\right)$ is a totally ordered set exactly when $S = \varnothing$ or $S$ has exactly one element.


When $S = \varnothing$ then $\mathcal P \left({S}\right) = \left\{{\varnothing}\right\}$ and it follows trivially that $\left({\mathcal P \left({S}\right), \subseteq}\right)$ is totally ordered.

$\Box$


Let $S = \left\{{x}\right\}$.

Then $\mathcal P \left({S}\right) = \left\{{\varnothing, \left\{{x}\right\}}\right\}$.

From Empty Set is Subset of All Sets we have $\varnothing \subseteq \left\{{x}\right\}$.

Again it follows by definition that $\left({\mathcal P \left({S}\right), \subseteq}\right)$ is totally ordered.

$\Box$


Now suppose $S$ is neither the empty set nor a singleton.

Then:

$\exists x, y \in S: x \ne y$

and so:

$\exists \left\{{x}\right\}, \left\{{y}\right\} \in \mathcal P \left({S}\right): \left\{{x}\right\} \ne \left\{{y}\right\}$

But further, $\left\{{x}\right\} \nsubseteq \left\{{y}\right\}$ and $\left\{{y}\right\} \nsubseteq \left\{{x}\right\}$.

That is, $\left\{{x}\right\}$ and $\left\{{y}\right\}$ are non-comparable by $\subseteq$.

Thus, by definition, $\left({\mathcal P \left({S}\right), \subseteq}\right)$ is not totally ordered.

Hence the result.

$\blacksquare$


Sources