Subset Relation is 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 $\mathbb S \subseteq \powerset S$ be any subset of $\powerset S$, that is, an arbitrary set of subsets of $S$.

Then $\subseteq$ is an ordering on $\mathbb S$.


In other words, let $\struct {\mathbb S, \subseteq}$ be the relational structure defined on $\mathbb S$ by the relation $\subseteq$.

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


General Result

Let $\mathbb S$ be a set of sets or class.


Then $\subseteq$ is an ordering on $\mathbb S$.


In other words, let $\struct {\mathbb S, \subseteq}$ be the relational structure defined on $\mathbb S$ by the relation $\subseteq$.

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


Proof

To establish that $\subseteq$ is an ordering, we need to show that it is reflexive, antisymmetric and transitive.

So, checking in turn each of the criteria for an ordering:


Reflexivity

\(\ds \forall T \in \mathbb S: \, \) \(\ds T\) \(\subseteq\) \(\ds T\) Set is Subset of Itself

So $\subseteq$ is reflexive.

$\Box$


Antisymmetry

\(\ds \forall S_1, S_2 \in \mathbb S: \, \) \(\ds S_1 \subseteq S_2 \land S_2 \subseteq S_1\) \(\iff\) \(\ds S_1 = S_2\) Definition 2 of Set Equality

So $\subseteq$ is antisymmetric.

$\Box$


Transitivity

\(\ds \forall S_1, S_2, S_3 \in \mathbb S: \, \) \(\ds S_1 \subseteq S_2 \land S_2 \subseteq S_3\) \(\implies\) \(\ds S_1 \subseteq S_3\) Subset Relation is Transitive

That is, $\subseteq$ is transitive.

$\Box$


So we have shown that $\subseteq$ is an ordering on $\mathbb S$.

$\blacksquare$


Sources