×

Characterizing the continuous degrees. (English) Zbl 1442.03023

The paper is devoted to the continuous degrees. It is shown that the almost total degrees coincide with the continuous degrees. Since the total degrees are definable in the partial order of enumeration degrees, it follows that the continuous degrees are also definable. Applying earlier work on the continuous degrees, this shows that the relation “PA above” on the total degrees is definable in the enumeration degrees. The authors also prove that every almost total degree is continuous and that the enumeration degree of \(A\) is continuous if and only if \(A\) is codable, meaning that \(A\) is enumeration above the complement of an infinite tree, every path of which enumerates \(A\).

MSC:

03D35 Undecidability and degrees of sets of sentences
03D25 Recursively (computably) enumerable sets and degrees
03D78 Computation over the reals, computable analysis
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Cai, M.; Ganchev, H. A.; Lempp, S.; Miller, J. S.; Soskova, M. I., Defining totality in the enumeration degrees, Journal of the American Mathematical Society, 29, 1051-1067 (2016) · Zbl 1402.03061 · doi:10.1090/jams/848
[2] Day, A. R.; Miller, J. S., Randomness for non-computable measures, Transactions of the American Mathematical Society, 365, 3575-3591 (2013) · Zbl 1307.03026 · doi:10.1090/S0002-9947-2013-05682-6
[3] Friedberg, R. M.; Rogers, H. Jr., Reducibility and completeness for sets of integers, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 5, 117-125 (1959) · Zbl 0108.00602 · doi:10.1002/malq.19590050703
[4] Gács, P., Uniform test of algorithmic randomness over a general space, Theoretical Computer Science, 341, 91-137 (2005) · Zbl 1077.68038 · doi:10.1016/j.tcs.2005.03.054
[5] Grubba, T.; Schröder, M.; Weihrauch, K., Computable metrization, Mathematical Logic Quarterly, 53, 381-395 (2007) · Zbl 1121.03084 · doi:10.1002/malq.200710009
[6] Kalimullin, I. Sh, Definability of the jump operator in the enumeration degrees, Journal of Mathematical Logic, 3, 257-267 (2003) · Zbl 1049.03030 · doi:10.1142/S0219061303000285
[7] T. Kihara and A. Pauly, Point degree spectra of represented spaces, https://arxiv.org/abs/1405.6866. · Zbl 07537759
[8] Kleene, S. C., Introduction to Metamathematics (1952), New York: D. Van Nostrand, New York · Zbl 0047.00703
[9] Levin, L. A., Uniform tests for randomness, Dokladi Akademii Nauk SSSR, 227, 33-35 (1976)
[10] Miller, J. S., Degrees of unsolvability of continuous functions, Journal of Symbolic Logic, 69, 555-584 (2004) · Zbl 1070.03026 · doi:10.2178/jsl/1082418543
[11] Myhill, J., Note on degrees of partial functions, Proceedings of the American Mathematical Society, 12, 519-521 (1961) · Zbl 0101.01201 · doi:10.1090/S0002-9939-1961-0125794-X
[12] Schröder, M., Effective metrization of regular spaces, Computability and Complexity in Analysis, Informatik-Berichte, 235, 63-80 (1998)
[13] Selman, A. L., Arithmetical reducibilities. I, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 17, 335-350 (1971) · Zbl 0229.02037 · doi:10.1002/malq.19710170139
[14] Tychonoff, A., Über einen Metrisationssatz von P. Urysohn, Mathematische Annalen, 95, 139-142 (1926) · JFM 51.0453.02 · doi:10.1007/BF01206602
[15] Urysohn, P., Zum Metrisationsproblem, Mathematische Annalen, 94, 309-315 (1925) · JFM 51.0453.01 · doi:10.1007/BF01208661
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.