Contributions to degree structures
Date of Issue2011
School of Physical and Mathematical Sciences
The investigation of computably enumerable degrees has led to the deep understanding of degree structures and the development of various construction techniques. This thesis is mainly concerned with the cupping and capping properties of computably enumerable degrees. In Chapter 1, we give an introduction to the fundamentals of computability theory, and notations used through the thesis. In Chapter 2, we study the only-high cuppable degrees, which was recently found by Greenberg, Ng and Wu, we prove that such degrees can be plus-cupping. This result refutes a claim of Li and Y. Wang, which says that every plus-cupping degree is 3-plus-cupping. In Chapter 3, we study the locally noncappable degrees, and we prove that for any nonzero incomplete c.e. degree a, there exist two incomparable c.e. degrees c, d > a witnessing that a is locally noncappable, and the supremum of c and d is high. This result implies that both classes of the plus-cuppping degrees and the nonbounding c.e. degrees do not form an ideal, which was proved by Li and Zhao by two separate constructions. Chapter 4 is devoted to the study of the infima of n-c.e. degrees. Kaddah proved that there are n-c.e. degrees a, b, c and an (n+1)-c.e. degree x such that a is the infimum of b and c in the n-c.e. degrees, but not in the (n+1)-c.e. degrees, as a < x < b, c. We will prove that such 4-tuples occur densely in the c.e. degrees. This result immediately implies that the isolated (n+1)-c.e. degrees are dense in the c.e. degrees, which was first proved by LaForte.