Ordering Equivalent to a Subset Relation

Theorem

Let $\left({S, \preceq}\right)$ be a poset.

Then there exists a set $\mathbb S$ of subsets of $S$ such that:

$\left({S, \preceq}\right) \cong \left({\mathbb S, \subseteq}\right)$

where:

• $\left({\mathbb S, \subseteq}\right)$ is the relational structure consisting of $\mathbb S$ and the subset relation
• $\cong$ denotes order isomorphism.

Hence the subset relation is, up to order isomorphism, the only ordering there is on a given set of subsets.

Proof

From Subset Relation is Ordering, we have that $\left({\mathbb S, \subseteq}\right)$ is a poset.

For each $a \in S$, let $S_a$ be the weak initial segment of $a$. That is:

$S_a := \left\{{b \in S: b \preceq a}\right\}$

Then let $T$ be defined as:

$T := \left\{{S_a: a \in S}\right\}$

Let the mapping $\phi: S \to T$ be defined as:

$\phi \left({a}\right) = S_a$

We are to show that $\phi$ is an order isomorphism.

$\phi$ is clearly surjective, as every $S_a$ is defined from some $a \in S$.

Now suppose $S_x, S_y \in T: S_x = S_y$.

Then:

$\left({b \in S: b \preceq x}\right\} = \left({b \in S: b \preceq y}\right\}$

We have that $x \in S_x = S_y$ and $y \in S_y = S_x$ which means $x \preceq y$ and $y \preceq x$.

So as an ordering is antisymmetric, we have $x = y$ and so $\phi$ is injective.

Hence by definition, $\phi$ is a bijection.

Now let $a_1 \preceq a_2$. Then by definition, $a_1 \in S_{a_2}$.

Let $a_3 \in S_{a_1}$.

Then by definition, $a_3 \preceq a_1$.

As an ordering is transitive, it follows that $a_3 \preceq a_2$ and so $a_3 \in S_{a_2}$.

So by definition of a subset, $S_{a_1} \subseteq S_{a_2}$.

Thus it follows that $\phi$ is an order isomorphism between $\left({S, \preceq}\right)$ and $\left({\mathbb S, \subseteq}\right)$.

$\blacksquare$

Sources

• Keith Devlin: The Joy of Sets: Fundamentals of Contemporary Set Theory (1993): $\S 1.5$: Theorem $1.5.2$