Embedding jump upper semilattices into the Turing degrees
Journal of Symbolic Logic 68 (3):989-1014 (2003)
| Abstract | We prove that every countable jump upper semilattice can be embedded in D, where a jump upper semilattice (jusl) is an upper semilattice endowed with a strictly increasing and monotone unary operator that we call jump, and D is the jusl of Turing degrees. As a corollary we get that the existential theory of $\langle D, \leq_{T}, \vee, '\rangle$ is decidable. We also prove that this result is not true about jusls with 0, by proving that not every quantifier free 1-type of jusl with 0 is realized in D. On the other hand, we show that every quantifier free 1-type of jump partial ordering (jpo) with 0 is realized in D. Moreover, we show that if every quantifier free type, $p(x_{1},..., x_{n})$ , of jpo with 0, which contains the formula $x_{1} \leq 0{^(m)} \& ... \& x_{n} \leq 0^{(m)}$ for some m, is realized in D, then every quantifier free type of jpo with 0 is realized in D. We also study the question of whether every jusl with the c.p.p. and size $\kappa \leq 2^{\aleph 0}$ is embeddable in D. We show that for $\kappa = 2^{\aleph 0}$ the answer is no, and that for κ = ℵ1 it is independent of ZFC. (It is true if $MA(\kappa)$ holds.) | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,672 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesSteffen Lempp & Manuel Lerman (1992). The Existential Theory of the Poset of R.E. Degrees with a Predicate for Single Jump Reducibility. Journal of Symbolic Logic 57 (3):1120-1130.
Hisato Muraki (1999). Non-Distributive Upper Semilattice of Kleene Degrees. Journal of Symbolic Logic 64 (1):147-158.
Guohua Wu (2006). Jump Operator and Yates Degrees. Journal of Symbolic Logic 71 (1):252 - 264.
Richard A. Shore (2007). Local Definitions in Degeree Structures: The Turing Jump, Hyperdegrees and Beyond. Bulletin of Symbolic Logic 13 (2):226-239.
Paolo Casalegno (1985). On the T-Degrees of Partial Functions. Journal of Symbolic Logic 50 (3):580-588.
Harold T. Hodes (1982). Jumping to a Uniform Upper Bound. Proceedings of the American Mathematical Society 85 (4):600-602.
Harold T. Hodes (1981). Upper Bounds on Locally Countable Admissible Initial Segments of a Turing Degree Hierarchy. Journal of Symbolic Logic 46 (4):753-760.
P. D. Welch (2000). Eventually Infinite Time Turing Machine Degrees: Infinite Time Decidable Reals. Journal of Symbolic Logic 65 (3):1193-1203.
Harold T. Hodes (1983). More About Uniform Upper Bounds on Ideals of Turing Degrees. Journal of Symbolic Logic 48 (2):441-457.
Antonio Montalb�N. (2003). Embedding Jump Upper Semilattices Into the Turing Degrees. Journal of Symbolic Logic 68 (3): 989-1014.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2009-01-28Total downloads0Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
