Skip to main content
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 ...
Joel David Hamkins's user avatar
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 ...
Emil Jeřábek's user avatar
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 ...
James E Hanson's user avatar
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 ...
Noah Schweber's user avatar
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 ...
Noah Schweber's user avatar
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 ...
Emil Jeřábek's user avatar
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 ...
Will Sawin's user avatar
  • 141k
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: ...
Dmytro Taranovsky's user avatar
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. ...
Timothy Chow's user avatar
  • 80.5k
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 ...
Emil Jeřábek's user avatar
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 $(\...
Erik Walsberg's user avatar
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 ...
Joel David Hamkins's user avatar
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,...
Joel David Hamkins's user avatar
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 ...
Timothy Chow's user avatar
  • 80.5k
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 ...
Joel David Hamkins's user avatar
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{\...
Joel David Hamkins's user avatar
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), ...
Ali Enayat's user avatar
  • 17.3k
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 ...
Emil Jeřábek's user avatar
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 ...
Joel David Hamkins's user avatar
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 ...
Joel David Hamkins's user avatar
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 ...
Qiaochu Yuan's user avatar
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 ...
Joel David Hamkins's user avatar
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 ...
Kameryn Williams's user avatar
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 ...
Ali Enayat's user avatar
  • 17.3k
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 ...
Joel David Hamkins's user avatar
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 ...
James E Hanson's user avatar
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) ...
abo's user avatar
  • 1,926
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 : ...
Timothy Chow's user avatar
  • 80.5k
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 ...
Peter LeFanu Lumsdaine's user avatar

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