Bounded-low sets and the high/low hierarchy
- PDF / 321,126 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 30 Downloads / 178 Views
Mathematical Logic
Bounded-low sets and the high/low hierarchy Huishan Wu1 Received: 24 October 2018 / Accepted: 18 March 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract Anderson and Csima (Notre Dame J Form Log 55:245–264, 2014) defined a bounded jump operator for bounded-Turing reduction, and studied its basic properties. Anderson et al. (Arch Math Logic 56:507–521, 2017) constructed a low bounded-high set and conjectured that such sets cannot be computably enumerable (c.e. for short). Ng and Yu (Notre Dame J Form Log, to appear) proved that bounded-high c.e. sets are Turing complete, thus answered the conjecture positively. Wu and Wu (Lecture notes in computer science, vol 11436, 647–658. Springer, Cham, 2019) showed that boundedlow sets can be superhigh by constructing a Turing complete bounded-low c.e. set. In this paper, we continue the study of the comparison between the bounded-jump and Turing jump. We show that low c.e. sets are not all bounded-low and that incomplete superhigh c.e. sets can be bounded-low. Keywords Computably enumerable sets · Bounded-low sets · Low sets · Superhigh sets Mathematics Subject Classification 03D10 · 03D25 · 03D30
1 Introduction Csima et al. [4] proved that Shoenfield jump inversion and Sacks jump inversion fail for truth-table reduction and bounded-Turing (also known as weak truth-table) reduction with Turing jump. Researchers in computability theory try to look for other jump operators for strong reducibilities. Anderson and Csima [1] defined the bounded
The author appreciates the referees for useful comments and helpful suggestions. This research project is supported by Science Foundation of Beijing Language and Culture University (supported by “the Fundamental Research Funds for the Central Universities”) (Grant No. 20YJ040004).
B 1
Huishan Wu [email protected] School of Information Science, Beijing Language and Culture University, 15 Xueyuan Road, Haidian District, Beijing 100083, China
123
H. Wu A
jump of A as Ab = {e ∈ N : ∃n ≤ e[ϕn (e) ↓ ∧Ψe ϕn (e) (e) ↓]}, where ϕ0 , ϕ1 , . . . and Ψ0 , Ψ1 , . . . are enumerations of partial computable functions and partial computable Turing functionals respectively, and A y stands for {n ∈ A : n ≤ y}. Anderson and Csima proved nice properties of this bounded jump with respect to bounded-Turing reduction. They also proved that the analogue of Shoenfield jump inversion holds for bounded-Turing reduction with the bounded jump. Ng and Yu [6] solved a question of Anderson and Csima, and proved that the analogue of Sacks jump inversion fails for bounded-Turing reduction with the bounded jump. For a set A, the double bounded jump of A is defined as the bounded jump of Ab , denoted by A2b . A set A is bounded-low if Ab ≤bT ∅b and bounded high if A ≤bT ∅b and ∅2b ≤bT Ab . Anderson et al. [2] proved that there are high bounded-low sets and low bounded-high sets, and conjectured that low bounded-high sets cannot be computably enumerable (c.e. for short). Ng and Yu [6] provided characterizations of bo
Data Loading...
