
Re: This Week's Finds in Mathematical Physics (Week 236)
Posted:
Aug 24, 2006 9:00 AM


It might help if I explain where I think the "autonomous progressions" analysis of predicativity goes wrong.
It's basically a bootstrap idea. You start with some formal system that is clearly predicatively acceptable, see which ordinals you can access within that system, use these new ordinals to formulate stronger systems, and repeat.
That is, we have a hierarchy of formal systems S_a, and once we've proven that a is an ordinal (more precisely, an ordinal notation) we get to work in S_a. There are variations but this is the basic idea.
The issue I have raised is: what justifies passing from "a is an ordinal notation" to "S_a is valid"? Well, the argument looks very simple. When you look at the definitions it's clear that if S_c is valid for all c < b then S_b is valid. So let X = {b < a: S_b is not valid}; from what I just said this set has no smallest element, hence by the wellordering property (i.e., a is an ordinal notation) it must be empty. Thus S_b is valid for all b < a, and we finally conclude that S_a is valid.
What's wrong with this argument is that forming the set X requires a comprehension axiom  an axiom that lets you form "the set of x such that P(x)" for some family of properties P  that goes way beyond anything that anyone thinks is predicative.
Now if you look carefully at the proof that autonomous progressions get up to Gamma_0 you find that you don't need the full strength of "S_a is valid". What you need is just "recursive definitions of length a are legitimate". So what's really at stake is: can a predicativist accept that if a is wellordered then constructions of length a are welldefined? We're tempted to say "of course" only because we're used to the classically trivial equivalence between induction and recursion which is proven using an impredicative comprehension axiom.
Here's where it really gets bad for the predicativityislimitedbyGamma_0 idea. Suppose we just agree, on whatever grounds, that predicativists can accept the statement "induction up to a implies recursion up to a". That's *too much*! This would allow the predicativist to see all at once that every a < Gamma_0 is an ordinal notation, and hence that Gamma_0 is an ordinal notation, which he's not supposed to be able to do.
The *only way* to get the Gamma_0 idea to work is to somehow show that (1) for each a, predicativists can accept "induction up to a implies recursion up to a" but (2) they cannot accept "for all a, induction up to a implies recursion up to a". I am not aware of any even remotely plausible defenses for these two claims.
I make this argument in detail in my paper "Predicativity beyond Gamma_0", which is available at
http://www.math.wustl.edu/~nweaver/conceptualism.html
I go to some length to show how essentially the same error appears in a variety of different analyses of predicativism. However, I think it's fundamentally a very simple error that is obvious once you see it, and I am somewhat baffled, and saddened, by the obstinate hostility I've encountered in response to my paper, on the Foundations of Mathematics discussion list and elsewhere.
(The paper is called "Predicativity beyond Gamma_0" because in the second part of the paper I try to show that using hierarchies of truth predicates it's possible to get well beyond Gamma_0 in a predicatively acceptable way.)
Nik Weaver Math Dept. Washington University St. Louis, MO 63130 nweaver@math.wustl.edu

