# There is a well ordering of the class of all finite sequences of ordinals

I am trying to solve this exercise from Jech's book on set theory:

Ex. 3.6: There is a well ordering of the class of all finite sequences of ordinals such that for each $$\alpha$$, the set of all finite sequences in $$\omega_{\alpha}$$ is an initial segment and its order-type is $$\omega_{\alpha}$$.

Definition: If $$W$$ is a well ordered set and $$u \in W$$, then the set $$\{ x \in W \mid x < u \}$$ is an initial segment in W

Any help?

For $f,g\in\operatorname{Ord}^{<\omega}$ define $n_{f,g}$ to be the value $\min\{n\mid f(n)\neq g(n)\}$ (if $f\neq g$). Now you can define $f<g$ to mean this: \begin{align*} &\max\operatorname{ran}(f) < \max\operatorname{ran}(g)\\ \lor&(\max\operatorname{ran}(f) = \max\operatorname{ran}(g) \land \operatorname{dom}(f) < \operatorname{dom}(g))\\ \lor&(\max\operatorname{ran}(f) = \max\operatorname{ran}(g) \land \operatorname{dom}(f) = \operatorname{dom}(g) \land f(n_{f,g}) < g(n_{f,g})) \end{align*} This is the well-ordering you're looking for. Now prove that it does what it's supposed to do!

Hint: Let $A_g$ be the initial segment $\{ f \in \operatorname{Ord}^{<\omega} \mid f < g \}$. It is easy to see that for every $\alpha$ the set $A_{\{(0,\alpha)\}}$ is equal to $\alpha^{<\omega}$; specifically - replacing $\alpha$ with $\omega_\alpha$ -, each $\omega_\alpha^{<\omega}$ is an initial segment in $<$.

Because of $|\omega_\alpha|\leq|\omega_\alpha^{<\omega}|$, the order type of $\omega_\alpha^{<\omega}$ can't be smaller than $\omega_\alpha$. Now suppose there's a smallest $\alpha$ such that the order type of $\omega_\alpha^{<\omega}$ is strictly greater than $\omega_\alpha$ and show that this leads to a contradiction.

• I am thinking of transfinite induction on $\alpha$. Is the following ok for the basis of the onduction? Let $\alpha = 0$. Let $g: \omega^{< \omega} \rightarrow \omega$ be an isomorphism. Then, $\{ f(u) \in \omega | u \in \omega^{< \omega} \}$ is the required initial segment. – A student Sep 17 '14 at 10:52
• I don't understand the question. What's the role of $g$? Where does $\alpha$ appear in all of this? Why is your initial segment not a set of finite sequences of ordinals? This all seems rather confused. (And have you already convinced yourself that my $<$ is indeed a well-ordering to begin with?) – Frunobulax Sep 17 '14 at 10:58
• I am trying to "create" an initial segment inside $\omega$. I know that $|\omega^{< \omega}| = |\omega|$. I know that if two well-ordered sets has the same cardinality then there is an order-preserving function $g$ which is one-to-one and onto. If this is not the right basis for the induction, then, how should this basis be written? – A student Sep 17 '14 at 11:18
• See the hint I added above. – Frunobulax Sep 17 '14 at 11:30
• I have started writing the proof here below. At the bottom, I pointed out something in your clue that is not clear to me. Could you clarify that for me? Thank you. – A student Sep 17 '14 at 12:16

We will show first that $<$ is a well order:

1. antysimetry: Let $f<g$. Then, \begin{align*} &\max\operatorname{ran}(f) < \max\operatorname{ran}(g)\\ \lor&(\max\operatorname{ran}(f) = \max\operatorname{ran}(g) \land \operatorname{dom}(f) < \operatorname{dom}(g))\\ \lor&(\max\operatorname{ran}(f) = \max\operatorname{ran}(g) \land \operatorname{dom}(f) = \operatorname{dom}(g) \land f(n_{f,g}) < g(n_{f,g})) \end{align*}

Suppose now that $g < f$. Then, $\max\operatorname{ran}(g) < \max\operatorname{ran}(f)$ will contradict lines 1,2,3 in the definition of $'<'$. $(\max\operatorname{ran}(g) = \max\operatorname{ran}(f) \land \operatorname{dom}(g) < \operatorname{dom}(f))$ will contradict lines 1,2,3 in the definition, and also $(\max\operatorname{ran}(g) = \max\operatorname{ran}(f) \land \operatorname{dom}(g) = \operatorname{dom}(f) \land f(n_{f,g}) < g(n_{f,g}))$ will contradict lines 1,2,3 in the definition. So, we cannot have $g<f$.

1. Transitivity: Suppose that $f<g$ and $g<h$. Then, we have, \begin{align*} &\max\operatorname{ran}(f) < \max\operatorname{ran}(g)\\ \lor&(\max\operatorname{ran}(f) = \max\operatorname{ran}(g) \land \operatorname{dom}(f) < \operatorname{dom}(g))\\ \lor&(\max\operatorname{ran}(f) = \max\operatorname{ran}(g) \land \operatorname{dom}(f) = \operatorname{dom}(g) \land f(n_{f,g}) < g(n_{f,g})) \end{align*}

and also

\begin{align*} &\max\operatorname{ran}(g) < \max\operatorname{ran}(h)\\ \lor&(\max\operatorname{ran}(g) = \max\operatorname{ran}(h) \land \operatorname{dom}(g) < \operatorname{dom}(h))\\ \lor&(\max\operatorname{ran}(g) = \max\operatorname{ran}(h) \land \operatorname{dom}(g) = \operatorname{dom}(h) \land g(n_{h,g}) < h(n_{h,g})) \end{align*}

If $max(ran(f))<max(ran(g))$ then $max(ran(f))<max(ran(h))$. If $max(ran(f))=max(ran(g))$ and $dom(f) < dom(g)$ then either $max(ran(f))=max(ran(h))$ or $dom(f) < dom(h)$.

checking the other properties of $'<'$ similarly, shows, that $f<h$.

1. totality: given $f \neq g$, we cannot have, $ran(f) = ran(g)$ and $dom(f) = dom(g)$ and $f(n) = g(n)$ for each $n$, since this would imply, $f=g$.

Let $A_g$ be the initial segment $\{ f \in \operatorname{Ord}^{<\omega} \mid f < g \}$. We will show first that:

For every $\alpha$ the set $A_{\{(0,\alpha)\}}$ is equal to $\alpha^{<\omega}$; specifically - replacing $\alpha$ with $\omega_\alpha$ -, each $\omega_\alpha^{<\omega}$ is an initial segment in $<$.

Question: what is the meaning of the notation $A_{(0,\alpha)}$?

• It was defined in the line before that: "Let $A_g$ be the initial segment..." In this case, $g=\{(0,\alpha)\}$, i.e. the function with domain $1=\{0\}$ and range $\{\alpha\}$. – Frunobulax Sep 17 '14 at 12:24
• Note that I didn't write $A_{(0,\alpha)}$ as you did but $A_{\{(0,\alpha)\}}$. – Frunobulax Sep 17 '14 at 12:31
• ok thank you. I will think about it a bit more and will edit my answer to my question accordingly – A student Sep 17 '14 at 12:37

The exercise says that "... an initial segment and its order-type is $\omega_\alpha$.", not that "... an initial segment and its cardinal is $\omega_\alpha$.".

I'm not sure, but my solution is:

$\quad$We define: \begin{aligned} \langle\alpha_0,\ldots&\rangle\prec\langle\beta_0,\ldots\rangle \leftrightarrow\\ &\text{there is }k\text{ such that }\\ &\qquad\alpha_k<\beta_k\text{ and }\alpha_i=\beta_i \text{ for all }i<k,\\ \langle\alpha_i:i<m&\rangle<\langle\beta_i:i<n\rangle\leftrightarrow\\ &\text{either }\sum_{i<m}\alpha_i+m < \sum_{i<n}\beta_i+n\\ &\text{or }\sum_{i<m}\alpha_i+m=\sum_{i<n}\beta_i+n\\ &\qquad\text{ and } \langle\alpha_i:i<m\rangle\prec\langle\beta_i:i<n\rangle.\\ \end{aligned}  $\quad$Let $X$ be the class of all finite sequences of ordinals. The relation $<$ defined above is a linear ordering of $X$. Moreover, if $S\subset X$ is nonempty, then $S$ has a least element. If we let $\Gamma(\alpha)=$ the order-type of the set $\{\beta\in X:\beta<\alpha\}$ for $\alpha\in X$, then $\Gamma$ is a one-to-one mapping of $X$ onto $Ord$. Note that for a finite sequence $\alpha$ in $\omega$, $\Gamma(\alpha)\in\omega$, and so $\langle\omega\rangle$ is the least element $\alpha$ of $X$ such that $\alpha$ is not a finite sequence in $\omega$; thus $\Gamma(\langle\omega\rangle)=\omega$.
$\quad$Let $\gamma(\alpha)=\Gamma(\langle\alpha\rangle)$. Note that $\gamma(\alpha)$ is an increasing function of $\alpha$, and also that since each infinite cardinal is indecomposable, by definition of $(X,<)$, $\gamma(\omega_\alpha)$ is the set of all finite sequences in $\omega_\alpha$. Let $\eta(\alpha)=$ the order-type of the set of all finite sequences in $\alpha$. Then $\gamma(\alpha)\le\eta(\alpha)$ and $\gamma(\omega_\alpha) =\eta(\omega_\alpha)$ for each $\alpha$. We show that $\gamma(\omega_\alpha)=\omega_\alpha$ by induction of $\alpha$. This is true for $\alpha=0$. Thus let $\alpha$ be the least ordinal such that $\gamma(\omega_\alpha)\ne\omega_\alpha$. Since $\gamma$ is increasing, $\gamma(\omega_\alpha)\ge\omega_\alpha$; thus $\gamma(\omega_\alpha)>\omega_\alpha$, and so there is a sequence $\beta$ such that $\Gamma(\beta)=\omega_\alpha$ and $\beta<\langle\omega_\alpha\rangle$. Then there is an ordinal $\delta$ such that $\beta<\langle\delta\rangle<\langle\omega_\alpha\rangle$; thus $\Gamma(\beta)=\omega_\alpha<\gamma(\delta)\le\eta(\delta)$ $\Leftrightarrow$ $\aleph_\alpha\le|\eta(\delta)|$ $=$ $|\eta(|\delta|)| \le\eta(|\delta|)$. But since $\delta<\omega_\alpha$, by the minimality of $\alpha$, $\eta(|\delta|)=|\delta|<\aleph_\alpha$. A contradiction. Finally, by definition of $\gamma$, for each nonzero limit ordinal $\alpha$, $\gamma(\omega_\alpha)= \text{sup }\{\gamma(\omega_\xi):\xi<\alpha\}=\omega_\alpha$.