# Questions tagged [theories-of-arithmetic]

Theories of arithmetic in first-order logic, such as Peano arithmetic, second-order arithmetic, Heyting arithmetic, and their subsystems and extensions.

247
questions

**2**

votes

**0**answers

274 views

### Alternative proof of Tennenbaum's theorem

The standard proof of Tennenbaums's theorem uses the existence of recursively enumerable inseparable sets and is presented e.g. in Kaye [1, 2], Smith [3].
In the following, $\mathcal{M}$ will always ...

**5**

votes

**1**answer

191 views

### Which arithmetical sentences have no counterexamples in the sense of Kreisel?

It is a well-known fact that given a first-order sentence $\psi$ in prenex normal form $\forall x_1 \exists y_1 \forall x_2 \exists y_2 \dots \forall x_n \exists y_n \theta(x_1,\dots,x_n,y_1,\dots,y_n)...

**12**

votes

**0**answers

336 views

### Are there signatures escaping from Tennenbaum's Theorem?

By Tennenbaum's Theorem all recursive models of $\mathsf{PA}$ are isomorphic to the standard model. And by a result of Wilmer this holds even for models of the theory $\mathsf{IE}_1\subseteq \mathsf{I}...

**2**

votes

**1**answer

103 views

### Representation of the equality relation between hereditarily finite sets in weak set theories

Consider General Set Theory ($ \mathsf { GST } $) axiomatized by the following.
Axiom of Extensionality: The sets $ x $ and $ y $ are the same set if they have the same members:
$$ \forall x \forall ...

**3**

votes

**1**answer

259 views

### Does ACA prove categoricity of the reals?

$\def\f#1{\text{#1}}$Does $\f{ACA}$ prove that any two internally complete ordered fields are isomorphic?
Here internal completeness is expressed roughly as "every sequence of reals with an upper ...

**7**

votes

**0**answers

266 views

### Generic behavior of "polynomialish" models of $\mathsf{Q}$

(This question was originally asked and bountied at MSE - with different notation, some more explicit arguments, and topology in place of forcing.)
Suppose $\mathcal{R}=(R_i)_{i\in\mathbb{N}}$ is a ...

**4**

votes

**0**answers

184 views

### $\Sigma_n$-complete sets in the Levy hierarchy

Recall that a set $A \subseteq \mathbb N$ is (many-one, Turing) $\Sigma_n$-complete if it's $\Sigma_n$ and any other $\Sigma_n$ set (many-one, Turing) reduces to it. This definition actually makes ...

**4**

votes

**0**answers

92 views

### Computably saturated Skolem hulls of Morley sequences in $\mathsf{PA}$

Recall that a model $M$ of a first-order theory $T$ (in a computable language $\mathcal{L}$) is computably saturated if for every finite tuple $\bar{a} \in M$ and every computable partial type $\Sigma(...

**0**

votes

**1**answer

233 views

### What is the smallest countable limit ordinal in which 'lost melodies' occur

The question is in the title. This question is in response to the following paragraph found at the end of Prof. Hamkins' answer to my MathOverflow question, Are ITTM's necessary to compute Turing's &...

**6**

votes

**0**answers

177 views

### Can this weakish system of arithmetic express multiplication for second-sort numbers?

Consider a 2-sorted first-order logic with equality (for first-sort entities). The first sort consists of numbers, the second sort (which will be capitalized) of unary functions. There is one constant,...

**7**

votes

**0**answers

68 views

### How similar can a model of $I\Delta_0$ be to the intersection of all of its definable cuts?

Let $M$ be a model of $I\Delta_0$. Recall that a definable cut is a definable (possibly with parameters) subset $I$ of $M$ that is non-empty, downwards closed, and closed under successor.
If we ...

**3**

votes

**0**answers

132 views

### Is anything known about $\Delta_n$ bounding?

For a class $\Gamma \in \{ \Sigma_n, \Pi_n, \Delta_n \}$ in the arithmetical hierarchy, we can consider the induction, bounding, and least number principles for $\Gamma$:
$\mathsf{I}\Gamma$ is $\big[ ...

**1**

vote

**1**answer

148 views

### Can $\mathsf{RCA}_0$ prove that every nonempty c.e. set $A \subseteq \mathbb{N}$ has a least element?

In other words, can $\mathsf{RCA}_0$ prove that for every function $f\colon \mathbb{N} \to \mathbb{N}$, there is $b \in \mathbb{N}$ such that
$$ \exists k \in \mathbb{N},\ f(k) = b\quad \land\quad \...

**3**

votes

**0**answers

104 views

### Does Robinson arithmetic interpret a Kripke model of the double negation translation of $\mathsf{I}\Delta_0 + \mathrm{Exp}$?

It is a well-known fact that while while Robinson arithmetic can interpret surprisingly strong theories, it cannot interpret $\mathsf{I}\Delta_0 + \mathrm{Exp}$, i.e., Peano arithmetic with induction ...

**6**

votes

**0**answers

330 views

### Proof of Tennenbaum's Theorem by McCarty

Tennenbaum's Theorem in its usual form states that for any countable non-standard model $M$ of PA there is no way to code the elements of $M$ as natural numbers such that either the addition or ...

**12**

votes

**1**answer

258 views

### What is the proof-theoretic ordinal of bare $\mathsf{NFU}$?

On the Stanford Encyclopedia of Philosophy article on alternative axiomatic set theories, it is stated without reference that bare $\mathsf{NFU}$ (i.e., $\mathsf{NFU}$ without the axiom of infinity) ...

**3**

votes

**1**answer

117 views

### Consistency and consistency strength of certain special cuts in $I\Delta_0$

Recall that $I\Delta_0$ is the theory in the language of arithmetic that consists of the axioms of $\mathsf{PA}$ with induction restricted to $\Delta_0$ formulas (i.e., formulas where all quantifiers ...

**1**

vote

**0**answers

106 views

### Why doesn't $\mathsf{B}\Sigma_2$ hold in $\mathsf{RCA}_0$?

For a formula $\varphi(i,u)$ of arithmetic, the bounding principle for $\varphi$ is the statement
$$\forall m \, \Big( \big( \forall i<m\ \exists u\ \varphi(i,u) \big) \to \big( \exists v\ \forall ...

**10**

votes

**1**answer

316 views

### What is the Turing degree of the monadic theory of the real line?

The monadic theory of the real line is the set of all sentences in the monadic second-order language of order which are true in $\mathbb{R}$. In this 1982 paper, Gurevich and Shelah show that true ...

**14**

votes

**2**answers

619 views

### How special is first-order $\mathsf{PA}$?

This is a modified version of a question which was asked and bountied at MSE without success.
Below, "$\mathsf{PA}$" refers to first-order Peano arithmetic.
There are various "...

**5**

votes

**1**answer

180 views

### Can a nonstandard model of $\mathsf{PA}$ be "$\Delta^1_1$-well-ordered?"

This was asked and bountied at MSE with no response:
My question is the following:
Is there a nonstandard model $\mathcal{M}\models\mathsf{PA}$ such that $\mathcal{M}$ has no $\Delta^1_1$-with-...

**8**

votes

**1**answer

220 views

### Paris-Harrington principles parametrized by functions $f:\mathbb N \to \mathbb N$

Recall that the Paris-Harrington Principle, $\mathsf{PH}$, is the statement that for each $e, r, k < \omega$ there is an $N < \omega$ so that given any coloring $c:[N]^e \to r$ there is an $H \...

**9**

votes

**1**answer

299 views

### What can $I\Delta_0$ prove?

What combinatorial and number-theoretic propositions can $I\Delta_0$ prove? Obviously there are an infinitude of them, but what are some well known theorems that can be proved in $I\Delta_0$, if any?

**8**

votes

**0**answers

168 views

### Reverse mathematics of Noetherian rings over $\mathbb{Q}$

Take the Hilbert Basis Theorem over the rational numbers in this form in the language of Second Order Arithmetic: For every $n\in N$ every ideal of the polynomial ring $\mathbb{Q}[x_1,\dots,x_n]$ is ...

**13**

votes

**3**answers

2k views

### Did Edward Nelson accept the incompleteness theorems?

Edward Nelson advocated weak versions of arithmetic (called predicative arithmetic) that couldn't prove the totality of exponentiation. Since his theory extends Robinson arithmetic, the incompleteness ...

**4**

votes

**0**answers

350 views

### Can Robinson arithmetic prove any interesting theorems?

The motivation for my question is I'm curious whether studying Robinson arithmetic can be fruitful in the same sense as studying group theory. Robinson arithmetic is so weak that there are many ...

**5**

votes

**0**answers

323 views

### Is $\mathsf{R}$ axiomatizable by finitely many schemes?

Recall that $\mathsf{R}$ is the theory of arithmetic consisting of the quantifier-free theory of $(\mathbb{N};+,\times,0,1,<)$ together with, for each $k\in\mathbb{N}$, the sentence $$\forall x[(\...

**3**

votes

**0**answers

177 views

### Set theories that are complete modulo finite-order arithmetic

In a previous question, I asked whether there can be effectively axiomatizable set theories (at least as strong as, say, ZF) that are complete modulo first-order arithmetic, to which the answer is no; ...

**4**

votes

**0**answers

239 views

### How can I prove that primitive recursion “preserves” representability in Peano Arithmetic?

I'm working on my thesis about Gödel's Incompleteness Theorems, and at some point I need to prove that the $\textsf{PA}$ system is able to represent all the recursive functions.
By recursive function ...

**3**

votes

**0**answers

90 views

### Interpretability of primitive recursive functions in Peano Arithmetic

Let $R$ be a set of defining equations for primitive recursive functions successively built up from $s, +, \cdot$.
Is PA + $R$ interpretable in PA? (Interpretability understood in the sense of Tarski, ...

**6**

votes

**0**answers

293 views

### Nelson's contradiction in finitism

I have read up, in Shoenfield and elsewhere, on a lot of the details involved in Nelson's failed proof of the inconsistency of arithmetic. I understand the Kritchman-Raz proof; the proof of the ...

**1**

vote

**0**answers

88 views

### Formalization in PA in the Kritchman-Raz proof

In their paper Kritchman and Raz present a proof of Gödel's second theorem using Kolmogorov complexity. To make it work, they operate in some (weak) formal theory $T$ that incorporates some arithmetic,...

**-1**

votes

**2**answers

436 views

### Peano axioms— mathematical induction and other axioms

The Peano axioms of $\Bbb N$ are:
$1 \in \Bbb N$, i.e. $\Bbb N$ is not empty and contains an element denoted by $1$.
Every natural number has a successor, i.e. $\forall n\in\Bbb N, \exists!s(n)\in\...

**2**

votes

**0**answers

162 views

### Representing iteration of a function in PA

Let $\mathscr{L}$ be a (recursive) FOL language, with numeral symbols $\underline{0},\underline{1},\ldots$. Let $T$ be a recursive, consistent theory, containing PA (or even just Robinson arithmetic)....

**4**

votes

**0**answers

287 views

### Iterated Gentzen: or, a Sith objection to the proof of consistency of PA

$\DeclareMathOperator\PRA{PRA}\DeclareMathOperator\WF{WF}\DeclareMathOperator\Con{Con}\DeclareMathOperator\PA{PA}$Preamble: In the year … in a galaxy far far away, a nasty Sith named Darth Dubious (...

**9**

votes

**1**answer

288 views

### An internalized version of Tennenbaum's Theorem

Tennenbaum's celebrated 1959 theorem (see here for a reference) is certainly one of the key theorems in mathematical logic. Not so much for its proof, but because it helps "isolating" $N$ ...

**1**

vote

**1**answer

216 views

### Complete and consistent first-order theories that contain interesting phenomena

Gödel has shown that a consistent recursively axiomatizable first-order theory that can interpret Robinson arithmetic is incomplete.
I think there is some sentimental value in working with a theory ...

**10**

votes

**1**answer

267 views

### Concrete examples of statements not provable in PRA + $\epsilon_0$-induction that are provable in PA?

It is well-known that $\mathbf{PRA}$ plus $\epsilon_0$-induction on bounded formulas cannot prove all $\mathbf{PA}$ theorems (essentially because $I\Sigma_1$ plus $\epsilon_0$-induction on bounded ...

**5**

votes

**3**answers

1k views

### Are there first-order statements that second order PA proves that first order PA does not?

Are there first-order statements that second order PA proves that first order PA does not? Is this known one way or the other? Could you share an example? (edit: to clarify, by 'second order PA' I don'...

**4**

votes

**0**answers

162 views

### The Return of Graham Arithmetics: adding induction up to $g_{64}$

In my previous question The inconsistency of Graham Arithmetics plus $ \forall n, n < g_{64}$, I introduced an extension of Robinson Arithmetics with the recursive definition of Tetraction, a small ...

**9**

votes

**0**answers

307 views

### Is there a definable model of PA whose domain is a proper class and whose complete theory is not definable?

Assume ZFC. Is there a formula of $\mathcal{L}_\in$ (without parameters) defining a model $\mathcal{M}$ of PA whose domain is a proper class but the complete theory of that model is not definable by ...

**12**

votes

**2**answers

731 views

### The inconsistency of Graham Arithmetics plus $ \forall n, n < g_{64}$

As you all know, Ronald Graham just passed away. He is famous for many fabulous contributions to finite combinatorics, and much much more, but perhaps none of them is as popular as the infamous ...

**6**

votes

**0**answers

139 views

### The provability logic of $I\Delta_0+\Omega_1 $ and complexity theory

Almost 30 years ago, a number of folks in provability logic tried to show that GL (see for instance the excellent survey by Rineke Verbrugge here) is indeed the logic of $I\Delta_0+\Omega_1$ (in the ...

**9**

votes

**1**answer

714 views

### Why can't we embed Tarski's truth in PA?

I recently learned that ZFC can prove $Con(PA)$ because it can give a model of PA, but I'm not given the technical details. (My teacher thinks it is too obvious to even mention.)
What plagues me is ...

**4**

votes

**1**answer

280 views

### Lob theorem for Robinson arithmetic

If i'm not wrong, the theory which Lob theorem applies to should be sufficiently strong, satisfying 3 "derivability" conditions, like PA.
$Q$ is the Robinson arithmetic.
I'm afraid $Q$, is ...

**2**

votes

**2**answers

335 views

### Is there any reasonable non-regular Gödel numbering of the language of arithmetic?

Let $\mathcal{L}$ be the language of arithmetic given as follows:
$x::= {\sf v} \mid x'$
$t ::= x \mid 0 \mid {\sf S}t \mid (t+t) \mid (t\times t)$
$A ::= \bot \mid \top \mid t=t \mid \neg A \mid (A \...

**52**

votes

**1**answer

2k views

### In the two-person Killing the Hydra game, what is the winning strategy?

My question is which player has a winning strategy in the
two-player version of the Killing the Hydra game?
In their amazing paper,
Kirby, Laurie; Paris, Jeff, Accessible independence results for ...

**7**

votes

**1**answer

359 views

### Natural $\Pi_1$ sentence independent of PA

Order invariant graphs and finite incompleteness by Harvey Friedman gives an example of a combinatorial/non-metamathematical $\Pi_1$ sentence that is independent of ZFC. Is there a simpler example of ...

**2**

votes

**0**answers

126 views

### Definability in countable nonstandard models of Peano arithmetic

I know that every element of $\mathbb{N}$ is definable the standard model of Peano Arithmetic. Does there exist a countable non-standard model of PA where the same is true?

**11**

votes

**2**answers

1k views

### Could Kronecker accept a proof of Goodstein's theorem?

A famous result of Goodstein asserts that the Goodstein sequence of integers terminates.
For a precise statement and a short proof, see https://en.wikipedia.org/wiki/Goodstein%27s_theorem.
A well ...