Incomparability in local structures of s -degrees and Q -degrees
- PDF / 341,229 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 45 Downloads / 205 Views
Mathematical Logic
Incomparability in local structures of s-degrees and Q-degrees Irakli Chitaia1 · Keng Meng Ng2 · Andrea Sorbi3
· Yue Yang4
Received: 20 April 2019 / Accepted: 10 January 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract We show that for every intermediate 20 s-degree (i.e. a nonzero s-degree strictly below the s-degree of the complement of the halting set) there exists an incomparable 01 s-degree. (The same proof yields a similar result for other positive reducibilities as well, including enumeration reducibility.) As a consequence, for every intermediate 02 Q-degree (i.e. a nonzero Q-degree strictly below the Q-degree of the halting set) there exists an incomparable 10 Q-degree. We also show how these results can be applied to provide proofs or new proofs (essentially already known, although some of them not explicitly noted in the literature) of upper density results in local structures of s-degrees and Q-degrees.
Chitaia’s work was supported by Shota Rustaveli National Science Foundation of Georgia (SRNSFG) (Grant number: YS-18-168). Ng was partially supported by the Grants MOE-RG131/17 and MOE2015-T2-2-055. Sorbi was partially supported by PRIN 2017 Grant “Mathematical Logic: models, sets, computability”. Sorbi is a member of INDAM-GNSAGA. Yang’s research was partially supported by NUS Grant R-146-000-231-114.
B
Andrea Sorbi [email protected] Irakli Chitaia [email protected] Keng Meng Ng [email protected] Yue Yang [email protected]
1
Department of Mathematics, Ivane Javakhishvili Tbilisi State University, 0186 Tbilisi, Georgia
2
Division of Mathematical Sciences, School of Physical and Mathematical Sciences, College of Science, Nanyang Technological University, Singapore 639798, Republic of Singapore
3
Dipartimento di Ingegneria Informatica e Scienze Matematiche, Università degli Studi di Siena, 53100 Siena, Italy
4
Department of Mathematics, National University of Singapore, Singapore 119260, Republic of Singapore
123
I. Chitaia et al.
Keywords Enumeration reducibility · s-reducibility · s-degree · Q-reducibility · Q-degree Mathematics Subject Classification 03D25 · 03D30
1 Introduction The reducibility known as s-reducibility is a restricted version of enumeration reducibility. We recall that any computably enumerable (or, c.e.) set W defines an enumeration operator (for short: e-operator), i.e. a mapping W from the power set of ω to the power set of ω (where ω denotes the set of natural numbers) such that, for A ⊆ ω, W (A) = {x : (∃u) [x, u ∈ W and Du ⊆ A] }, where Du is the finite set with canonical index u: throughout the rest of the paper, we will often identify finite sets with their canonical indices, thus writing, for instance, x, D instead of x, u if D = Du . If A = (B) for some e-operator then we say that A is enumeration reducible to B (or, more simply, A is e-reducible to B; in symbols: A e B) via . An e-operator is said to be an s-operator, if is defined by a c.e. set W such that (∀ finite D)(∀x)[x, D ∈ W
Data Loading...
