All Questions
Tagged with theories-of-arithmetic computability-theory
11 questions with no upvoted or accepted answers
12
votes
0
answers
249
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
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
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
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
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
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
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'...
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
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
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