UNDECIDABILITY AND 1-TYPES IN THE RECURSIVELY-ENUMERABLE DEGREES

Authors
AMBOSSPIES K SHORE RA
Citation
K. Ambosspies et Ra. Shore, UNDECIDABILITY AND 1-TYPES IN THE RECURSIVELY-ENUMERABLE DEGREES, Annals of pure and applied Logic, 63(1), 1993, pp. 3-37
Citations number
18
Categorie Soggetti
Mathematics, Pure",Mathematics,Mathematics,Mathematics
Journal title
Annals of pure and applied Logic → ACNP
ISSN journal
01680072
Volume
63
Issue
1
Year of publication
1993
Pages
3 - 37
Database
ISI
SICI code
0168-0072(1993)63:1<3:UA1ITR>2.0.ZU;2-9
Abstract
We show that the theory of the partial ordering of recursively enumera ble Turing degrees is undecidable and has uncountably many 1-types. In contrast to the original proof of the former which used a very compli cated 0''' argument our proof proceeds by a much simpler infinite inju ry argument. Moreover, it combines with the permitting technique to ge t similar results for any ideal of the r.e. degrees.