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
Best Answer
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.