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
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

Turing and truth table degrees of

-generic and recursively enumerable sets

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