Computability-Theoretic and Proof-Theoretic Aspects of Partial and Linear Orderings

by Rodney G. Downey, Denis R. Hirschfeldt, Steffen Lempp, and Reed Solomon

Status: published in the Israel Journal of Mathematics 138 (2003) 271 - 290.

Availability: journal version and preprint

Abstract. Szpilrajn's Theorem states that any partial order P has a linear extension L. This is a central result in the theory of partial orderings, allowing one to define, for instance, the dimension of a partial ordering. It is now natural to ask questions like "Does a well-partial ordering always have a well-ordered linear extension?" Variations of Szpilrajn's Theorem state, for various (but not for all) linear order types t, that if P does not contain a subchain of order type t, then we can choose L so that L also does not contain a subchain of order type t. In particular, a well-partial ordering always has a well-ordered extension.

We show that several effective versions of variations of Szpilrajn's Theorem fail, and use this to narrow down their proof-theoretic strength in the spirit of reverse mathematics.