25
votes

### Can we interpret arithmetic in set theory, with exactly PA as the ZFC provable consequences?

The standard terminology is that an interpretation $I$ of a theory $U$ in a theory $T$ is faithful if for all sentences $\phi$ in the language of $U$,
$$T\vdash\phi^I\iff U\vdash\phi.$$
(Here and ...

23
votes

Accepted

### Do we expect that sufficiently large computable ordinals settle every question of arithmetic?

The question of whether a computable linear order is well-founded is $\Pi^1_1$-complete, so this is true in a sense:
There is a computable function $F$ such that, for every sentence $\varphi$ in the ...

22
votes

Accepted

### Did Edward Nelson accept the incompleteness theorems?

Gödel’s second incompleteness theorem requires neither exponentiation nor “impredicative concepts”. The systems Nelson works in are fragments of arithmetic interpretable on definable cuts in $Q$; one ...

22
votes

Accepted

### Can we interpret arithmetic in set theory, with exactly PA as the ZFC provable consequences?

This is equivalent to the $\Sigma_1$-soundness of $\mathsf{ZFC}$ (and this equivalence is highly robust to replacing $\mathsf{PA}$ with some other theory):
If $\mathsf{ZFC}$ is $\Sigma_1$-sound then ...

21
votes

### What is the logical status of the sentence combining the ideas of Löb and Rosser, "this sentence is provable before any proof of its negation"?

As Akiva Weinberger conjectured, this depends on the implementation.
Indeed, $0=0$ is a sentence of this type, i.e. $0=0$ is equivalent to the claim that there is a proof of $0=0$ that is shorter than ...

20
votes

### Do we expect that sufficiently large computable ordinals settle every question of arithmetic?

The claim of well-foundedness depends not only on the ordinal $α$, but also on how $α$ is represented by a recursive well-ordering.
Pathological representations
Strong statements from small ordinals: ...

17
votes

### What can be proven in Peano arithmetic but not Heyting arithmetic?

According to Harvey Friedman, the following theorem is provable in PA but not HA:
Every polynomial $P:\mathbb{Z}^n \to \mathbb{Z}^m$ with integer coefficients assumes a value closest to the origin.
...

16
votes

### Is (Z,+,0,1,P2,P3) decidable?

Christian Schulz (a grad student at Urbana) and Philipp Hieronymi have recently shown that $(\mathbb{Z},+,<,2^{\mathbb{N}},3^{\mathbb{N}})$ is undecidable. And I believe they prove this for $(\...

15
votes

### What is the canonical way to extend Peano's axioms to the set of all integers?

Here is a somewhat different way to think about it, although the result is equivalent to the theories in the other answers.
Begin with the observation that the structures $\langle\mathbb{N},+,\cdot,0,...

14
votes

Accepted

### Dedekind-Peano axioms, but numbers have at most one successor

Victoria Gitman and I recently looked at the first-order version of this theory, which we called fPA, to contrast it with the theory FPA, which Woodin has looked into, which is a possibly stronger ...

13
votes

### Did Edward Nelson accept the incompleteness theorems?

(EDIT: I have substantially rewritten this answer in light of what I have learned from Emil Jeřábek and from reading some of the relevant references more carefully.)
As Emil Jeřábek has said, the ...

13
votes

### How special is first-order $\mathsf{PA}$?

There are several notable papers, starting with a key paper of Angus Macintyre (Ramsey quantifiers in arithmetic, Model theory of algebra and arithmetic, Lecture Notes in Math., 834, Springer, 1980), ...

13
votes

### What is the canonical way to extend Peano's axioms to the set of all integers?

I don't think there is one canonical system. Some version of what you wrote would do (but you need to do something about ordering). In model theory of arithmetic, where it is often convenient to work ...

11
votes

### Interpretation of $ZFC^-$ in 2nd order Peano arithmetic

This started out as a comment, but it ended up too long so here it is as an answer.
The best reference I know for this is Simpson's book Subsystems of Second-Order Arithmetic, who does most—not quite ...

10
votes

Accepted

### How special is first-order $\mathsf{PA}$?

This argument has a couple of iffy points, but I believe it does work.
In this paper, Shelah introduced a logic $\mathcal{L}(Q_{\mathrm{Brch}})$ which is fully compact, has the property that any ...

10
votes

### Dedekind-Peano axioms, but numbers have at most one successor

I've looked at the system you've mentioned, where you assume these as mathematical axioms:
(1) Uniqueness of successoring
(2) Uniqueness of predecessoring
(3) 0 doesn't have a predecessor
(4) ...

9
votes

Accepted

### What is the proof-theoretic ordinal of bare $\mathsf{NFU}$?

As in the question, I will use $\mathsf{NFU}$ for "bare" $\mathsf{NFU}$, i.e., the result of weakening the extensionality axiom in Quine's $\mathsf{NF}$ so as to allow urelements. Let $\...

9
votes

### Which recursively-defined predicates can be expressed in Presburger Arithmetic?

In addition to the answers above, it is worth mentioning that the existential fragment of Presburger arithmetic can actually be extended by a full divisibility predicate while retaining decidability [...

Community wiki

9
votes

Accepted

### How much induction does a p-adic valuation need?

If you want to stick to theories in the basic language of arithmetic $\langle0,1,+,\cdot,<\rangle$, the irrationality of $\sqrt2$ can be easily proved in the theory $IE_1$ (i.e., using induction ...

8
votes

### Can there be computable non-standard models of PA in a weaker sense?

This is a great question!
Let me give a meager partial answer, for the case where we are talking
about nonstandard models of true arithmetic.
Theorem. No nonstandard model of true arithmetic arises ...

7
votes

### Models of arithmetic in a signature with exponentiation but not addition and multiplication

$\mathsf{TA}_{\exp}$ does have recursive nonstandard models. In fact, even the considerably stronger theory $\mathrm{Th}(\mathbb N,+,2^x)$ (Presburger arithmetic with exponentiation) has recursive ...

7
votes

Accepted

### Is the statement "All numbers are counting numbers" independent of $PA$?

The statement asserting that every number is a counting number is $\forall n\ C(n)$, and this is definitely independent of PA, if PA is understood to include induction only in the usual language of ...

7
votes

### How much induction does a p-adic valuation need?

This is not intended as an answer but rather as a long-winded explanation of what having a 2-adic valuation means for really weak theories such as Q and open induction, which is much too long for a ...

7
votes

### What is the logical status of the sentence combining the ideas of Löb and Rosser, "this sentence is provable before any proof of its negation"?

As Akiva Weinberger and Will Sawin have already pointed out, the answer does depend on the details of the of the formalisation of the notion of proof.
Let's fix some terminology: Given a proof ...

7
votes

### Dedekind-Peano axioms, but numbers have at most one successor

As pointed out by Emil Jeřábek (in the comment to Joel Hamkins' answer), the system you are referring to is known as "Peano Arithmetic with a top". It has been studied for several decades. A ...

6
votes

Accepted

### Extensions of the Ackermann interpretation to nonstandard theories of arithmetic

Based on the comments, I think it's worth clarifying some points about the Ackermann interpretation.
The Ackermann interpretation is definable: it is a formula $\varphi(x, y)$, and - given a model $M\...

6
votes

Accepted

### Does ACA prove categoricity of the reals?

The current version of the question is flawed: the proposed categoricity principle is in fact classically false. Roughly speaking, any "interesting" theory of the appropriate type is going ...

6
votes

### Can $\mathsf{RCA}_0$ prove that every nonempty c.e. set $A \subseteq \mathbb{N}$ has a least element?

As Emil Jeřábek and James Hanson mentioned in comments, this is well-known in the literature of first-order arithmetic as the $\Sigma_1$ least number principle, $\mathsf{L}\Sigma_1$. Simpson doesn't ...

Only top scored, non community-wiki answers of a minimum length are eligible

#### Related Tags

theories-of-arithmetic × 275lo.logic × 215

set-theory × 60

model-theory × 58

proof-theory × 34

computability-theory × 29

reverse-math × 21

nt.number-theory × 20

reference-request × 19

foundations × 14

ultrafinitism × 12

ordinal-analysis × 11

mathematical-philosophy × 10

metamathematics × 9

decidability × 8

computational-complexity × 7

ac.commutative-algebra × 6

induction × 6

forcing × 5

ordinal-numbers × 5

nonstandard-analysis × 5

bounded-arithmetic × 5

prime-numbers × 4

constructive-mathematics × 4

axioms × 4