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)

 
 

 

Finitely generated codings and the degrees r.e. in a degree $ {\bf d}$


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 Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [L] Harrington and R. A. Shore, [1981]. Definable degrees and automorphisms of $ \mathcal{D}$, Bull. Amer. Math. Soc. (N.S.) 4, 97-100. MR 590819 (82g:03077)
  • [C] G. Jockusch, Jr., [1980]. Degrees of generic sets, Recursion Theory: Its Generalizations and Applications (F. R. Drake and S. S. Wainer, eds.), London Math. Soc. Lecture Notes, no. 45, Cambridge Univ. Press, pp. 110-139. MR 598304 (83i:03070)
  • [B] Jonsson, [1953]. On the representation of lattices, Math. Scand. 1, 193-206. MR 0058567 (15:389d)
  • [S] C. Kleene and E. L. Post, [1954]. The upper semi-lattice of degrees of unsolvability, Ann. of Math. (2) 59, 379-407. MR 0061078 (15:772a)
  • [M] Lerman, [1971]. Initial segments of the degrees of unsolvability, Ann. of Math. (2) 93, 365-389. MR 0307893 (46:7008)
  • 1. -, [1982]. Structure theory for the degrees of unsolvability, Springer-Verlag, Berlin (to appear).
  • [M] Lerman, R. A. Shore and R. I. Soare, [1981]. The recursively enumerable degrees are not $ {\aleph _0}$-categorical, Adv. in Math, (to appear). MR 753871 (86d:03040)
  • [D] Posner, [1980]. A survey of the non-$ RE$ degrees $ \leqslant {\mathbf{0}}'$, Recursion Theory: Its Generalizations and Applications (F. R. Drake and S. S. Wainer, eds.), London Math. Soc. Lecture Notes, no. 45, Cambridge Univ. Press, pp. 52-109. MR 598303 (83i:03071)
  • [G] E. Sacks, [1966]. Degrees of unsolvability, 2nd ed., Ann. of Math. Studies, no. 55, Princeton Univ. Press, Princeton, N.J. MR 0186554 (32:4013)

Similar Articles

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

American Mathematical Society