##
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