__Preliminary version of article:__

** Arnold Beckmann, Samuel R. Buss, Chris Pollett.
"Ordinal Notations and Well-Orderings in Bounded Arithmetic."
Annals of Pure and Applied Logic 120 ( 2002) 197-223.
Publisher's Erratum: Annals of Pure and Applied Logic 123 ( 2003) 291.**

** Download: postscript or PDF.**

** From the introduction: **Ordinal notations and
provability of well-foundedness have been a central tool in the study of the consistency
strength and computational strength of formal theories of arithmetic. This development
began with Gentzen's consistency proof for Peano arithmetic based on the well-foundedness
of ordinal notations up to $\epsilon_0$. Since the work of Gentzen, ordinal notations and
provable well-foundedness have been studied extensively for many other formal systems,
some stronger and some weaker than Peano arithmetic. In the present paper, we investigate
the provability and non-provability of well-foundedness of ordinal notations in very weak
theories of bounded arithmetic, notably the theories $S^i_2$ and $T^i_2$ with $1\le i \le
2$. We prove several results about the provability of well-foundedness for ordinal
notations; our main results state that for the usual ordinal notations for ordinals below
$\epsilon_0$ and $\Gamma_0$, the theories $T^1_2$ and $S^2_2$ can prove the ordinal
$\Sigma^b_1$-minimization principle over a bounded domain. PLS is the class of functions
computed by a polynomial local search to minimize a cost function. It is a corollary of
our theorems that the cost function can be allowed to take on ordinal values
below~$\Gamma_0$, without increasing the class PLS.