Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

Embedding the diamond lattice in the recursively enumerable truth-table degrees


Authors: Carl G. Jockusch and Jeanleah Mohrherr
Journal: Proc. Amer. Math. Soc. 94 (1985), 123-128
MSC: Primary 03D25
DOI: https://doi.org/10.1090/S0002-9939-1985-0781069-3
MathSciNet review: 781069
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: It is shown that the four element Boolean algebra can be embedded in the recursively enumerable truth-table degrees with least and greatest elements preserved. Corresponding results for other lattices and other reducibilites are also discussed.


References [Enhancements On Off] (What's this?)

  • [1] P. Fejer and R. Shore, Embedding recursively presented lattices into the r.e. tt-degrees (to appear).
  • [2] C. Jockusch, Semirecursive sets and positive reducibility, Trans. Amer. Math. Soc. 131 (1968), 420-436. MR 0220595 (36:3649)
  • [3] A. H. Lachlan, Some notions of reducibility and productiveness, Z. Math. Logik Grundlagen Math. 11 (1965), 17-44. MR 0172795 (30:3014)
  • [4] -, A note on universal sets, J. Symbolic Logic 31 (1966), 573-574. MR 0211857 (35:2732)
  • [5] -, Lower bounds for pairs of recursively enumerable degrees, Proc. London Math. Soc. 16 (1966), 537-569. MR 0204282 (34:4126)
  • [6] P. G. Odifreddi, Strong reducibilities, Bull. Amer. Math. Soc. (N.S.) 4 (1981), 37-86. MR 590818 (82k:03064)
  • [7] D. Posner, The upper semilattice of degrees $ \leqslant 0'$ is complemented, J. Symbolic Logic 46 (1981), 705-713. MR 641484 (84i:03084)
  • [8] H. Rogers, Theory of recursive functions and effective computability, McGraw-Hill, New York, 1968. MR 0224462 (37:61)
  • [9] J. R. Shoenfield, Quasicreative sets, Proc. Amer. Math. Soc. 8 (1957), 964-967. MR 0089808 (19:723b)
  • [10] R. I. Soare, Fundamental methods for constructing recursively enumerable degrees, Recursion Theory, Its Generalisations and Applications (F. R. Drake and S. S. Wainer, editors), Cambridge Univ. Press, Cambridge, 1980, pp. 1-51. MR 598302 (82j:03051)
  • [11] P. R. Young, On semicylinders, splinters, and bounded truth-table reducibility, Trans. Amer. Math. Soc. 115 (1965), 329-339. MR 0209151 (35:54)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 03D25

Retrieve articles in all journals with MSC: 03D25


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1985-0781069-3
Keywords: Recursively enumerable sets, truth-table degrees, lattice embeddings
Article copyright: © Copyright 1985 American Mathematical Society

American Mathematical Society