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

Author:
Richard A. Shore

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

MSC:
Primary 03D25; Secondary 03D30

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

MathSciNet review:
637179

Full-text PDF

Abstract | References | Similar Articles | Additional Information

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

**[L]**Leo Harrington and Richard A. Shore,*Definable degrees and automorphisms of \cal𝐷*, Bull. Amer. Math. Soc. (N.S.)**4**(1981), no. 1, 97–100. MR**590819**, https://doi.org/10.1090/S0273-0979-1981-14871-0**[C]**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****[B]**Bjarni Jónsson,*On the representation of lattices*, Math. Scand**1**(1953), 193–206. MR**0058567**, https://doi.org/10.7146/math.scand.a-10377**[S]**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**0061078**, https://doi.org/10.2307/1969708**[M]**Manuel Lerman,*Initial segments of the degrees of unsolvability*, Ann. of Math. (2)**93**(1971), 365–389. MR**0307893**, https://doi.org/10.2307/1970779**1.**-, [1982].*Structure theory for the degrees of unsolvability*, Springer-Verlag, Berlin (to appear).**[M]**M. Lerman, R. A. Shore, and R. I. Soare,*The elementary theory of the recursively enumerable degrees is not ℵ₀-categorical*, Adv. in Math.**53**(1984), no. 3, 301–320. MR**753871**, https://doi.org/10.1016/0001-8708(84)90028-8**[D]**David B. Posner,*A survey of non-r.e. degrees ≤0′*, 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****[G]**Gerald E. Sacks,*Degrees of unsolvability*, Princeton University Press, Princeton, N.J., 1963. MR**0186554**

Retrieve articles in *Proceedings 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-9939-1982-0637179-1

Keywords:
Recursively enumerable degrees,
homogeneity problems,
generic degrees

Article copyright:
© Copyright 1982
American Mathematical Society