Lattice embeddings in the recursively enumerable truth table degrees

Haught, Christine Ann

doi:10.1090/S0002-9947-1987-0882702-4

Lattice embeddings in the recursively enumerable truth table degrees

Author: Christine Ann Haught
Journal: Trans. Amer. Math. Soc. 301 (1987), 515-535
MSC: Primary 03D25; Secondary 03D30
DOI: https://doi.org/10.1090/S0002-9947-1987-0882702-4
MathSciNet review: 882702
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: It is shown that every finite lattice, and in fact every recursively presentable lattice, can be embedded in the r.e. tt-degrees by a map preserving least and greatest elements. The decidability of the -quantifier theory of the r.e. tt-degrees in the language with $\leqslant ,\, \vee ,\, \wedge ,\,0$ , and 1 is obtained as a corollary.

[1] Peter A. Fejer and Richard A. Shore, Embeddings and extensions of embeddings in the r.e. tt- and wtt-degrees, Recursion theory week (Oberwolfach, 1984) Lecture Notes in Math., vol. 1141, Springer, Berlin, 1985, pp. 121–140. MR 820777, https://doi.org/10.1007/BFb0076217
[2] C. A. Haught, Turing and truth table degrees of -generic and recursively enumerable sets, Dissertation, Cornell Univ., Ithaca, N. Y., 1985.
[3] Carl G. Jockusch Jr. and Jeanleah Mohrherr, Embedding the diamond lattice in the recursively enumerable truth-table degrees, Proc. Amer. Math. Soc. 94 (1985), no. 1, 123–128. MR 781069, https://doi.org/10.1090/S0002-9939-1985-0781069-3
[4] Piergiorgio Odifreddi, Strong reducibilities, Bull. Amer. Math. Soc. (N.S.) 4 (1981), no. 1, 37–86. MR 590818, https://doi.org/10.1090/S0273-0979-1981-14863-1
[5] Pavel Pudlák and Jiří T ma, Every finite lattice can be embedded in a finite partition lattice, Algebra Universalis 10 (1980), no. 1, 74–95. MR 552159, https://doi.org/10.1007/BF02482893
[6] Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
[7] Richard A. Shore, Finitely generated codings and the degrees r.e. in a degree 𝑑, Proc. Amer. Math. Soc. 84 (1982), no. 2, 256–263. MR 637179, https://doi.org/10.1090/S0002-9939-1982-0637179-1