Skip to main content

All Questions

Filter by
Sorted by
Tagged with
6 votes
1 answer
743 views

Which part(s) of this proof of Goodstein's Theorem are not expressible in Peano arithmetic?

EDIT: Noah Schweber helpfully points out that $\mathsf{ACA}_0$ is a conservative extension of Peano arithmetic in which certain aspects of my proof not expressible in Peano arithmetic are expressible. ...
Julian Newman's user avatar
4 votes
1 answer
269 views

Does Peano's axioms prove $\alpha$-induction for primitive recursive sequences for every concrete $\alpha < \varepsilon_0$?

It is well-known that Peano's axioms (PA) cannot prove $\varepsilon_0$-induction for primitive recursive sequences (PRWO($\varepsilon_0$)), because PA + PRWO($\varepsilon_0$) proves the consistency of ...
Imperishable Night's user avatar
1 vote
0 answers
123 views

Is possibile to define transfinite sum and product recursively? [closed]

On mathstackexchange a few days ago I published the following question where I asked about "transfinite" sum and products but actually nobody answered or gave an opinion with a comment: thus ...
Antonio Maria Di Mauro's user avatar
6 votes
0 answers
422 views

What is proof-theoretic ordinal of weak first-order arithmetic?

According to Wikipedia(https://en.wikipedia.org/wiki/Ordinal_analysis) and nlab(https://ncatlab.org/nlab/show/ordinal+analysis), a proof-theoretic ordinal of $\mathsf{PRA}$ is $\omega^\omega$. ...
Alwe's user avatar
  • 178
3 votes
1 answer
181 views

Least ordinal not embedded in a total order

If $(E,<)$ is a linear order, let $s(E,<)$ denote the least ordinal which doesn't embed in $(E,<)$. I am trying to prove the following: If $(M,+,.,0,1)$ is a model of open induction, (or ...
nombre's user avatar
  • 2,519
13 votes
3 answers
1k views

Which ordinals can be proof-theoretic ordinals of a reasonable theory?

When talking to a friend recently he asked a question - are there any reasonable first-order theories which have proof theoretic ordinal equal to small or large Veblen ordinal? I have then extended ...
Wojowu's user avatar
  • 28.2k
12 votes
1 answer
835 views

Transfinitely extending $\sf PA$ — can we get stronger than $\sf ZFC$?

Let $\sf PA$ denote the theory of natural numbers with constants $(0, 1)$ and binary operators $(+,\times)$ based on the first-order predicate calculus with equality, having the following axioms, ...
Vladimir Reshetnikov's user avatar
27 votes
5 answers
4k views

What is induction up to $\varepsilon_0$?

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 ...
David E Speyer's user avatar