3
votes
3answers
163 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$ ...
6
votes
1answer
151 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$: ...
8
votes
3answers
256 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 ...
3
votes
1answer
354 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 ...
3
votes
1answer
447 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 ...
13
votes
6answers
967 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?