Back to search

University of Leeds

Computably Extendible Order Types

Abstract

dc:description.abstract

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.

Degree

thesis:*
Name dc:type.qualificationname
Ph.D
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of Leeds
Year dc:date.issued
2016

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Gay, James Robert Kishore
Advisors dc:contributor.advisor
  • Halupczok, Immanuel
  • Cooper, S Barry
  • Macpherson, H Dugald

Rights

Language dc:language.dcterms_iso639_2
eng

Identifiers

dc:identifier.*
Identifier
uk.bl.ethos.694112

Chain of custody

source
Harvested from
White Rose University Consortium
Base URL
etheses.whiterose.ac.uk/cgi/oai2
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

Gay, James Robert Kishore. Computably Extendible Order Types. doctoral thesis, University of Leeds, 2016.