Open Access
2009 On the Degrees of Diagonal Sets and the Failure of the Analogue of a Theorem of Martin
Keng Meng Ng
Notre Dame J. Formal Logic 50(4): 469-493 (2009). DOI: 10.1215/00294527-2009-022

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

Download 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

Published: 2009
First available in Project Euclid: 11 February 2010

zbMATH: 1202.03049
MathSciNet: MR2598875
Digital Object Identifier: 10.1215/00294527-2009-022

Subjects:
Primary: 03D25
Secondary: 68Q30

Keywords: computable numberings , hyperhypersimple , maximal

Rights: Copyright © 2009 University of Notre Dame

Vol.50 • No. 4 • 2009
Back to Top