Lattice embeddings in the recursively enumerable truth table degrees
HTML articles powered by AMS MathViewer
- by Christine Ann Haught PDF
- Trans. Amer. Math. Soc. 301 (1987), 515-535 Request permission
Abstract:
It is shown that every finite lattice, and in fact every recursively presentable lattice, can be embedded in the r.e. $\text {tt}$-degrees by a map preserving least and greatest elements. The decidability of the $1$-quantifier theory of the r.e. $\text {tt}$-degrees in the language with $\leqslant , \vee , \wedge , 0$, and 1 is obtained as a corollary.References
- 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, DOI 10.1007/BFb0076217 C. A. Haught, Turing and truth table degrees of $1$-generic and recursively enumerable sets, Dissertation, Cornell Univ., Ithaca, N. Y., 1985.
- 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, DOI 10.1090/S0002-9939-1985-0781069-3
- Piergiorgio Odifreddi, Strong reducibilities, Bull. Amer. Math. Soc. (N.S.) 4 (1981), no. 1, 37–86. MR 590818, DOI 10.1090/S0273-0979-1981-14863-1
- 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, DOI 10.1007/BF02482893
- Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
- Richard A. Shore, Finitely generated codings and the degrees r.e. in a degree $\textbf {d}$, Proc. Amer. Math. Soc. 84 (1982), no. 2, 256–263. MR 637179, DOI 10.1090/S0002-9939-1982-0637179-1
Additional Information
- © Copyright 1987 American Mathematical Society
- 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