Undecidability and 1-types in the recursively enumerable degrees

• Verfasst von: Ambos-Spies, Klaus [VerfasserIn]
• Verfasst von: Shore, Richard A. [VerfasserIn]
• Titel: Undecidability and 1-types in the recursively enumerable degrees
• Verf.angabe: Klaus Ambos-Spies, Richard A. Shore
• Jahr: 1993
• Umfang: 35 S.
• Fussnoten: Elektronische Reproduktion der Druck-Ausgabe 13. Mai 2002 ; Gesehen am 12.06.2023
• Titel Quelle: Enthalten in: Annals of pure and applied logic
• Ort Quelle: Amsterdam [u.a.] : Elsevier, 1983
• Jahr Quelle: 1993
• Band/Heft Quelle: 63(1993), 1, Seite 3-37
• ISSN Quelle: 1873-2461
• DOI: doi:10.1016/0168-0072(93)90206-S
• Datenträger: Online-Ressource
• Sprache: eng
• K10plus-PPN: 1848773668

Abstract

Ambos-Spies, K. and R.A. Shore, Undecidability and 1-types in the recursively enumerable degrees, Annals of Pure and Applied Logic 63 (1993) 3-37. We show that the theory of the partial ordering of recursively enumerable Turing degrees is undecidable and has uncountably many 1-types. In contrast to the original proof of the former which used a very complicated O''' argument our proof proceeds by a much simpler infinite injury argument. Moreover, it combines with the permitting technique to get similar results for any ideal of the r.e. degrees.