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 ...
- 41.6k
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 ...
- 19.1k
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 ...
- 41.6k
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 ...
- 19.1k
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 ...
- 125k
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: ...
- 5,507
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.
...
- 72.5k
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,599
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,...
- 208k
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 ...
- 208k
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 ...
- 72.5k
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), ...
- 15.7k
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 ...
- 41.6k
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 ...
- 1,847
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 ...
- 8,036
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,646
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 $\...
- 15.7k
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 [...
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 ...
- 41.6k
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 ...
- 208k
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 ...
- 41.6k
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 ...
- 208k
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 ...
- 43.1k
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 ...
- 711
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 ...
- 15.7k
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\...
- 19.1k
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 ...
- 19.1k
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