Embedding lattices in the Kleene degrees

ArticleOriginal scientific text

Title

Authors ¹

Department of Mathematics, Nagoya University, Chikusa-ku, Nagoya 464-8602, Japan

Under ZFC+CH, we prove that some lattices whose cardinalities do not exceed

ℵ_{1}

can be embedded in some local structures of Kleene degrees.

K. J. Devlin, Constructibility, Springer, 1984.
K. Hrbáček, On the complexity of analytic sets, Z. Math. Logik Grundlag. Math. 24 (1978), 419-425.
M. Lerman, Degrees of Unsolvability, Springer, 1983.
H. Muraki, Local density of Kleene degrees, Math. Logic Quart. 43 (1995), 183-189.
H. Muraki, Non-distributive upper semilattice of Kleene degrees, J. Symbolic Logic 64 (1999), 147-158.
R. A. Shore and T. A. Slaman, The p-T degrees of the recursive sets: lattice embeddings, extensions of embeddings and the two-quantifier theory, Theoret. Comput. Sci. 97 (1992), 263-284.
R. Solovay, Determinacy and type 2 recursion (abstract), J. Symbolic Logic 36 (1971), 374.
G. Weitkamp, Kleene recursion over the continuum, Ph.D. Thesis, Pennsylvania State Univ., 1980.