Well-Ordering Proof in Cunningham

Question

In Cunningham's Proof [1] of the Well-Ordering Principle (assuming $\textsf{AC}$), he begins by considering the set $\mathcal{W} = \{ \preceq | \preceq \text{a well-ordering on a subset of } A \}$ for some arbitrary set $A$. He then defines the "continuation" relation $\unlhd$ on $\mathcal{W}$ as follows:

$$ \text{For any } \preceq, \preceq^{'} \in \mathcal{W}, \\ \preceq \: \unlhd \: \preceq^{'} \Longleftrightarrow \text{(i)} \preceq \: \subseteq \: \preceq^{'} \text{and (ii) if } x \preceq^{'} y \text{ and } y \preceq y, \text{then } x \preceq y $$

where "$x$ and $y$ are arbitrary." Firstly, considering the fact that $\preceq \:$ is, by definition, a well-ordering on some subset of $A$, why is the reflexivity requirement ($y \preceq y$) needed? It was my understanding that this was already satisfied by virtue of well-orders being total orders (which, I think, require reflexivity).

More broadly, why is (ii) needed at all? I'm having a hard time finding an example of a superset to some relation $\preceq \: \in \mathcal{W}$ that doesn't satisfy this property. Could any of you offer a simple example of a superset that does not satisfy (ii)?

Apologies if I'm missing something obvious.

[1] $\textit{Set Theory: A First Course}$ by Daniel Cunningham (2016)

Answer 1

So elements of $W$ are well-orderings on subsets of $A$. To make this clearer, we can write $(B,\preceq)\in W,$ where $B\subset A$ and $\preceq$ is a well-ordering on $B$. We can rewrite the two conditions as $(B,\preceq)\trianglelefteq(B',\preceq')$ if

1. $B\subset B'$ and for any $a,b\in B,$ we have $a\preceq b\Longrightarrow a\preceq'b.$

2. If $a\preceq'b$ (which implies that $a,b\in B'$) and $b\in B,$ then $a\in B$ and $a\preceq b$.

As Andreas said, writing $y\preceq y$ implies that $y\in B$ (because this is the set on which $\preceq$ is defined). Since $\preceq$ is a well-order and thus reflexive, we have $y\preceq y\Longleftrightarrow y\in B.$

Let's do an example. Let $A=\{a,b\}$. Then there are five well-ordered subsets of $A$: $$\emptyset,\quad\{a\},\quad\{b\},\quad\{a<b\},\quad \{b<a\}.$$ Now you can check that $\{a\}\trianglelefteq\{a<b\}$. However $\{a\}\not\trianglelefteq\{b< a\}.$ The well-ordered set $\{b<a\}$ clearly extends the singleton $\{a\}$, so they satisfy (1). But it doesn't satisfy (2), because $b<a$ but $b\notin \{a\}$ (in the language of condition 2, this is $b\preceq' a$ and $a\in B$, but $b\notin B$).

If $B'$ is any well-ordered set and $B\subset B'$ is a well-ordered subset satisfying the above two conditions, we often say that $B$ is an initial segment of $B'$. Check that this is equivalent to the following: $$\text{Either }B=B'\text{ or there is some }b\in B'\text{ with }B=\{a\in B':a<b\}.$$ This is important in the proof of the well-ordering theorem. Suppose that $\mathscr C\subset W$ is a totally-ordered subset under $\trianglelefteq$. Condition (1) ensures that $\bigcup_{B\in\mathscr C}\!B$ has a total ordering extending that of any $B\in \mathscr C$. But the union might not be well-ordered. For example, every set $\{1/n,\dots,1/3,1/2,1\}$ is well-ordered, but the union $\{1/n:n\text{ a positive integer}\}$ is not well-ordered. Condition (2) is designed to ensure that the union is well-ordered.

In general, the concept of "initial segment" makes the ordinal numbers well-ordered (modulo some detail about proper classes). Specifically, if $A,B$ are well-ordered sets, we have one of the following:

3. There is a unique order-preserving injection $f:A\rightarrow B$ such that $f(A)\trianglelefteq B.$
4. There is a unique order-preserving injection $f:B\rightarrow A$ such that $f(B)\trianglelefteq A.$

If both (3) and (4) are true, then there is a unique order-preserving bijection $f:A\rightarrow B$.

Answer 2

Thanks to reflexivity, $y\preceq y$ is just saying that $y$ is in the subset of $A$ that $\preceq$ well-orders.