White Rose University Consortium logo
University of Leeds logo University of Sheffield logo York University logo

Lachlan Non-Splitting Pairs and High Computably Enumerable Turing Degrees

Bondin, Ingram (2018) Lachlan Non-Splitting Pairs and High Computably Enumerable Turing Degrees. PhD thesis, University of Leeds.

[img] Text (PDF)
Ingram Bondin - PhD dissertation.pdf - Final eThesis - complete (pdf)
Restricted until 1 December 2019.

Request a copy

Abstract

A given c.e. degree a > 0 has a non-trivial splitting into c.e. degrees v and w if a is the join of v and w and v | w. A Lachlan Non-Splitting Pair is a pair of c.e. degrees <a,d> such that a > d and there is no non-trivial splitting of a into c.e. degrees w and v with w > d and v > d. Lachlan [Lachlan1976] showed that such a pair exists by proving the Lachlan Non-Splitting Theorem. This theorem is remarkable for its discovery of the 0'''-priority method, and became known as the `Monster' due to its significant complexity. Harrington, Shore and Slaman subsequently tried to explain Lachlan's methods in more intuitive and comprehensible terms in a number of unpublished notes. Leonhardi [Leonhardi1997] then published a short account of the Lachlan Non-Splitting Theorem based on these notes and generalised the theorem in a different direction. In their work on the separation of the jump class High from the jump class Low2, Shore and Slaman [SlamanShore1993] also conjectured that every high c.e. degree strictly bounds a Lachlan Non-Splitting Pair, a fact which could be used to separate the two jump classes. While this separation was eventually achieved through the notion of a Slaman Triple, the conjecture itself remained an open question. Cooper, Yi and Li [CooperLiYi2002] also defined the notion of a c.e. Robinson degree as one which does not strictly bound the base d of a Lachlan Non-Splitting Pair <a,d>, and sought to understand the relationship of this notion to the High/Low Hierarchy. In this dissertation we make the following two contributions. Firstly we show that a counter-example can be found to show that the account of the Lachlan Non-Splitting Theorem given by Leonhardi [Leonhardi1997] fails to satisfy its requirements. By rectifying the construction, we give a complete, correct and intuitive account of the Lachlan Non-Splitting Theorem. Secondly we show that the high permitting method developed by Shore and Slaman [SlamanShore1993] can be combined with the construction of the Lachlan Non-Splitting Theorem just described to prove that every high c.e. degree strictly bounds a Lachlan Non-Splitting Pair. From this it follows that the existence of a Lachlan Non-Splitting Pair can be used to separate the jump classes High and Low2, that the distribution of Lachlan Non-Splitting Pairs with respect to these jump classes mirrors the one for Slaman Triples, and that there is no high c.e. Robinson degree.

Item Type: Thesis (PhD)
Keywords: Computably Enumerable Turing Degrees, Lachlan Non-Splitting Pairs, High Degrees
Academic Units: The University of Leeds > Faculty of Maths and Physical Sciences (Leeds) > School of Mathematics (Leeds) > Pure Mathematics (Leeds)
Depositing User: Mr Ingram Bondin
Date Deposited: 13 Nov 2018 12:14
Last Modified: 13 Nov 2018 12:14
URI: http://etheses.whiterose.ac.uk/id/eprint/22019

Please use the 'Request a copy' link(s) above to request this thesis. This will be sent directly to someone who may authorise access.
You can contact us about this thesis. If you need to make a general enquiry, please see the Contact us page.

Actions (repository staff only: login required)