Computability-Theoretic and Proof-Theoretic Aspects of Partial
and Linear Orderings
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 τ, that if P does not contain a subchain
of order type τ, then we can choose L so that L also
does not contain a subchain of order type τ. 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.
drh@math.uchicago.edu