Abstract
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.
Citation
Keng Meng Ng . "On the Degrees of Diagonal Sets and the Failure of the Analogue of a Theorem of Martin." Notre Dame J. Formal Logic 50 (4) 469 - 493, 2009. https://doi.org/10.1215/00294527-2009-022
Information