27
$\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 $\varepsilon_0$, which has been expressed to me roughly as the claim that $\varepsilon_0$ is well-ordered. I understand what ordinals are, and what $\varepsilon_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 $\varepsilon_0$ is well-ordered as a first order sentence in arithmetic. Would someone mind spelling this out for me?

Improve this question
$\endgroup$
6
  • $\begingroup$ Does what you're looking for start on page 456 of this paper? projecteuclid.org/… $\endgroup$
    – Jason Dyer
    Commented Nov 11, 2009 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
    Commented Nov 11, 2009 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
    Commented Nov 11, 2009 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
    Commented Nov 12, 2009 at 2:22
  • 1
    $\begingroup$ @TheAmplitwist : I think $\epsilon$ looks too much like $\in. \qquad$ $\endgroup$
    – Michael Hardy
    Commented May 31, 2023 at 18:43

5 Answers 5

Reset to default
12
$\begingroup$

Here's a more detailed answer:

The above-mentioned link (recreated below [1]) 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)$.

[1] P. Tosi, Normal derivability and first-order arithmetic, Notre Dame J. Formal Logic 21(2): 449-466 (April 1980) doi:10.1305/ndjfl/1093883058.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Alas, it seems to be a dead link now. $\endgroup$
    – Geoffrey Irving
    Commented May 30, 2023 at 17:47
  • $\begingroup$ @GeoffreyIrving added a link to the (hopefully correct) paper. $\endgroup$
    – Ori Gurel-Gurevich
    Commented May 31, 2023 at 22:11
18
$\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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Jul 24, 2019 at 20:55
  • 1
    $\begingroup$ $\epsilon_0$ does have a finitary representation of a similar sort! It is a computable ordinal and quite low on the Veblen hierarchy (see e.g. this). However it does not have a Cantor normal form (and is the first such ordinal), so the notation needs to be different from that one. $\endgroup$
    – cody
    Commented May 31, 2023 at 22:18
  • $\begingroup$ and $\mathrm{PA}$ does not prove that induction up to $\epsilon_0$ is well-founded for any "reasonable" notation system for it, though it can express that statement. $\endgroup$
    – cody
    Commented May 31, 2023 at 22:20
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) doi:10.1017/bsl.2018.91. Since the version I have immediate free access to is the accepted author manuscript version found on the University of Helsinki research portal, 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"? (available as arXiv:1807.05641):

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.

Improve this answer
$\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.

Improve this answer
$\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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .