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

Question

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?

Answer 1

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.

Answer 2

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$.

2. 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$.

3. 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)}$?

Answer 3

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$.