38
$\begingroup$

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

$\endgroup$
13
  • 4
    $\begingroup$ There is an interpretation in terms of sorted lists here: sbseminar.wordpress.com/2009/12/07/… $\endgroup$ Feb 20, 2011 at 14:02
  • $\begingroup$ Duplicate? mathoverflow.net/questions/5065/… $\endgroup$ Feb 20, 2011 at 15:43
  • $\begingroup$ 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! $\endgroup$
    – user11618
    Feb 20, 2011 at 15:56
  • 1
    $\begingroup$ I don't know if this qualifies as "visualization", but Takeuti's book has a very explicit and lengthy discussion of precisely this issue. $\endgroup$ Jun 1, 2015 at 19:13
  • $\begingroup$ @ChristianRemling, do you remember which book? (Is it Introduction to Axiomatic Set Theory?) $\endgroup$ Jan 5, 2018 at 21:04

4 Answers 4

31
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Lucas K.
    Feb 20, 2011 at 18:25
  • $\begingroup$ 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! $\endgroup$
    – user11618
    Feb 20, 2011 at 19:57
  • $\begingroup$ 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. $\endgroup$
    – Lucas K.
    Feb 20, 2011 at 20:31
  • 9
    $\begingroup$ 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. $\endgroup$ Jul 31, 2012 at 18:37
  • 2
    $\begingroup$ I finally went and fixed the error David Milovich points out; thanks for the correction. $\endgroup$ Sep 11, 2021 at 11:19
5
$\begingroup$

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.

$\endgroup$
19
  • $\begingroup$ "My personal opinion is that the usual ways of defining $\epsilon_0$ make it seem mind-bogglingly infinitary" .... My personal opinion is that every recursive ordinal is fundamentally finitary (but only once we understand it and realise that the larger structures involved in the def. are merely to help us in keeping track of complex steps of visualisation). So I would personally use the term complex instead of infinitary in the given quote since, in my personal opinion, making a divide of finitary/infinitary at some arbitrary point isn't quite right. But anyway, just my thoughts. $\endgroup$
    – SSequence
    Jan 10, 2019 at 8:34
  • $\begingroup$ But perhaps, "finitary" doesn't have a fixed meaning anyway. Because, based on various essays (on related topics) I have read/skimmed, it seems that its precise meaning is subject to interpretation. But honestly, I don't really know. Anyway, there is also another nice exposition for an (easy) notation for $\epsilon_0$ in the book "Where is the godel point hiding". (I haven't read it though) $\endgroup$
    – SSequence
    Jan 10, 2019 at 11:23
  • $\begingroup$ @SSequence : I agree; "finitary" has no fixed meaning. Back in Gentzen's day, what we now call primitive recursive arithmetic (PRA) was considered finitary, and people hoped for a finitary consistency proof of PA. Since induction up to $\epsilon_0$ was the only non-PRA ingredient in Gentzen's consistency proof, he discussed in detail whether such an induction could be considered finitary. So $\epsilon_0$ and the word finitary (or its German cognates) have a long history of being connected to each other. Even today, I hear suspicions voiced about $\epsilon_0$ being illegitimately infinitary. $\endgroup$ Jan 10, 2019 at 16:05
  • $\begingroup$ @SSequence I think we need to distinguish between "has a finitary description" and "has a fully analyzable finitary description" - the point isn't that the index for a Turing machine building a copy of $\epsilon_0$ need be "infinitary" somehow, but rather the (argued) lack of finitistic methods for establishing the "fundamental facts" about such an index (e.g. "is well-founded"). Of course this just introduces more subjectivity into the issue - even ignoring finitaritude(?), what does "fully analyzable" (/"fundamental facts") mean? - but I think it's a meaningful distinction. $\endgroup$ Jan 10, 2019 at 16:13
  • $\begingroup$ @TimothyChow The impression I had about this term was similar. That is, it seems to me that nearly all (usual) forms of "finitism" accept PRA (something that I have seen mentioned numerous times in relation to finitism). And after that they accept more principles depending on circumstances or arguments directly presented to them. Anyway it is good to have it clarified, since a lot of the survey books on phil. seem to be very formal about it and don't mention this kind of thing very clearly. $\endgroup$
    – SSequence
    Jan 10, 2019 at 17:14
4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ The blog post gives in detail how to encode ordinals. However, there is no proof that there isn't a infinite descending chain. $\endgroup$
    – Lucas K.
    Feb 20, 2011 at 16:18
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.