Subset Relation on Power Set is Partial Ordering

From ProofWiki
Jump to navigation Jump to search

Theorem

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.


Proof

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$.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Subset_Relation_on_Power_Set_is_Partial_Ordering&oldid=654039"