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
, 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
Retrieve articles in Transactions of the American Mathematical Society with MSC: 03D25, 03D30
Retrieve articles in all journals with MSC: 03D25, 03D30
Additional Information
DOI:
https://doi.org/10.1090/S0002-9947-1987-0882702-4
Article copyright:
© Copyright 1987
American Mathematical Society