# Tag Info

## Hot answers tagged theories-of-arithmetic

Accepted

### What is known about the theory of natural numbers with only 0, successor and max?

This theory is equivalent to the theory of a discrete linear order with a least element and no largest element, that is, the theory of $\langle\mathbb{N},<\rangle$. From max we can define the order ...

### 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 ...
• 45.7k

### How is it possible for PA+¬Con(PA) to be consistent?

As is being discussed in the comments, the non-standard proofs in non-standard models of $\mathsf{PA}$ are not trustworthy (in that they're not sound). I'll give a sort of 'toy model' illustrating the ...
• 10.4k
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 ...
• 20.6k
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 ...
• 20.6k
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 ...
• 45.7k

### 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 ...
• 141k

### 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: ...
• 6,365

### 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. ...
• 80.5k
Accepted

### Is there a theory between HA and PA that doesn't have Markov's rule?

$\def\prf{\mathrm{Prf}}\def\pr{\mathrm{Pr}}\def\con{\mathrm{Con}}\def\f{\ulcorner\bot\urcorner}\def\ha{\mathsf{HA}}$Let $\prf(x,y)$ be the formalized proof predicate for either HA or PA (it doesn’t ...
• 45.7k

### 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 ...
• 80.5k