[FOM] Iterating under Con(T)

[Nik Weaver]

Richard Heck wrote:

> "What happens if we start with PA and keep adding consistency
> statements forever?" ... To make the question more precise, define
> the following sequence of theories by transfinite recursion:
> T_0 = PA
> T_{k+1} = T_k + Con(T_k)
> T_l = \cup_{k<l} T_k, for l a limit

and Joe Shipman warned:

> Eventually there will be a limit ordinal k for which there is no
> canonical statement Con(T_k), so you won't be able to define T_(k+1).

Feferman's "Transfinite Recursive Progressions of Axiomatic Theories"
is certainly the right place to start.  What Joe is getting at is a
subtlety in statements of the form "Con(T)", namely that such a
statement does not refer directly to T but rather to some recursive
enumeration of the Godel numbers of axioms of T.  This causes a
problem at limit ordinals because, given an enumeration of the
axioms of T_k for each k < l, there are many ways to enumerate the
axioms of cup_{k<l} T_k, and you can get inequivalent theories at
stage l depending on the enumeration you choose.  (This is assuming
l is a recursive ordinal.  Actually the whole discussion only makes
sense for recursive ordinals.)

There is a uniform way to define T_k if we take k to be not an
ordinal but a Church-Kleene ordinal notation.  There is also a
stronger natural reflection principle than merely asserting
Con(T), namely, for each formula phi add the omega-rule "if for
each n, T proves phi(n), then (forall n)(phi(n))". Feferman showed
that if you do this to get from T_k to T_{k+1} then cup_k T_k
(taking the union over all ordinal notations) is complete, i.e.,
all true statements of first order arithmetic are theorems.  The
catch is that it's not so easy to determine which natural numbers
are C-K ordinal notations.  Indeed this question embodies not just
arithmetic complexity but second order arithmetic complexity.

It's also sort of cheating because even defining the concept
"Church-Kleene ordinal notation" involves going substantially
beyond PA, so if you're willing to accept this as a legitimate
concept then you should have been willing to start with a
stronger base system.

Feferman addresses this point in "Systems of predicative analysis".
Here the goal is to determine just how far one can get if one
really is only willing to start with PA.  His conclusion is that
one can get up to the ordinal Gamma_0.  However, although this
analysis has been widely accepted for almost half a century, I
believe it is not correct, as I explain at length in my paper
"Predicativity beyond Gamma_0", which is available on my web
page (see especially Section 1.4).

Nik Weaver
Math Dept.
Washington University
St. Louis, MO 63130 USA
nweaver at math.wustl.edu
http://www.math.wustl.edu/~nweaver/