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

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.