Computably Extendible Order Types

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.