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

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

Availability: DVI (A4 paper) and PostScript

**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.

drh@math.uchicago.edu