Subset Relation on Power Set is Partial Ordering

From ProofWiki
Jump to navigation Jump to search


Let $S$ be a set.

Let $\powerset S$ be the power set of $S$.

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

Then $\struct {\powerset S, \subseteq}$ is an ordered set.

The ordering $\subseteq$ is partial if and only if $S$ is neither empty nor a singleton; otherwise it is total.


From Subset Relation is Ordering, we have that $\subseteq$ is an ordering on any set of subsets of a given set.

Suppose $S$ is neither a singleton nor the empty set.

Then $\exists a, b \in S$ such that $a \ne b$.

Then $\set a \in \powerset S$ and $\set b \in \powerset S$.

However, $\set a \nsubseteq \set b$ and $\set b \nsubseteq \set a$.

So by definition, $\subseteq$ is a partial ordering.

Now suppose $S = \O$.

Then $\powerset S = \set \O$ and, by Empty Set is Subset of All Sets, $\O \subseteq \O$.

Hence, trivially, $\subseteq$ is a total ordering on $\powerset S$.

Now suppose $S$ is a singleton: let $S = \set a$.

Then $\powerset S = \set {\O, \set a}$.

So there are only two elements of $\powerset S$, and we see that $\O \subseteq \set a$ from Empty Set is Subset of All Sets.

So, trivially again, $\subseteq$ is a total ordering on $\powerset S$.