# Understanding the countable ordinals up to $\epsilon_{0}$

Hello,

in a recent MO question, link, discussing the current foundations of mathematics, the author linked a video lecture by Prof. Voevodsky, which argues against the principle of $\epsilon_{0}$-induction used in Gentzen's proof of the consistency of PA.

In discussions arising from the question, some people commented that imagining an infinite descending chain in $\epsilon_{0}$ is "crazy".

I would like to understand better this ordinal, since I actually don't know exactly how to depict it in my mind.

I have clear in my mind the order associated with the finite ordinals. I use in my mind a notation of the following kind:

$1 = I$

$2= II$

$3= III$

$4= IIII$

$\omega = (III\dots)$

$\omega+1= (III\dots)I$

$\omega +2 = (III\dots)II$

$\omega + \omega= \omega \cdot 2= (III\dots)(III\dots)$

In general I understand $\alpha + \beta$ as the juxtaposition of the two representations.

$\omega\cdot 3 = (III\dots)(III\dots)(III\dots)$

$\omega\cdot \omega = \omega^{2} = \big( (III\dots)(III\dots)(III\dots)\dots\big)$

In general I understand $\alpha \cdot \beta$, by replacing each $I$ symbol in $\beta$ with the representation of $\alpha$. So

$\omega^{3}=\omega^{2}\cdot \omega = \big( \omega^{2} \omega^{2} \omega^{2} \dots \big)$

This allows me to visualize every ordinal of the form $\omega^{n}\cdot m + k$, with $n,m,k$ naturals (i.e finite ordinals). So far I have absolutely no doubt that there are no infinite descending chain in ordinals of the form $\omega^{n}\cdot m + k$.

However I start having problem with the ordinal $\omega^{\omega}= \bigsqcup_{n<\omega}\omega^{n}$. Do you have any idea on how to visualize $\omega^{\omega}$ is a way consistent with the representation used above (which i actually found here) ?

Anyway, looking at wikipedia, I still manage to visualize $\omega^{\omega}$ as the set of infinite strings of natural number, having only finitely many digits different from $0$.

Still I have no doubt that there are no infinite descending chain in $\omega^{\omega}$.

Perhaps i might be able to understand $\omega^{\omega^{\omega}}$, namely the set of infinite strings labeled with elements of $\omega^{\omega}$, having only finitely many elements different from $0$. Or (i guess) equivalently a $\omega\times\omega$ square labeled with naturals, where only finitely many columns are different from $0^{\omega}$, and all of these non constant-$0$ columns, contains only finitely many digits different from $0$.

However I do not know how to visualize $\epsilon_{0}$. I mean I know that the elements of $\epsilon_{0}$ can be represented by finite-branching finite trees labeled with natural numbers, but that doesn't give me a strong intuition about the fact that no infinite chain exists, so I guess its not a great picture (or at least I do not understand it properly, yet).

Questions

A) Could you suggest a way to visualize $\omega^{\omega^{\omega}}$? It should be in such a way to convince me about the fact that there are no infinite down-chain.

B) Could you suggest a way to visualize $\epsilon_{0}$, again arguing that it should be very clear that there are no infinite down-chain.

C) Could you please state your opinion about Prof. Voevodsky, which argues against the principle of $\epsilon_{0}$-induction used in Gentzen's? This shouldn't be a duplicate of the previous, wider thread link, I'm only interested in this little bit of Voevodsky's talk.

Thank you in advance,

bye

matteo

-
There is an interpretation in terms of sorted lists here: sbseminar.wordpress.com/2009/12/07/… –  Qiaochu Yuan Feb 20 '11 at 14:02
Duplicate? mathoverflow.net/questions/5065/… –  François G. Dorais Feb 20 '11 at 15:43
Thanks Qiaochou an Yuan! I apologize if this is considered to be a duplicate. Even if I tried to search for epsilon_{0} in MO, i couldn't find that Question, which I think it's indeed quite close to mine. Also Qiaochu's proposed link comes from the same question, so I guess you might consider to close this one, if you think that's appropriate. thanks again! –  Matteo Mio Feb 20 '11 at 15:56

The standard way to visualize $\epsilon_0$ is by the Hydra game. Here the elements of $\epsilon_0$ are visualized as isomorphism classes of rooted finite trees. The inequality can be described by the "cutting off heads" rule: The tree $T_1$ is greater than $T_2$ is there is a series of head cuttings which reduces $T_1$ to $T_2$. Writing out the inequality relationship between trees directly is a pain, see my blogpost. If you turn those nested sets into trees in the obvious way, you get the Hydra game.

I am told that most people do not find it intuitive that the Hydra game ends. I find that, once I've played a few rounds (try this applet) I find it "obvious", although writing down an actual proof is still painful.

As far as an actual proof, you should directly show the following: Let $X$ be a totally ordered set. Let $\omega^X$ be the set of functions $X \to \omega$ which are $0$ for almost all $x \in X$, ordered lexicographically. Then $\omega^X$ is well ordered. (UPDATE: There are errors in this paragraph, see David Milovich's comment below.)

So every tower of $\omega$'s is well ordered and, $\epsilon_0$, being the union of all such towers, is also well-ordered.

By the way, you don't ask this, but you might be curious what happens when you try to write out this proof within PA. Recall that PA can't directly talk about subsets of $\omega$. The statement that $\omega$ is well-ordered is encoded as an axiom schema. Let $\phi(x, y_1, y_2, \ldots, y_N)$ be any statement with variables $x$ and $y_i$ running through $\omega$. Then PA has the following axiom: $$\forall y_1, y_2, \ldots, y_n \in \omega: \left( \exists x \in \omega : \phi(x, y_{\bullet}) \implies \exists x' \in \omega : \left( \phi(x', y_{\bullet}) \wedge \forall x \in \omega \left( \phi(x, y_{\bullet}) \implies x \geq x' \right) \right) \right).$$ Please read this axiom until you understand that, in English, it says "For all $y$'s, if there is some $x$ obeying $\phi$, then there is a least $x$ obeying $\phi$."

Let's call this axiom $W(\phi, \omega)$. We'll use similar notation with $\omega$ replaced by other sets. Here is a challenging and important exercise: Let $X$ be an ordered set. Let $\phi$ be a statement about $\omega^X$, which may have other variables $y_i$ in it. Construct a specific statement $\sigma(\phi)$ about $X$, with other variables $z_i$ running through $X$, such that $$W(\sigma(\phi), X) \implies W(\phi, \omega^X) \quad (*).$$

For every specific $\phi$, the statement $(*)$ can be proved in PA. Since $W(\psi, \omega)$ is a axiom of PA for every $\psi$, we can prove $W(\phi, \omega^{\omega^{\ldots^{\omega}}})$ in PA for any $\phi$ and any specific height of tower.

But, in order to show that $\epsilon_0$ is well-ordered, we need to show that $W(\phi, \omega^{\omega^{\ldots^{\omega}}})$ simultaneously for every height of tower. Tracing through the arguments here, you would need to know $W(\phi, \omega)$, $W(\sigma(\phi), \omega)$, $W(\sigma(\sigma(\phi)), \omega)$, $W(\sigma^3(\phi), \omega)$ and so forth. As a human mathematician, that probably doesn't bother you at all. But, in the formal system PA, any proof can only use finitely many axioms. So there is no way to write a proof which uses all of the axioms $W(\sigma^k(\phi), X)$, for all $k$.

Of course, this doesn't show that some more clever argument couldn't prove that $\epsilon_0$ is well-ordered while working with PA; you need the Kirby-Paris theorem for that. (More precisely Kirby-Paris plus Godel shows that, if PA proves $\epsilon_0$ is well-ordered, then PA is inconsistent.) But I find that seeing this obstacle, the need to use infinitely many versions of the well-ordering axiom, clarifies my understanding of what is gong on.

-
Thanks for the answer (although I didn't write the question). I was searching for these proofs, but that was rather hard to find. Most proofs (such as in the Wikipedia), stop by saying that it is well-ordered. –  Lucas K. Feb 20 '11 at 18:25
Hi David, I'll definitely need a couple of days to digest your blog's post and this answer, but from what I already managed to understant, it is great and very clear!! thank you a lot! –  Matteo Mio Feb 20 '11 at 19:57
David, I think you answered another question from me: mathoverflow.net/questions/25430/… Give the proof, I think the answer to that question is Yes! FOL + PA extended with COR can prove Goodsteins-theorem. –  Lucas K. Feb 20 '11 at 20:31
This answer is over a year old, but for the sake of future readers: This is false: "Let $X$ be a totally ordered set. Let $\omega^X$ be the set of functions $X \to \omega$ which are $0$ for almost all $x \in X$, ordered lexicographically. Then $\omega^X$ is well ordered." Just look in $\omega^\omega$: the characteristic functions of the singletons. The correct version requires $X$ to be well ordered and gives $\omega^X$ the reverse lexicographic order, i.e., compares functions at their greatest coordinate of disagreement. –  David Milovich Jul 31 '12 at 18:37

David Speyer's blog post, inspired by the MO question referenced by Francois Dorais in the comments, contains a detailed answer to this question.

-
The blog post gives in detail how to encode ordinals. However, there is no proof that there isn't a infinite descending chain. –  Lucas K. Feb 20 '11 at 16:18
Yes Tom's right. Moreover as I said in the question, some people feel uncomfortable about the absence of infinite down-chains in $\epsilon_{0}$ (or at least this is what i get from Voevodsky's talk). I'm not either comfortable or uncomfortable to be honest, that's why i'm seeking some explanation to build up my own prospective. (I haven't had time yet to read Speyer's blog post though!) –  Matteo Mio Feb 20 '11 at 17:33