On the Degrees of Diagonal Sets and the Failure of the Analogue of a Theorem of
				Martin

Ng ,  Keng Meng

On the Degrees of Diagonal Sets and the Failure of the Analogue of a Theorem of Martin

Ng , Keng Meng

Notre Dame J. Formal Logic, Tome 50 (2009) no. 1, p. 469-493 / Harvested from Project Euclid

Résumé

Semi-hyperhypersimple c.e. sets, also known as diagonals, were introduced by Kummer. He showed that by considering an analogue of hyperhypersimplicity, one could characterize the sets which are the Halting problem relative to arbitrary computable numberings. One could also consider half of splittings of maximal or hyperhypersimple sets and get another variant of maximality and hyperhypersimplicity, which are closely related to the study of automorphisms of the c.e. sets. We investigate the Turing degrees of these classes of c.e. sets. In particular, we show that the analogue of a theorem of Martin fails for these classes.

Publié le : 2009-10-15
Classification: maximal, hyperhypersimple, computable numberings, 03D25, 68Q30

@article{1265899126,
     author = {Ng ,  Keng Meng},
     title = {On the Degrees of Diagonal Sets and the Failure of the Analogue of a Theorem of
				Martin},
     journal = {Notre Dame J. Formal Logic},
     volume = {50},
     number = {1},
     year = {2009},
     pages = { 469-493},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1265899126}
}

Ng ,  Keng Meng. On the Degrees of Diagonal Sets and the Failure of the Analogue of a Theorem of
				Martin. Notre Dame J. Formal Logic, Tome 50 (2009) no. 1, pp.  469-493. http://gdmltest.u-ga.fr/item/1265899126/