We show that for any ω-r.e. degree d and n-r.e. degree b with d

Mathematical Logic in Philosophy of Mathematics

Direct download (3 more)  

 

Export citation  

 

Bookmark   1 citation  

By constructing a maximal incomplete d.r.e. degree, the nondensity of the partial order of the d.r.e. degrees is established. An easy modification yields the nondensity of the n-r.e. degrees and of the ω-r.e. degrees.

By constructing a maximal incomplete d.r.e. degree, the nondensity of the partial order of the d.r.e. degrees is established. An easy modification yields the nondensity of the n-r.e. degrees and of the ω-r.e. degrees.

This dissertation is highly motivated by d.r.e. Nondensity Theorem, which is interesting in two perspectives. One is that it contrasts Sacks Density Theorem, and hence shows that the structures of r.e. degrees and d.r.e. degrees are different. The other is to investigate what other properties a maximal degree can have.In Chapter 1, we briefly review the backgrounds of Recursion Theory which motivate the topics of this dissertation.In Chapter 2, we introduce the notion of $$ -cupping degree. It is closely (...) related to the notion of maximal d.r.e. degree. In fact, a $$ -cupping degree is maximal d.r.e. degree. We then prove that there exists an isolated $$ -cupping degree by combining strategies for maximality and isolation with some efforts.Chapter 3 is part of a joint project with Steffen Lempp, Yiqun Liu, Keng Meng Ng, Cheng Peng, and Guohua Wu. In this chapter, we prove that any finite boolean algebra can be embedded into d.r.e. degrees as a final segment. We examine the proof of d.r.e. Nondensity Theorem and make developments to the technique to make it work for our theorem. The goal of the project is to see what lattice can be embedded into d.r.e. degrees as a final segment, as we observe that the technique has potential be developed further to produce other interesting results.prepared by Yong Liu.E-mail: [email protected]. (shrink)

The Turing degrees of infinite levels of the Ershov hierarchy were studied by Liu and Peng [8]. In this paper, we continue the study of Turing degrees of infinite levels and lift the study of density property to the levels beyond ω2. In doing so, we rely on notations with some nice properties. We introduce the concept of normalizing notations and generate normalizing notations for higher levels. The generalizations of the weak density theorem and the nondensity theorem are proved (...) for higher levels in the Ershov hierarchy. Furthermore, we also investigate the minimal degrees in the infinite levels of the Ershov hierarchy. (shrink)

In this thesis, we study Turing degrees in the context of classical recursion theory. What we are interested in is the partially ordered structures $\mathcal {D}_{\alpha }$ for ordinals $\alpha <\omega ^2$ and $\mathcal {D}_{a}$ for notations $a\in \mathcal {O}$ with $|a|_{o}\geq \omega ^2$.The dissertation is motivated by the $\Sigma _{1}$ -elementary substructure problem: Can one structure in the following structures $\mathcal {R}\subsetneqq \mathcal {D}_{2}\subsetneqq \dots \subsetneqq \mathcal {D}_{\omega }\subsetneqq \mathcal {D}_{\omega +1}\subsetneqq \dots \subsetneqq \mathcal {D}$ be a $\Sigma _{1}$ (...) -elementary substructure of another? For finite levels of the Ershov hierarchy, Cai, Shore, and Slaman [Journal of Mathematical Logic, vol. 12, p. 1250005] showed that $\mathcal {D}_{n}\npreceq _{1}\mathcal {D}_{m}$ for any $n < m$. We consider the problem for transfinite levels of the Ershov hierarchy and show that $\mathcal {D}_{\omega }\npreceq _{1}\mathcal {D}_{\omega +1}$. The techniques in Chapters 2 and 3 are motivated by two remarkable theorems, Sacks Density Theorem and the d.r.e. Nondensity Theorem.In Chapter 1, we first briefly review the background of the research areas involved in this thesis, and then review some basic definitions and classical theorems. We also summarize our results in Chapter 2 to Chapter 4. In Chapter 2, we show that for any $\omega $ -r.e. set D and r.e. set B with $D<_{T}B$, there is an $\omega +1$ -r.e. set A such that $D<_{T}A<_{T}B$. In Chapter 3, we show that for some notation a with $|a|_{o}=\omega ^{2}$, there is an incomplete $\omega +1$ -r.e. set A such that there are no a-r.e. sets U with $A<_{T}U<_{T}K$. In Chapter 4, we generalize above results to higher levels. We investigate Lachlan sets and minimal degrees on transfinite levels and show that for any notation a, there exists a $\Delta ^{0}_{2}$ -set A such that A is of minimal degree and $A\not \equiv _T U$ for all a-r.e. sets U.prepared by Cheng Peng.E-mail: [email protected]. (shrink)