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

Computably Extendible Order Types

Gay, James Robert Kishore (2016) Computably Extendible Order Types. PhD thesis, University of Leeds.

Text (Final eThesis)
thesis.pdf - Final eThesis - complete (pdf)
Available under License Creative Commons Attribution-Noncommercial-Share Alike 2.0 UK: England & Wales.

Download (488Kb) | Preview


In this thesis we consider, from a computability perspective, the question of what order-theoretic properties of a partial order can be preserved under linear extension. It is well-known that such properties as well-foundedness or scatteredness can be preserved, that is, given any well-founded partial order you can find a well-founded linear extension and mutatis mutandis for scattered partial orders. An order type σ is extendible if a partial order that does not embed σ can always be extended to a linear order that does not extend σ. So for example “given any well-founded partial order, you can find a well-founded linear extension” is equivalent to saying that ω^∗ is extendible. The extendible order types were classified by Bonnet [3] in 1969. We define notions of computable extendibility and then apply them to investigate the computable extendibility of three commonly used order types, ω^∗ , ω^∗ + ω and η. In Chapter 2 we prove that given a computably well-founded computable partial order, you can find a computably well-founded ω-c.e. linear extension, and further that this result doesn’t hold for n-c.e. for any finite n. In Chapter 3 we show how to extend these results for linearisations of computable partial orders which do not embed ζ = ω^∗ + ω. In Chapter 4 we prove the analogous results for scattered partial orders.

Item Type: Thesis (PhD)
Keywords: partial order, linear order, total order, linearisation, well-founded, scattered, computable partial order, computable linearisation
Academic Units: The University of Leeds > Faculty of Maths and Physical Sciences (Leeds) > School of Mathematics (Leeds) > Pure Mathematics (Leeds)
Identification Number/EthosID: uk.bl.ethos.694112
Depositing User: Mr James Gay
Date Deposited: 27 Sep 2016 12:52
Last Modified: 06 Oct 2016 14:43
URI: http://etheses.whiterose.ac.uk/id/eprint/13976

You do not need to contact us to get a copy of this thesis. Please use the 'Download' link(s) above to get a copy.
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)