26
$\begingroup$

This is a question asked out of curiosity, and because I can't understand the Wikipedia page.

I have often been told that PA cannot prove the validity of induction up to $\epsilon_0$, which has been expressed to me roughly as the claim that $\epsilon_0$ is well-ordered. I understand what ordinals are, and what $\epsilon_0$ is. I also understand first order logic and axiom schemes, so I understand how the induction axiom scheme formalizes the notion that $\omega$ is well-ordered.

What I don't understand is how one could formulate the statement that $\epsilon_0$ is well-ordered as a first order sentence in arithmetic. Would someone mind spelling this out for me?

$\endgroup$
  • $\begingroup$ Does what you're looking for start on page 456 of this paper? projecteuclid.org/… $\endgroup$ – Jason Dyer Nov 11 '09 at 16:40
  • 1
    $\begingroup$ Maybe, but if it is there I don't understand it. This seems to be explaining how to label trees by ordinals below $\epsilon_0$. I'm trying to figure out how to pack epsilon_0 into positive integers, which are the objects PA is allowed to talk about. $\endgroup$ – David E Speyer Nov 11 '09 at 16:52
  • 1
    $\begingroup$ This reference explains how to encode $\epsilon_0$ into $\omega$. You just split $\omega$ into infinitely many countable sets and embed $S_i$ into the $i$-th set (all in a recursive manner). $\endgroup$ – Ori Gurel-Gurevich Nov 11 '09 at 17:04
  • 2
    $\begingroup$ Every ordinal under epsilon_0 has a unique Cantor normal form which can then be encoded as a natural. $\endgroup$ – Dan Piponi Nov 12 '09 at 2:22
10
$\begingroup$

Here's a more detailed answer:

The above-mentioned link constructs a recursive relation $E$ on $\omega$, such that $(\omega, E)$ is isomorphic to $(\epsilon_0, \in )$. Then, induction up to $\epsilon_0$ is interpreted as $E$-induction, that is, for every predicate $\phi$, if $(\forall x E y \phi(x))\rightarrow \phi(y)$ then $\forall y \phi(y)$.

$\endgroup$
17
$\begingroup$

I now realize that a full answer to this question would be far longer than is appropriate for MathOverflow. So I wrote a blog post. Thanks to everyone who helped me understand what is going on here.

$\endgroup$
  • $\begingroup$ @DavidE.Speyer: Since on your blog post, $\omega^{\omega}$ is represented by the list (((()))), is there some reason why $\epsilon_0$ cannot have a 'finitary' representation of a similar sort? $\endgroup$ – Thomas Benjamin Jul 24 '19 at 20:55
2
$\begingroup$

The answer to your question can be found in Maria Hameen-Anttila's paper, "Nominalistic Ordinals, Recursion on Higher Types, and Finitism", Bulletin of Symbolic Logic,25(1), 101-124 (2019). Since the version I have immediate free access to is the Accepted author manuscript version found on the University of Helsinki research portal (www.researchportal.helsinki.fi/publications/nominalistic-ordinals-recursion-on-higher-types-and-finitism), I will be using that version's pagination rather than the published version's pagination when referring to the pages on which the answer to your question can be found.

To begin with, the answer to your question can be found on pp. 4-14 (these pages also provide the historical context regarding the answer--the actual answer can be found on pp. 12-14 in the Accepted author manuscript on the Web). I hope this helps.

As regards the statement, "I have often been told that $PA$ cannot prove the validity of induction up to $\epsilon_0$, which has been expressed to me roughly as the claim that $\epsilon_0$ is well-ordered", you might consider Noah Schweber's nice answer to my mathoverflow question, "What does 'can almost be proven in $PA$' mean regarding Theorem 2 of Timothy Chow's expository article, 'The Consistency of Arithmetic' ":

We have an arithmetic statement of the form

$(*)$ $\forall$$x$$\varphi$($x$)

which while not provable in $PA$ has the property that for each natural number $n$ the instance

$(*)_{n}$ $\varphi$($\mathfrak n$)

is provable in $PA$ (where "$\mathfrak n$" is the numeral corresponding to the natural number $n$)...

...Note that we also have the same phenomenon with respect to consistency: for each natural number $n$, $PA$ proves "there is no $PA$-proof of '0=1' of length $\lt$ $n$." So $PA$ almost proves $Con$($PA$).

It should be noted that this same phenomenon holds for defining $\epsilon_0$ as well. As is known, $\epsilon_0$ can be defined as follows:

{$\omega$, $\omega^{\omega}$, $\omega^{\omega^{\omega}}$,...} = $\epsilon_0$ for a countably infinite number of iterations of $\omega^{\alpha}$.

Since it is known that $PA$ proves that each of the elements of $\epsilon_0$ is well-ordered, but doesn't prove that the set of ordinals that is itself $\epsilon_0$ is well-ordered, one can see that the aforementioned set is well-ordered since each of its members is well-ordered. Here we have a early concrete example of Godel's First Incompleteness Theorem before Paris-Harrington or Goodstein sequences. I hope this clarifies things at least somewhat.

$\endgroup$
1
$\begingroup$

Maybe it's spelled out in a more convenient way in Wikipedia here (about Goodstein sequences), or in the page about Gentzen's consistency proof of Peano's arithmetic.

Hope this helps.

$\endgroup$
1
$\begingroup$

David, if you are still confused, note that any ordinal under $\epsilon_0$ can be converted into what is essentially a base-ω positional numeral system. There are more details here.

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