While looking at a proof of "Maximum Principle implies Well-Ordering Theorem" in this web-page


I came across a Lemma inside this proof which includes a statement in it's own proof that I've found quite problematic. The Lemma states that:

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

Define $\prec$ as: \begin{align*} \left({A,<}\right) \prec \left({A',<'}\right) \end{align*} if and only if \begin{align*} \left({A,<}\right) \textrm{ equals an initial segment of } \left({A',<'}\right) \end{align*} 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.

This is where I've a problem in this proof here:


"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,<_C}\right)$ from Equality is Transitive."

How can one make this bold assertion, when we don't know whether or not the well-ordered relation on $A$, $B$ and $C$ are same ? I ask this question because any initial segment of a well-ordered set $\left({A,<_A}\right)$ by an element of $A$ would depend upon the relation $<_A$.

If $\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)$, it means $\left({A,<_A}\right) = \left({S_x(B),<_B}\right), \textrm{ where } S_x(B) = \left\{ b \in B \textrm{ }|\textrm{ } b <_B x \right\}$ and $\left({B,<_B}\right) = \left({S_y(C),<_C}\right), \textrm{ where } S_y(C) = \left\{ c \in C \textrm{ }|\textrm{ } c <_C y \right\}$ respectively.

How can we conclude $S_x(B)$ is an initial segment of $\left({C,<_C}\right)$ when we don't have any relationship between the relations $<_B$ and $<_C$ ? That is, how can we show that $S_x(B) = \left\{ b \in B \textrm{ }|\textrm{ } b <_B x \right\} = S_z(C) = \left\{ c \in C \textrm{ }|\textrm{ } c <_C z \right\}$, for some $z \in S_y(C)$ ?


Being an initial segment means, amongst other things, that $A\subseteq B$ and $<_A=<_B\restriction A$.

For example $(\{0,1\},\{\langle 0,1\rangle\})$ is an initial segment of $\Bbb N$ with the standard order, whereas $(\{0,1\},\{\langle 1,0\rangle\})$ is not.

So yes, an initial segment of an initial segment, is an initial segment.

  • $\begingroup$ I'm sorry I cannot follow you. Are you saying that $<_A = <_B$ when A is treated as an initial segment of B ? $\endgroup$ – Minto P Jun 11 '20 at 19:50
  • $\begingroup$ I am saying that $<_A$ is $<_B\cap A\times A$. $\endgroup$ – Asaf Karagila Jun 11 '20 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.