Undecidability and 1-types in the recursively enumerable degrees
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...
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Dokumenttyp: | Article (Journal) |
| Sprache: | Englisch |
| Veröffentlicht: |
1993
|
| In: |
Annals of pure and applied logic
Year: 1993, Jahrgang: 63, Heft: 1, Pages: 3-37 |
| ISSN: | 1873-2461 |
| DOI: | 10.1016/0168-0072(93)90206-S |
| Online-Zugang: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1016/0168-0072(93)90206-S Verlag, lizenzpflichtig, Volltext: https://www.sciencedirect.com/science/article/pii/016800729390206S 
|
| Verfasserangaben: | Klaus Ambos-Spies, Richard A. Shore |
| Zusammenfassung: | 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. |
|---|---|
| Beschreibung: | Elektronische Reproduktion der Druck-Ausgabe 13. Mai 2002 Gesehen am 12.06.2023 |
| Beschreibung: | Online Resource |
| ISSN: | 1873-2461 |
| DOI: | 10.1016/0168-0072(93)90206-S |