Finitely generated codings and the degrees r.e. in a degree 𝑑

Shore, Richard A.

doi:10.1090/S0002-9939-1982-0637179-1

Finitely generated codings and the degrees r.e. in a degree $\textbf {d}$
HTML articles powered by AMS MathViewer

by Richard A. Shore

Proc. Amer. Math. Soc. 84 (1982), 256-263

DOI: https://doi.org/10.1090/S0002-9939-1982-0637179-1

PDF | Request permission

Abstract:

We introduce finitely generated (partial) lattices which can be used to code an arbitrary set $D$. Results of Lerman, Shore and Soare are used to embed these lattices in the degrees r.e. in $D$. Thus if the degrees r.e. in and above ${\mathbf {d}}$ are isomorphic to those r.e. in and above ${\mathbf {c}}$, ${\mathbf {d}}$ and ${\mathbf {c}}$ are of the same arithmetic degree. Similar applications are given to generic degrees and general homogeneity questions.

References

Leo Harrington and Richard A. Shore, Definable degrees and automorphisms of ${\cal D}$, Bull. Amer. Math. Soc. (N.S.) 4 (1981), no. 1, 97–100. MR 590819, DOI 10.1090/S0273-0979-1981-14871-0
Carl G. Jockusch Jr., Degrees of generic sets, 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. 110–139. MR 598304
Bjarni Jónsson, On the representation of lattices, Math. Scand. 1 (1953), 193–206. MR 58567, DOI 10.7146/math.scand.a-10377
S. C. Kleene and Emil L. Post, The upper semi-lattice of degrees of recursive unsolvability, Ann. of Math. (2) 59 (1954), 379–407. MR 61078, DOI 10.2307/1969708
Manuel Lerman, Initial segments of the degrees of unsolvability, Ann. of Math. (2) 93 (1971), 365–389. MR 307893, DOI 10.2307/1970779

Structure theory for the degrees of unsolvability

M. Lerman, R. A. Shore, and R. I. Soare, The elementary theory of the recursively enumerable degrees is not $\aleph _{0}$-categorical, Adv. in Math. 53 (1984), no. 3, 301–320. MR 753871, DOI 10.1016/0001-8708(84)90028-8
David B. Posner, A survey of non-r.e. degrees $\leq {\bf 0}^{\prime }$, 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. 52–109. MR 598303
Gerald E. Sacks, Degrees of unsolvability, Princeton University Press, Princeton, N.J., 1963. MR 0186554