All Questions
Tagged with theories-of-arithmetic computability-theory
39 questions
12
votes
0
answers
248
views
+50
Is there a decidable theory of arithmetic with a non-collapsing quantifier hierarchy?
This question is very close to this old MSE question of mine, which is still unanswered.
Is there an (ideally reasonably-natural!) expansion of the structure $(\mathbb{N};+)$ in a finite language ...
- 20.7k
6
votes
1
answer
197
views
Is there a 1-generic degree g such that Th(D(< g)) is more complicated than true arithmetic?
I am currently reading an article titled "Embedding and Coding Below a 1-Generic Degree" by Greenberg and Montalbán(link to a free source:https://pi.math.cornell.edu/~erlkonig/Papers/...
- 893
5
votes
0
answers
109
views
Computational complexity of arithmetic sentences over classical theories
Below, I use the term "tracker" rather than "realizer" since I'm not requiring the relevant objects to be computable.
Define the relation "$f$ tracks $\varphi$" for $f:\...
- 20.7k
4
votes
1
answer
193
views
Further research on relevant realizability etc
I just read Dunn's 1979 paper Relevant Robinson's Arithmetic, and the end especially caught my interest. Following the surprising role of constant functions in collapsing "relevant Q with zero&...
- 20.7k
1
vote
0
answers
123
views
Is possibile to define transfinite sum and product recursively? [closed]
On mathstackexchange a few days ago I published the following question where I asked about "transfinite" sum and products but actually nobody answered or gave an opinion with a comment: thus ...
4
votes
1
answer
155
views
Does this hierarchy of fragments of $I \Sigma_1$ collapse?
Does anyone know whether the following hierarchy of fragments of
$\mathrm{I} \Sigma_1$ (or rather
$\mathrm{I} \Pi_1$) collapses or not?
Let $\Sigma^b_n$ denote formulas in the language of arithmetic ...
4
votes
1
answer
258
views
What is the theory of statements with a provably *bounded* realizer (according to PA)?
$\let\T\mathrm\def\kr{\mathrel{\mathbf r}}$This is a follow up to Kleene realizability in Peano arithmetic.
We can summarize the results from Emil Jeřábek's answer as follows:
\begin{gather*}
T_1 = \{ ...
- 6,403
3
votes
1
answer
123
views
Kleene normal form theorem for r.e. relations proven in arithmetical theories
After reading the relevant chapters of Classical Recursion Theory (freely available from here), I have the following questions concerning Theorem II.1.10 (Normal form theorem) and Theorem IV.1.9 (...
- 31
7
votes
0
answers
110
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 ...
- 20.7k
32
votes
2
answers
3k
views
Do we expect that sufficiently large computable ordinals settle every question of arithmetic?
I came across a post by Ron Maimon on physics.SE that makes what seems to me to be a very interesting conjecture I've never seen before about what it would take to settle every question of arithmetic. ...
- 118k
4
votes
1
answer
439
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 ...
- 211
5
votes
1
answer
283
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)...
- 13.2k
5
votes
0
answers
318
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,882
1
vote
0
answers
148
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 ...
- 798
11
votes
1
answer
400
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 ...
- 4,597
4
votes
0
answers
431
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
2
votes
0
answers
237
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)....
- 18.7k
2
votes
2
answers
436
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 \...
1
vote
2
answers
267
views
The "higher topology" of countable Scott sets
Fix some computable bijection $b$ between $\omega$ and $2^{<\omega}$. For $r\in 2^\omega$, let $$[r]=\{f\in 2^\omega: \forall\sigma\prec f(b^{-1}(\sigma)\in r)\}$$ be the closed subset of Cantor ...
- 20.7k
19
votes
1
answer
748
views
What non-standard model of arithmetic does Hofstadter reference in GEB?
Following some of the coolest bits of Hofstadter's Gödel, Escher, Bach, extensions of the standard model of arithmetic are described. A ways in, the paragraph "Supernatural Addition and Multiplication"...
- 1,288
3
votes
0
answers
85
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
324
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'...
7
votes
1
answer
597
views
Can an uncountable model of Peano Arithmetic be recursive?
Can an uncountable model of Peano Arithmetic be recursive?
What does it mean for an uncountable model to be recursive? Well, we represent the elements of the model using real numbers instead of ...
- 6,403
1
vote
0
answers
205
views
Lowest Turing degree that allows a Turing machine to tell whether $\operatorname{Con}(PA)$?
Let $T$ be a given turing machine. We say that $T$ decides $\operatorname{Con}(PA)$ if $PA + \operatorname{Con}(PA) \vdash T \text { accepts}$ and $PA + \lnot \operatorname{Con}(PA) \vdash T \text { ...
- 6,403
5
votes
1
answer
195
views
Can extensions of $Q$ contradict Löb with recursive reflection?
It is an odd and arguably unacceptable situation that $PA$ does not have $\vdash_{PA}(Pr_{PA}\ulcorner A\urcorner\to A)$ for false recursive sentences $A$.
However, it is not clear to me that Löb'...
- 3,574
4
votes
0
answers
292
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
16
votes
1
answer
831
views
Can there be computable non-standard models of PA in a weaker sense?
By Tennenbaum's theorem, in the usual sense of computability for models,
neither addition nor multiplication can be computable in a countable non-standard model of PA.
Weak version:
Can addition or ...
user5810
4
votes
1
answer
245
views
Induction and nonstandard halting times of standard machines
For a nonstandard model of enough arithmetic - say, $\mathcal{N}\models I\Sigma_1$ - we can define the set of halting times of standard machines relative to $\mathcal{N}$: $$SH(\mathcal{N})=\{n\in\...
- 20.7k
0
votes
1
answer
336
views
Definability of arithmetic functions and relations
Motivation: Many "weak" arithmetic functions and/or relations ("relations" for short) are equivalent with relations explicitly definable by relations which were recursively defined by them beforehand (...
- 9,720
12
votes
1
answer
835
views
Transfinitely extending $\sf PA$ — can we get stronger than $\sf ZFC$?
Let $\sf PA$ denote the theory of natural numbers with constants $(0, 1)$ and binary operators $(+,\times)$ based on the first-order predicate calculus with equality, having the following axioms, ...
- 6,819
3
votes
3
answers
683
views
Turing Functional and $\Sigma_1^0$-formulas in models of fragments of PA
In models of PA with restricted induction power (for example, only $I\Sigma_n$ is present), the failure of higher induction scheme is characterised by the existence of definable cuts (like $\Sigma_2$ ...
- 3,038
7
votes
1
answer
198
views
A well-behaved $A$ that is almost contained in every element of some filter for a countable arithmetically closed family $\mathfrak X$
The question has relevance for constructing Scott sets with certain extra desirable properties.
Suppose that $\mathfrak X$ is a countable arithmetically closed family of subsets of $\mathbb N$: ...
- 2,240
10
votes
3
answers
618
views
If an oracle Turing machine halts with every infinite arithmetic oracle, can it fail to halt with some non-arithmetic oracle?
Let $e$ be an index of an oracle Turing machine program and $k$ be some natural number. Let us say that a subset of $\mathbb N$ is arithmetic if it is definable in the model $\langle \mathbb N,+,\cdot,...
- 2,240
3
votes
1
answer
437
views
Axiomatizations of complete theories
This question was motivated by this recent question by Ricky Demer.
In his paper $\Pi^0_1$ classes and Boolean combinations of recursively enumerable sets, Carl Jockusch showed that there is no ...
- 44.4k
18
votes
3
answers
2k
views
Is Robinson Arithmetic biinterpretable with some theory in LST?
Let ZFC$^{\text{fin}}$ be ZFC minus the axiom of infinity plus the negation of the axiom of infinity. It is well-known that ZFC$^{\text{fin}}$ is biinterpretable with Peano Arithmetic. In this sense ...
- 3,267
3
votes
1
answer
746
views
Turing degrees of nonstandard models of PA
Since the theorems of (PA + "there is a nonstandard number") are recursively enumerable, by the
Low Basis Theorem, WKL0's proof of the completeness theorem gives a nonstandard model of PA of [low ...
user5810
18
votes
3
answers
1k
views
Computable nonstandard models for weak systems of arithmetic
By Tennenbaum's theorem, PA itself does not have any computable nonstandard models. The integer polynomials which are 0 or have a positive leading coefficient form a computable nonstandard model of ...
user5810
16
votes
3
answers
19k
views
Non-computable but easily described arithmetical functions
I have read about the existence of functions of the kind described in the title in several places, but never seen an instance of them. Sorry if this is too much an elementary question to be posted ...
- 1,465
17
votes
7
answers
2k
views
Non-constructive proofs of decidability?
Are there examples of sets of natural numbers that are proven to be decidable but by non-constructive proofs only?