Union of Nest of Orderings is Ordering
Contents
Theorem
Let $S$ be a set.
Let $C$ be a nonempty nest of orderings on $S$.
Then $\bigcup C$ is an ordering on $S$.
Proof
Let $\preceq$ be an arbitrary element of $C$.
Let $\sim \, = \, \bigcup C$.
Checking in turn each of the criteria for an ordering:
Let $a, b \in S$.
Let $a \sim b$ and $b \sim a$.
Since $a \sim b$ and $b \sim a$, there exist $\preceq_1, \preceq_2 \, \in \, C$ such that $a \preceq_1 b$ and $b \preceq_2 a$.
Since $C$ is a chain:
- $\preceq_1 \, \subset \, \preceq_2$
or:
- $\preceq_2 \, \subset \, \preceq_1$
Without loss of generality, suppose $\preceq_1 \, \subset \, \preceq_2$.
Then it must hold that $a \preceq_2 b$.
Since:
- $a \preceq_2 b$
- $b \preceq_2 a$
- $\preceq_2 \, \in \, T$ is an ordering
it follows that:
- $a = b$
and so $\sim$ is antisymmetric.
$\Box$
Reflexivity
Let $a \in S$.
Because $\preceq$ is an ordering:
- $a \preceq a$
As $\preceq \, \subseteq \, \sim$:
- $a \sim a$
and so $\sim$ is reflexive.
$\Box$
Transitivity
Let $a, b, c \in S$.
Let $a \sim b$ and $b \sim c$.
Thus there are elements $\preceq_1$ and $\preceq_2$ of $C$ such that:
- $a \preceq_1 b$ and $b \preceq_2 c$
Since $C$ is a chain, it must hold (as above) that:
- $a \preceq_2 b$ or $b \preceq_1 c$
Without loss of generality, suppose $a \preceq_2 b$
Since:
- $a \preceq_2 b$
- $b \preceq_2 c$
- $\preceq_2 \, \in \, T$ is an ordering
it follows that:
- $a \preceq_2 c$
Since $\preceq_2 \, \subseteq \, \sim$:
- $a \sim c$
So $\sim$ has been shown to be transitive.
$\Box$
$\sim$ has been shown to be reflexive, transitive and antisymmetric.
Hence by definition it is an ordering.
$\blacksquare$