0
$\begingroup$

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?

$\endgroup$
0
3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ – A student Sep 17 '14 at 10:52
  • $\begingroup$ 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?) $\endgroup$ – Frunobulax Sep 17 '14 at 10:58
  • $\begingroup$ 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? $\endgroup$ – A student Sep 17 '14 at 11:18
  • $\begingroup$ See the hint I added above. $\endgroup$ – Frunobulax Sep 17 '14 at 11:30
  • $\begingroup$ 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. $\endgroup$ – A student Sep 17 '14 at 12:16
0
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ 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\}$. $\endgroup$ – Frunobulax Sep 17 '14 at 12:24
  • 1
    $\begingroup$ Note that I didn't write $A_{(0,\alpha)}$ as you did but $A_{\{(0,\alpha)\}}$. $\endgroup$ – Frunobulax Sep 17 '14 at 12:31
  • $\begingroup$ ok thank you. I will think about it a bit more and will edit my answer to my question accordingly $\endgroup$ – A student Sep 17 '14 at 12:37
0
$\begingroup$

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

$\endgroup$

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.