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

Question

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

Answer 1

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 as follows: Let $f$ and $g$ be distinct elements of $\omega^X$ and let $x$ be the greatest element of $x$ for which $f(x)\neq g(x)$. Then $f<g$ if and only if $f(x) < g(x)$. Then $\omega^X$ is well ordered. 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.

Answer 2

In the course of writing an expository article on the consistency of arithmetic, I was led to try to explain $\epsilon_0$ in as "finitary a manner" as possible. Here is what I came up with, inspired greatly by the account in Torkel Franzen's book Inexhaustibility: A Non-Exhaustive Account, as well as the LISP programming language.

Define a list to be either an empty sequence—denoted by ( ) and referred to as the empty list—or, recursively, a finite nonempty sequence of lists. If we write a list by separating the constituent elements by commas and enclosing the entire sequence with parentheses, then for example, (( ), ( ), ( )) and ((( ), ( )), ((( ), (( ), ( ))), ( ))) are lists. The number of constituent lists is called its length (it is zero for the empty list). If $a$ is a nonempty list, then we write $a[i]$ for the $i$th constituent list of $a$, where $i$ ranges from 1 to the length of $a$.

Next, recursively define a total ordering $\le$ on lists as follows (it is essentially a lexicographic ordering). Let $a$ and $b$ be lists, with lengths $m$ and $n$ respectively. If $m\le n$ and $a[i] = b[i]$ for all $1\le i \le m$ (this condition is vacuously satisfied if $m=0$), then $a\le b$. Otherwise, there exists some $i$ such that $a[i] \ne b[i]$; let $i_0$ be the least such number, and declare $a< b$ if $a[i_0] < b[i_0]$.

Finally, recursively define a list $a$ to be an ordinal (or more precisely, an ordinal below $\epsilon_0$, but I will just say ordinal for short) if all its constituent lists are ordinals and $a[i] \ge a[j]$ whenever $i<j$. (In particular, the empty list is an ordinal, since the condition is vacuously satisfied.)

As an exercise, you can verify that the ordinals ((( ))) and ((( ), ( ))) and ((( )), (( ))) are, in standard notation, the same as $\omega$, $\omega^2$, and $\omega \cdot 2$ respectively.

My personal opinion is that the usual ways of defining $\epsilon_0$ make it seem mind-bogglingly infinitary, but the above definition makes it clear that any particular ordinal is just a special type of finite list of finite lists of finite lists of … of finite lists. Not very infinitary at all.

The proof that there is no infinite descending sequence is not particularly mind-boggling either, in this language. Rather than type it out here, I refer you to the proof of Theorem 1 in my expository article.

I find that after understanding this proof, the hard thing to wrap my head around is how it can possibly be true that PA does not prove that there is no infinite descending sequence. My current gut feeling is that PA seems weirdly weak, because it cannot even formalize a proof as simple as this one.

Answer 3

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

Answer 4

This is meant to be a simple but perhaps slightly alternative answer. Define two functions $V_1:\epsilon_0 \rightarrow \epsilon_0$ and $V_2:\epsilon_0 \rightarrow \epsilon_0$.

For any given $x$, define $\gamma$ as the smallest ordinal such that $\gamma \cdot \omega > x$. And now define:

$V_1(x)=0 \qquad \qquad \qquad \qquad \qquad when\; x<\omega$

$V_1(x)=\alpha \;such\; that\; \omega^\alpha=\gamma \qquad \quad when\; x \geq\omega$

$V_2(x)=Pre(x) \qquad \qquad \quad when\; x<\omega$

$V_2(x)=Lsub(\gamma,x) \qquad \qquad when \; x \geq\omega $

Here $Pre$ stands for usual predecessor function (with output $0$ on $0$). And $Lsub:\epsilon_0 \times \epsilon_0 \rightarrow \epsilon_0$ is defined as: $$Lsub(\alpha,\beta)=0 \qquad if \, \alpha > \beta$$ $$Lsub(\alpha,\beta)=\{\,y\in \epsilon_0\,|\,\alpha+y=\beta\,\} \qquad if \, \alpha \le \beta$$

Note that for all values in the domain (except $x=0$), we have $V_1(x)<x$ and $V_2(x)<x$. Furthermore, we can observe that for any non-zero ordinals $\alpha_1,\alpha_2<\epsilon_0$ (where $\alpha_1 \neq \alpha_2$) it is not the case that $V_1(\alpha_1)=V_1(\alpha_2)$ and $V_2(\alpha_1)=V_2(\alpha_2)$.

And with this we can associate with every ordinal less than $\epsilon_0$ a "unique" finite tree. Each node will have either "two" or "no" child nodes. Also each node is individually completely unmarked (no number/label etc. associated with it).

For example, for any $\alpha<\epsilon_0$ we can define the left-subtree as the tree of $V_1(\alpha)$ and right-subtree as the tree of $V_2(\alpha)$. Furthermore, the tree for $0$ can be defined just as a single (unmarked) node. I think one can use (transfinite) induction to show that for any non-zero ordinals $\alpha_1,\alpha_2<\epsilon_0$ (where $\alpha_1 \neq \alpha_2$), their representations as trees will be different.

Perhaps to someone who is "very skeptical" that $\epsilon_0$ can be well-ordered at all (in terms of finite objects) one could try to convince them that the functions $V_1$ and $V_2$ are simple enough that applying any possible combination of them (as composition) on a given $\alpha<\epsilon_0$ would return to $0$ in finite attempts.

For just applying $V_1$ it is very easy to see. For example, $V_1(\omega^{\omega^\omega})=\omega^\omega$, $V_1(\omega^\omega)=\omega$, $V_1(\omega)=1$, $V_1(1)=0$. Similarly $V_1(\omega^{\omega^2})=\omega^2$. So it seems to me that application $V_1$ can be thought of as just "eating up" the towers (and finite number of towers will be eaten up with finite number of attempts).

But the situation seems more complex for a combination and convincing someone who is "very skeptical" might require a more intuitive/visualisable explanation that any combination (of $V_1$ and $V_2$ applied as composition) would also always go back to $0$ in finite attempts.

---

But it seems that a good way to see whether there is no infinite descending chain is to write down a complex game where the person claiming the chain is supposed to provide a new (natural) number at each stage. And eventually showing that no matter what numbers are provided, the game has to terminate.

Edit: I noticed the faulty reasoning in my previous post. I have removed it.

P.S. I noticed this question under the "Related" list. I hope it is fine to bump an old question (especially if it has an accepted answer) for a slightly different kind of answer.