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 ...
- 230k
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 ...
- 45.7k
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 ...
- 10.4k
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 ...
- 20.7k
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 ...
- 20.7k
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 ...
- 45.7k
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 ...
- 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: ...
- 6,365
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.
...
- 80.3k
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 ...
- 45.7k
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 $(\...
- 1,659
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 ...
- 230k
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,...
- 230k
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 ...
- 80.3k
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 ...
- 230k
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{\...
- 230k
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), ...
- 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 ...
- 45.7k
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 ...
- 230k
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 ...
- 230k
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 ...
- 116k
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 ...
- 230k
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 ...
- 2,097
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 ...
- 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 ...
- 230k
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.4k
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) ...
- 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 : ...
- 80.3k
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 ...
- 19.6k
Only top scored, non community-wiki answers of a minimum length are eligible