All Questions
34 questions
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
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 ...
- 16.6k
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/...
- 1,780
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&...
- 1,094
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 ...
- 47.8k
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 = \{ ...
- 12.9k
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 (...
- 17.7k
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 ...
- 18.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
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. ...
- 7,545
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)...
- 5,831
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 ...
- 63.9k
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 ...
- 20.7k
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"...
- 24.8k
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 ...
- 4,727
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'...
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
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?
- 53
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'...
- 47.8k
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 ...
- 47.8k
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\...
- 44.4k
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, ...
- 20.7k
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$ ...
- 229
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,...
- 237k
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 ...
CommunityBot
- 1
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 ...
CommunityBot
- 1