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...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
1993
|
| In: |
Annals of pure and applied logic
Year: 1993, Volume: 63, Issue: 1, Pages: 3-37 |
| ISSN: | 1873-2461 |
| DOI: | 10.1016/0168-0072(93)90206-S |
| Online Access: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1016/0168-0072(93)90206-S Verlag, lizenzpflichtig, Volltext: https://www.sciencedirect.com/science/article/pii/016800729390206S 
|
| Author Notes: | Klaus Ambos-Spies, Richard A. Shore |
| Summary: | 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. |
|---|---|
| Item Description: | Elektronische Reproduktion der Druck-Ausgabe 13. Mai 2002 Gesehen am 12.06.2023 |
| Physical Description: | Online Resource |
| ISSN: | 1873-2461 |
| DOI: | 10.1016/0168-0072(93)90206-S |