Local structure theory and the Ershov hierarchy

This thesis is concerned with three special properties of Turing degree structure and the Ershov hierarchy. We study the distributions of the nonhemimaximal c.e. degrees, noncomputable left c.e. reals with only computable presentations, and the cupping property in the Ershov hierarchy. A general int...

Full description

Saved in:
Bibliographic Details
Main Author: Fang, Chengling
Other Authors: Wu Guohua
Format: Theses and Dissertations
Language:English
Published: 2012
Subjects:
Online Access:https://hdl.handle.net/10356/48687
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-48687
record_format dspace
spelling sg-ntu-dr.10356-486872023-02-28T23:46:49Z Local structure theory and the Ershov hierarchy Fang, Chengling Wu Guohua School of Physical and Mathematical Sciences DRNTU::Science::Mathematics::Mathematical logic This thesis is concerned with three special properties of Turing degree structure and the Ershov hierarchy. We study the distributions of the nonhemimaximal c.e. degrees, noncomputable left c.e. reals with only computable presentations, and the cupping property in the Ershov hierarchy. A general introduction is presented in Chapter 1. In Chapter 2, we study the distribution of nonhemimaximal c.e. degrees. Here, we give an alternative proof of the existence of a low2, but not low, nonhemimaximal c.e. degree, where the technique used is a 0′′ -priority argument. In Chapter 3, we investigate left c.e. reals and prove that below any high c.e. degree, there is a noncomputable left c.e. real with only computable presentations. The proof of this result utilizes the machinery developed by Shore and Slaman. In Chapter 4, we study the complements of cappable c.e. degrees. We prove that for any nonzero cappable c.e. degree c, there is an almost universal cupping d.c.e. degree d and a c.e. degree b < d such that (i) b and c form a minimal pair; and (ii) b bounds all c.e. degrees below d. DOCTOR OF PHILOSOPHY (SPMS) 2012-05-08T03:09:52Z 2012-05-08T03:09:52Z 2012 2012 Thesis Fang, C. L. (2012). Local structure theory and the Ershov hierarchy. Doctoral thesis, Nanyang Technological University, Singapore. https://hdl.handle.net/10356/48687 10.32657/10356/48687 en 116 p. application/pdf
institution Nanyang Technological University
building NTU Library
continent Asia
country Singapore
Singapore
content_provider NTU Library
collection DR-NTU
language English
topic DRNTU::Science::Mathematics::Mathematical logic
spellingShingle DRNTU::Science::Mathematics::Mathematical logic
Fang, Chengling
Local structure theory and the Ershov hierarchy
description This thesis is concerned with three special properties of Turing degree structure and the Ershov hierarchy. We study the distributions of the nonhemimaximal c.e. degrees, noncomputable left c.e. reals with only computable presentations, and the cupping property in the Ershov hierarchy. A general introduction is presented in Chapter 1. In Chapter 2, we study the distribution of nonhemimaximal c.e. degrees. Here, we give an alternative proof of the existence of a low2, but not low, nonhemimaximal c.e. degree, where the technique used is a 0′′ -priority argument. In Chapter 3, we investigate left c.e. reals and prove that below any high c.e. degree, there is a noncomputable left c.e. real with only computable presentations. The proof of this result utilizes the machinery developed by Shore and Slaman. In Chapter 4, we study the complements of cappable c.e. degrees. We prove that for any nonzero cappable c.e. degree c, there is an almost universal cupping d.c.e. degree d and a c.e. degree b < d such that (i) b and c form a minimal pair; and (ii) b bounds all c.e. degrees below d.
author2 Wu Guohua
author_facet Wu Guohua
Fang, Chengling
format Theses and Dissertations
author Fang, Chengling
author_sort Fang, Chengling
title Local structure theory and the Ershov hierarchy
title_short Local structure theory and the Ershov hierarchy
title_full Local structure theory and the Ershov hierarchy
title_fullStr Local structure theory and the Ershov hierarchy
title_full_unstemmed Local structure theory and the Ershov hierarchy
title_sort local structure theory and the ershov hierarchy
publishDate 2012
url https://hdl.handle.net/10356/48687
_version_ 1759855788207112192