Equality to Initial Segment Imposes Well-Ordering

From ProofWiki
Jump to navigation Jump to search

Lemma

Let $X$ be a set.

Let $\mathcal A$ be the set of all ordered pairs $\left({A,<}\right)$ such that $A$ is a subset of $X$ and $<$ is a strict well-ordering of $A$.

Define $\prec$ as:

$\left({A,<}\right) \prec \left({A',<'}\right)$

if and only if

$\left({A,<}\right)$ equals an initial segment of $\left({A',<'}\right)$.

Let $\mathcal B$ be a set of ordered pairs in $\mathcal A$ such that $\mathcal B$ is ordered by $\prec$.

Let $B'$ be the union of the sets $B$ for all $\left({B,<}\right) \in \mathcal B$.

Let $<'$ be the union of the relations $<$ for all $\left({B,<}\right)$.


Then $\left({B',<'}\right)$ is strictly well-ordered set.


Proof

If the set $X$ considered is empty or a singleton, the lemma holds vacuously or trivially.

Thus assume $X$ contains at least two elements.


We first prove that $\prec$ is a strict partial ordering on $\mathcal A$.

From the definition of initial segment, no $\left({A,<}\right)$ can equal an initial segment of itself.

Thus $\prec$ is antireflexive.

Suppose $\left({A,<_A}\right)$ equals an initial segment of $\left({B,<_B}\right)$ and $\left({B,<_B}\right)$ equals an initial segment of $\left({C,<_C}\right)$.

Then $\left({A,<_A}\right)$ equals an initial segment of $\left({C,<'}\right)$ from Equality is Transitive.

Thus $\prec$ is a strict partial order on $\mathcal A$.


We then prove that any $\left({B',<'}\right)$ is a strictly well-ordered set.

Let $x_1,x_2 \in B'$.

That is, let $x_i \in \left({A_i,<_i}\right)$ for $i = 1, 2$.

Suppose $x_2 \prec x_1$.

That is, $\left({A_2,<_2}\right)$ equals an initial segment in $\left({A_1,<_1}\right)$

By the definition of initial segment, both $x_1$ and $x_2$ are in $\left({A_1,<_1}\right)$.

Thus $<'$ is connected, as all $<_i$ are strict well-orderings by hypothesis.


For any $x_i \in \left({A_i,<_i}\right)$, $x_i \nprec x_i$ as all $<_i$ are strict well-orderings by hypothesis.

Thus $<'$ is antireflexive.


To show that $<'$ is transitive, consider $x_i \in \left({B',<'}\right)$ for $i = 1, 2, 3$.

Suppose $x_1 <' x_2 <' x_3$.

Then $x_1 <_1 x_2$ and $x_2 <_2 x_3$, from the definition of $<'$ as a union of relations $<_i$.

Then $\left({A_j,<_j}\right)$ is an initial segment of $\left({A_i,<_i}\right)$ for $j = 1, 2; j < i$

Thus $x_1 <_i x_2 <_i x_3$.

Then $x_1 <_i x_3$, as all $<_i$ as all $<_i$ are strict well-orderings by hypothesis.

Conclude that $<'$ is itself a strict ordering.


It remains to be shown that $<'$ is a well-ordering.

Let $A$ be an arbitrary non-empty subset of $B'$.

Let $x \in A$ and $x \in \left({B,<}\right)$ for $\left({B,<}\right) \in \mathcal B$.

Then for all $y \in A$, $y <' x$ if and only if $y < x$ and $y \in B$.

As $<$ is a well-ordering, $\left({B \cap A, <}\right)$ has a smallest element $b$.

This $b$ is then a smallest element of $<'$ in $A$.

Conclude that $<'$ is a strict well-ordering on $B'$.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Equality_to_Initial_Segment_Imposes_Well-Ordering&oldid=359717"