COMPUTABLY ENUMERABLE SETS AND QUASI-REDUCIBILITY

Authors
DOWNEY R LAFORTE G NIES A
Citation
R. Downey et al., COMPUTABLY ENUMERABLE SETS AND QUASI-REDUCIBILITY, Annals of pure and applied Logic, 95(1-3), 1998, pp. 1-35
Citations number
15
Categorie Soggetti
Mathematics,Mathematics,Mathematics,Mathematics
Journal title
Annals of pure and applied Logic → ACNP
ISSN journal
01680072
Volume
95
Issue
1-3
Year of publication
1998
Pages
1 - 35
Database
ISI
SICI code
0168-0072(1998)95:1-3<1:CESAQ>2.0.ZU;2-A
Abstract
We consider the computably enumerable sets under the relation of Q-red ucibility. We first give several results comparing the upper semilatti ce of c.e. Q-degrees, [R-Q, less than or equal to (Q)], under this red ucibility with the more familiar structure of the c.e. Turing degrees. In our final section, we use coding methods to show that the elementa ry theory of [R-Q, less than or equal to (Q)] is undecidable. (C) 1998 Elsevier Science B.V. All rights reserved.