A real is called properly n-generic if it is n-generic but not n+1-generic. We show that every 1-generic real computes a properly 1-generic real. On the other hand, if m > n ≥ 2 then an m-generic real cannot compute a properly n-generic real.
A set X is prime bounding if for every complete atomic decidable (CAD) theory T there is a prime model U of T decidable in X. It is easy to see that $X = 0\prime$ is prime bounding. Denisov claimed that every $X <_{T} 0\prime$ is not prime bounding, but we discovered this to be incorrect. Here we give the correct characterization that the prime bounding sets $X \leq_{T} 0\prime$ are exactly the sets which are not $low_2$ . Recall that (...) X is $low_2$ if $X\prime\prime$ $\leq_{T} 0\prime$ . To prove that a $low_2$ set X is not prime bounding we use a $0\prime$ -computable listing of the array of sets { Y : Y $\leq_{T}$ X } to build a CAD theory T which diagonalizes against all potential X-decidable prime models U of T. To prove that any $non-low_{2}$ ; X is indeed prime bounding, we fix a function f $\leq_T$ X that is not dominated by a certain $0\prime$ -computable function that picks out generators of principal types. Given a CAD theory T. we use f to eventually find, for every formula $\varphi (\bar{x})$ consistent with T, a principal type which contains it, and hence to build an X-decidable prime model of T. We prove the prime bounding property equivalent to several other combinatorial properties, including some related to the limitwise monotonic functions which have been introduced elsewhere in computable model theory. (shrink)
Cholak, Goncharov, Khoussainov, and Shore [1] showed that for each k > 0 there is a computably categorical structure whose expansion by a constant has computable dimension k. We show that the same is true with k replaced by ω. Our proof uses a version of Goncharov's method of left and right operations.
We give some new examples of possible degree spectra of invariant relations on Δ 0 2 -categorical computable structures, which demonstrate that such spectra can be fairly complicated. On the other hand, we show that there are nontrivial restrictions on the sets of degrees that can be realized as degree spectra of such relations. In particular, we give a sufficient condition for a relation to have infinite degree spectrum that implies that every invariant computable relation on a Δ 0 2 (...) -categorical computable structure is either intrinsically computable or has infinite degree spectrum. This condition also allows us to use the proof of a result of Moses [23] to establish the same result for computable relations on computable linear orderings. We also place our results in the context of the study of what types of degree-theoretic constructions can be carried out within the degree spectrum of a relation on a computable structure, given some restrictions on the relation or the structure. From this point of view we consider the cases of Δ 0 2 -categorical structures, linear orderings, and 1-decidable structures, in the last case using the proof of a result of Ash and Nerode [3] to extend results of Harizanov [14]. (shrink)
We construct the set of the title, answering a question of Cholak, Jockusch, and Slaman [1], and discuss its connections with the study of the proof-theoretic strength and effective content of versions of Ramsey's Theorem. In particular, our result implies that every ω-model of RCA 0 + SRT 2 2 must contain a nonlow set.
We show that for every c.e. degree a > 0 there exists an intrinsically c.e. relation on the domain of a computable structure whose degree spectrum is {0, a}. This result can be extended in two directions. First we show that for every uniformly c.e. collection of sets S there exists an intrinsically c.e. relation on the domain of a computable structure whose degree spectrum is the set of degrees of elements of S. Then we show that if α ∈ (...) ω∪{ω } then for any α-c.e. degree a > 0 there exists an intrinsically α-c.e. relation on the domain of a computable structure whose degree spectrum is {0, a}. All of these results also hold for m-degree spectra of relations. (shrink)
