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. Models of Peano arithmetic.
67
questions with no upvoted or accepted answers
14
votes
0
answers
595
views
Reverse Mathematics of Euclid's theorem
Euclid's theorem that there are infinitely many prime numbers has multiple proofs, ranging from Euclid's original theorem that constructs a new prime from a finite list of such, to Euler's proof that ...
- 33.9k
11
votes
0
answers
467
views
Which sentences are "irreducibly" self-referential over $\mathsf{PA}$?
Previously asked at MSE. Below, all sentences/formulas are in the language of arithmetic, and for simplicity we conflate numbers with numerals and sentences with Godel numbers.
Say that a sentence $\...
- 19.2k
10
votes
0
answers
158
views
Minkowski's lattice theorem in fragments of arithmetic
It is widely remarked that Minkowski's lattice theorem (or, convex body theorem) is a kind of geometrical pigeonhole principle. And it seems it should have a very elementary proof at least for convex ...
- 10.8k
9
votes
0
answers
191
views
Is there an Arithmetized Completeness theorem for intuitionistic theories?
For classical theories, Henkin's completeness proof can be arithmetized. This leads to the result that for classical theories $T$ and $S$ if $\sigma$ is a formula enumerating $S$ in $T$ then $S \leq T ...
- 481
9
votes
0
answers
196
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 ...
- 10.8k
9
votes
0
answers
320
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 ...
8
votes
0
answers
334
views
What arithmetic is interpretable in Mayberry's Euclidean set theory?
John Mayberry published what he calls a Euclidean set theory in his book The Foundations of Mathematics in the Theory of Sets. It is ZF with the axiom of infinity replaced by an axiom saying "the ...
- 10.8k
8
votes
0
answers
1k
views
What's Reeb's take on naive integers?
Georges Reeb's "claim Q" is the statement that "naive integers don't fill up $\mathbb{N}$". To anyone familiar with model theory this could easily be interpreted as the existence of nonstandard models ...
- 15.3k
8
votes
0
answers
194
views
Kripke models of $HA$
Let $K$ be a kripke model and $k$ be one of its node, then $\mathcal{M}_k$ is classical structure of $k$.
What is the strongest theory of arithmetic like $T$ such that for
every kripke model $K\...
- 1,699
7
votes
0
answers
104
views
How tightly are decidability and "induction-completeness" linked?
It is known that there are a number of expansions of the structure $\mathfrak{N}:=(\mathbb{N};+)$ which are decidable (= have computable theories); one such example is the expansion by a predicate ...
- 19.2k
7
votes
0
answers
280
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 ...
- 19.2k
7
votes
0
answers
81
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 ...
- 10.3k
7
votes
0
answers
169
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 ...
- 7,613
6
votes
0
answers
399
views
Can Set Theory be turned into Infinite Arithmetic?
The following system I'd label as "Infinite Arithmetic" is simply an endeavor to extend second order arithmetic to the infinite ordinal world, and extending with it the representation of ...
- 9,266
6
votes
0
answers
411
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 ...
- 211
6
votes
0
answers
328
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 ...
- 179
6
votes
0
answers
370
views
What is proof-theoretic ordinal of weak first-order arithmetic?
According to Wikipedia(https://en.wikipedia.org/wiki/Ordinal_analysis) and nlab(https://ncatlab.org/nlab/show/ordinal+analysis), a proof-theoretic ordinal of $\mathsf{PRA}$ is $\omega^\omega$.
...
- 178
6
votes
0
answers
106
views
When can two elementary end extensions of models of PA be uniquely amalgamated?
$\DeclareMathOperator{Cod}{Cod}$
$\DeclareMathOperator{Scl}{Scl}$
$\DeclareMathOperator{Def}{Def}$
$\DeclareMathOperator{Lt}{Lt}$
Background:
All of the background to this question can be found in ...
5
votes
0
answers
156
views
How to show that $\omega^\omega$ is well-founded in PA?
By induction on $n$ variables I can show that for any meta-natural number $n$, PA proves well-foundedness of $\omega^n$. However it is well known that PA proves well-foundedness of $\omega^\omega$ ...
- 91
5
votes
0
answers
294
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 ...
- 1,832
5
votes
0
answers
283
views
Is the two variable fragment of arithmetic, i.e., theory of ($\mathbb{N}, + ,\times$), decidable?
Any references would be appreciated. Most places only address different vocabularies (e.g. a survey of arithmetical definability by Bes).
5
votes
0
answers
124
views
Lascar strong types in fragments of arithmetic
Are Lascar strong types (definition below) in models of fragments of arithmetic always type definable? (They trivially are, in models of full induction.)
Definition Given a saturated model ${\cal M}$ ...
4
votes
0
answers
144
views
Can this theory of dyadic rationals prove that multiplying by three is the same as summing thrice?
(This question arose from a discussion with Jade Vanadium about a theory of dyadic rationals.)
Let $T$ be the 2-sorted FOL theory with sorts $ℕ,ℚ$ and constant-symbols $0,1$ and binary function-...
- 2,733
4
votes
0
answers
252
views
What is the meaning and proof of Harvey Friedman’s ultrafinite incompleteness sentence?
On page 7 of his paper “Adventures in Incompleteness”, Harvey Friedman states the following:
IN ANY LONG ENOUGH SEQUENCE $x_1,...,x_n$ FROM $\{1,2,3\}$, SOME $(x_i,...,x_{2i})$ IS A SUBSEQUENCE OF ...
- 4,529
4
votes
0
answers
189
views
Is there a simple proof of consistency of EA?
Let $\mathsf{EA}+\mathsf{CE}$ be elementary arithmetic with cut elimination theorem. Is there a simple (1-)consistency proof of $\mathsf{EA}$ over $\mathsf{EA}+\mathsf{CE}$? I think that a naïve ...
- 178
4
votes
0
answers
103
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(...
- 10.3k
4
votes
0
answers
505
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 ...
- 665
4
votes
0
answers
402
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 ...
- 49
4
votes
0
answers
193
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 ...
- 7,613
4
votes
0
answers
283
views
the strength of saying "each sentence of true arithmetic has a recursive proof"
Let $PA_{\omega}$ be just like $PA$ except that $PA_{\omega}$-proofs can use any number of applications of the recursive $\omega$-rule.
The recursive $\omega$-rule allows the following:
For each ...
- 449
4
votes
0
answers
217
views
Construction of model of arithmetic from an arbitrary model
Let $M$ be a non-standard model of $PA$, $a\in |M|$ be an arbitrary non-standard number and $T$ be a theory of arithmetic. We want to choose a subset $M'\subsetneq M$ such that:
$M'\models PA^-$ (or $...
- 1,699
3
votes
0
answers
198
views
Independence and truth in PA
By $\textbf{PA}$ I will mean the usual first-order Peano Arithmetic. I will denote an element of $\mathbb{N}$ by $n$, and by $[n]$ I will denote the corresponding term in the language of $\textbf{PA}$:...
- 2,733
3
votes
0
answers
198
views
Self-referential Quinean proof of Löb's Theorem
Given its relevance for Open-source game theory, Dr. Andrew Critch asks the following about provability logic:
We conjecture that Löb’s Theorem can be proven without the use of the
modal fixed point $...
- 421
3
votes
0
answers
148
views
Why is the proof of decidability of arithmetic (Theorem 2.1) in Hamkins & Lewis (2000) enough?
Recently, I was reading the paper "Infinite Time Turing Machines" by Hamkins & Lewis. And one of the first theorems (Theorem 2.1) is about decidability of arithmetic.
The proof is quite ...
- 31
3
votes
0
answers
154
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[ ...
3
votes
0
answers
138
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 ...
- 10.3k
3
votes
0
answers
189
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; ...
- 665
3
votes
0
answers
157
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, ...
- 189
3
votes
0
answers
276
views
What does second order set theory give us that is new?
There is a natural analogy between the theories PA and ZFC. See the linked question by Gro-Tsen here.
Peano arithmetic (PA) is a first order approximation to the natural numbers. As is well known, ...
- 18.2k
3
votes
0
answers
81
views
What is the relation of total functions in second order arithmetic and fast growing hierarchies?
Answer to this questions shows that fast growing hierarchies can grow arbitrarily fast for some definition of 'arbitrary'.
Can second order arithmetic define all these functions (for any ordinal) ...
- 225
3
votes
0
answers
287
views
Is the quantifier-free fragment of Robinson arithmetic essentially undecidable?
It is well known that Robinson arithmetic (Q) is undecidable, and in fact essentially undecidable. Matiyasevich's theorem implies that the quantifier-free fragment of Q is also undecidable. However, I'...
3
votes
0
answers
134
views
A conservativity result of intuitionistic set theory over arithmetic
In their 1985 paper "Arithmetic Transfinite Induction and Recursive Well-Orderings", Friedman and Ščedrov prove that the theory $\mathbf{ZFI}$ is conservative over $\mathbf{HA}^*$ (see here, Theorem ...
- 345
3
votes
0
answers
187
views
What is the known weakest axiom system has Löb's derivability conditions?
We know that Peano Arithmetic satisfies Löb's derivability conditions, which is required in the proof of Gödel's 2nd incompleteness theorem. Is this the best result? If not, is there any known weaker ...
- 759
3
votes
0
answers
318
views
Peano (Dedekind) categoricity
What is the smallest fragment of second order logic such that $Th(\mathbb{N})$ in that logic is categorical (only one model, namely natural numbers, up to isomorphism). For example, can we do this in ...
3
votes
0
answers
340
views
example just slightly better than the greedy construction
Roth's theorem provides an estimate for the largest
size of a nonaveraging subset of $\lbrace 1,2, \ldots ,n \rbrace$ (a set of integers is nonaveraging if it does not contain any nontrivial three-...
- 3,565
3
votes
0
answers
754
views
Why isn't Montgomery modular exponentiation considered for use in quantum factoring?
It is well known that modular exponentiation (the main part of an RSA operation) is computationally expensive, and as far as I understand things the technique of Montgomery modular exponentiation is ...
- 15.3k
2
votes
0
answers
68
views
Can all the strongly provable theorems of $\sf PA+\neg Con(PA)$ be captured in an effective manner through alternative kind of provability?
If we extend $\sf PA$ with the following axiom asserting its own inconsistency:
Inconsistency: $\exists x: \operatorname {Proof}_{\sf PA} (x, \ulcorner 0=1 \urcorner)$
For short denote this axiom by $\...
- 9,266
2
votes
0
answers
118
views
Can PA be acyclically complete?
Any formula $\phi$ in the first order language of arithmetic is to be called acyclic if and only if we can associate with it an acyclic undirected graph whose nodes are the variable symbols occurring ...
- 9,266
2
votes
0
answers
76
views
Which sets of natural numbers are "lambda-analytic"?
Begin with a bit of notation. Let $t = t_0, \ldots, t_d$ be a finite sequence of real numbers. Define
$$\lambda^t(x) = x^{t_0} \log(x)^{t_1} \log(\log(x))^{t_2} \cdots.$$
for all real numbers $x \in ...
- 13.1k
2
votes
0
answers
128
views
Can we extend the projectively extended real line with a single number that stands for division of zero by zero?
If we work within $\hat{\mathbb R} = \mathbb R \cup \{\infty\}$, i.e. one point compactification of the real line.
We extend $<$ relation on $\mathbb R$ to $\hat <$ defined as:
$ x \ \hat{<} \...
- 9,266