36
votes

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

27
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 ...

26
votes

### 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 ...

24
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 ...

24
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 ...

21
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 ...

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

21
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.
...

17
votes

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

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

16
votes

### Con(PA) via non-well-foundedness?

This is a completely standard perspective in work on models-of-PA, a view that informs dozens of arguments. That is simply the nature of nonstandard models, that things they think are well founded are ...

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

### 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 ...

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

14
votes

Accepted

### Extensions of $PA+\neg Con(PA)$ with large consistency strength

Let $T$ be the theory PA + ¬Con(PA), plus the axiom asserting that there is no proof of a contradiction in ZFC (or ZFC+LC etc.) of size below $k$, where $k$ is the smallest such that $\newcommand\PA{\...

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

13
votes

Accepted

### Analysis I, simpler proof of Tao's construction of the integers

In fact one doesn't need the replacement axiom at all in order to implement this set-theoretic construction of the integers. The entire construction can be undertaken in Zermelo set theory, which ...

12
votes

Accepted

### Is there a useful measure of density of decidable sentences in PA?

Asymptotic density seems a very natural measure. The density of a set of sentences is the limit as $n\to\infty$ of the proportion of those sentences of length at most $n$ amongst all sentences of ...

12
votes

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

In the proof of the completeness theorem guaranteeing that a consistent theory like $PA + \neg \text{Con}(PA)$ has a model, roughly (as I understand it) the model construction process adjoins a ...

11
votes

Accepted

### Can the "real" Peano Arithmetic be inconsistent?

It seems that the Feferman-style description of PA will exhibit your requirements.
Specifically, consider the theory $P$ defined as follows. Begin to enumerate the usual PA axioms, but include the ...

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

11
votes

Accepted

### Can singular long models require less than PA?

The answer to the question is strongly in the positive, since the following theorem of Kaye implies that for every singular cardinal $\kappa$, and for any fixed natural number $n$, the common theory ...

11
votes

Accepted

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

Because your argument involves arithmetical classes at several points, as you noticed, it is not directly expressible in the first-order language of $\newcommand\PA{\text{PA}}\PA$, although as Noah ...

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) ...

10
votes

### In what sense does the sentence $\operatorname{con}(\mathsf{PA})$ "say" that $\mathsf{PA}$ is consistent?

There is really nothing peculiar about Con(PA) in this regard. Let's take a simpler statement, such as
$$(\exists x \exists y \exists z : xxx + yyy - zzz = 114) \vee (\exists x \exists y \exists z : ...

10
votes

Accepted

### In what sense does the sentence $\operatorname{con}(\mathsf{PA})$ "say" that $\mathsf{PA}$ is consistent?

The PA sentence “$\newcommand{\Con}{\text{Con}}\Con(\newcommand{\PA}{\text{PA}}\PA)$” says that PA is consistent in exactly the same ways that the PA sentences representing, say, the fundamental ...

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

#### Related Tags

theories-of-arithmetic × 324lo.logic × 258

set-theory × 76

model-theory × 70

proof-theory × 42

computability-theory × 37

reference-request × 22

reverse-math × 22

nt.number-theory × 20

foundations × 14

ordinal-analysis × 12

ultrafinitism × 12

mathematical-philosophy × 11

metamathematics × 9

ordinal-numbers × 8

decidability × 8

computational-complexity × 7

ac.commutative-algebra × 6

constructive-mathematics × 6

induction × 6

bounded-arithmetic × 6

soft-question × 5

forcing × 5

nonstandard-analysis × 5

definability × 5