Possible Turing degrees of countable models of ZFC

161 Views Asked by At

Let $M$ be a countable model in a signature $\Sigma$. We assume $\Sigma$ is finite, and (for convenience) has no function or constant symbols.

Without loss of generality, we can assume that $M$'s object set is a subset of the natural numbers. We can then ask about the Turing degree of $M$'s object set, as a set of natural numbers. Furthermore, for each $n$-ary relation $R$ in $\Sigma$, we can ask about the Turing degree of $M$'s interpretation of $R$ (considered as a subset of $\mathbb{N}$ , where $n$-tuples of natural numbers (objects of $M$) have been coded as single natural numbers). We then define the "Turing degree of $M$" to be the least upper bound of the degree of its object set and the degrees of all of its relations.

Question: If ZFC has a model, does it have a countable model whose Turing degree is bounded by $\emptyset^{(n)}$ for some finite $n$?

1

There are 1 best solutions below

0
On BEST ANSWER

Yes, and that we are considering $\mathsf{ZFC}$ is not really relevant (except that for $\mathsf{ZFC}$ we know we do not have a recursive model):

If $T$ is a consistent theory with an r.e. axiomatization, we can carry out the argument of Henkin's proof of the completeness theorem for $T$, and obtain a $\Delta^0_2$ model of $T$ whose universe is a recursive set of numbers.

(I do not know who this result is due to, maybe Hartley Rogers, Jr., who mentions it as exercise 14.11 in page 332 of his book Theory of recursive functions and effective computability.)