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

Jockusch, Carl G.; Mohrherr, Jeanleah

doi:10.1090/S0002-9939-1985-0781069-3

Embedding the diamond lattice in the recursively enumerable truth-table degrees
HTML articles powered by AMS MathViewer

by Carl G. Jockusch and Jeanleah Mohrherr

Proc. Amer. Math. Soc. 94 (1985), 123-128

DOI: https://doi.org/10.1090/S0002-9939-1985-0781069-3

PDF | Request permission

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

Embedding recursively presented lattices into the r.e. tt-degrees

Carl G. Jockusch Jr., Semirecursive sets and positive reducibility, Trans. Amer. Math. Soc. 131 (1968), 420–436. MR 220595, DOI 10.1090/S0002-9947-1968-0220595-7
A. H. Lachlan, Some notions of reducibility and productiveness, Z. Math. Logik Grundlagen Math. 11 (1965), 17–44. MR 172795, DOI 10.1002/malq.19650110104
A. H. Lachlan, A note on universal sets, J. Symbolic Logic 31 (1966), 573–574. MR 211857, DOI 10.2307/2269692
A. H. Lachlan, Lower bounds for pairs of recursively enumerable degrees, Proc. London Math. Soc. (3) 16 (1966), 537–569. MR 204282, DOI 10.1112/plms/s3-16.1.537
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
David B. Posner, The upper semilattice of degrees $\leq {\bf 0}^{\prime }$ is complemented, J. Symbolic Logic 46 (1981), no. 4, 705–713. MR 641484, DOI 10.2307/2273220
Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto-London, 1967. MR 0224462
J. R. Shoenfield, Quasicreative sets, Proc. Amer. Math. Soc. 8 (1957), 964–967. MR 89808, DOI 10.1090/S0002-9939-1957-0089808-7
Robert I. Soare, Fundamental methods for constructing recursively enumerable degrees, Recursion theory: its generalisation and applications (Proc. Logic Colloq., Univ. Leeds, Leeds, 1979) London Math. Soc. Lecture Note Ser., vol. 45, Cambridge Univ. Press, Cambridge-New York, 1980, pp. 1–51. MR 598302
Paul R. Young, On semi-cylinders, splinters, and bounded-truth-table reducibility, Trans. Amer. Math. Soc. 115 (1965), 329–339. MR 209151, DOI 10.1090/S0002-9947-1965-0209151-1