6
$\begingroup$

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/below1generic.pdf). At the end of section 3 in the paper they mention a few questions left without answer, one of them being: Is there a 1-generic degree g such that Th(D(< g)) is more complicated than true arithmetic? Where Th(D(< g)) is the theory of turing degrees below the degree of the 1-generic.

My question is, has there been any resolution/progress on this question given that it was posed 20 years ago?

$\endgroup$

1 Answer 1

6
$\begingroup$

If $g$ is the Turing degree of an arithmetically generic set, then the first order theory of $D(<g)$ is decided by forcing. For Cohen forcing, the forcing relation for an arithmetic sentence is arithmetically definable. So, in the case of a arithmetically generic $g$, the theory of $D(<g)$ is computable from $0^\omega.$

This need not be the case when $g$ is the Turing degree of a set that is 1-generic but not necessarily fully generic. Consider a 2-generic $g$ such that $0^\omega$ is recursive in $g''$.

One can construct a representative $G$ of such a $g$ by recursion: alternate between (1) meeting the dense sets required for 2-genericity and (2) coding the bits of $0^\omega.$ In other words, follow Friedberg's jump inversion construction, but for the double jump instead of the jump.

For such $G$, the structure $(N,G),$ first order arithmetic with an additional unary predicate for $G$, can define $0^\omega$ as follows. As $0^\omega$ is a $\Pi^0_2$-singleton, let $\Theta$ be a $\Pi^0_2$ formula such that for any $X\subset\omega$, $\Theta(X)$ is true if and only if $X=0^\omega$. Then, $n\in 0^\omega$ if and only if $(N,G)$ satisfies the statement "There exists an $e$ such that $\Phi_e(G'')$ satisfies $\Theta$ and $n\in\Phi_e(G'').$" Here, $\Phi_e$ denotes the partial recursive functional with index $e$.

According to Greenberg and Montalban, since $g$ is 2-generic, there is a definable family of codings of the standard model of arithmetic within $D(<g)$. The same proof shows that there is a definable family of codings of the standard model of arithmetic with an additional predicate such that for at least one of these coded structures, the additional predicate is for a representative $G$ of $g$. Then, the theory of $D(<g)$ can compute whether $n\in 0^\omega$ by checking whether there is a coded standard model $(N,G)$ such that $(N,G)$ satisfies "There exists an $e$ such that $\Phi_e(G'')$ satisfies $\Theta$ and $n\in\Phi_e(G'').$"

Since the Turing degrees of the $\Pi^0_2$-singletons are cofinal among the Turing degrees of the hyperarithmetical sets, the degrees of $Th(D(<g),$ for $g$ 1-generic, are similarly cofinal among the Turing degrees of the hyperarithmetical sets.

$\endgroup$
1
  • $\begingroup$ Very well structured answer, thank you. $\endgroup$
    – H.C Manu
    Commented Aug 13 at 10:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .