Sunday, January 11, 2009

Parsons's Mathematical Thought: Sec. 50, Induction and impredicativity

Here's the first half of an improved(?!?) discussion of this section: sorry about the delay!

Parsons now takes up another topic that he has written about influentially before, namely impredicativity. He describes his own earlier claim like this: "no explanation [of the predicate `is a natural number'] is in sight that is not impredicative''. That claim has been challenged by Feferman and Hellman in a couple of joint papers, and Parsons takes the present opportunity to respond. As the title of this section indicates, Parsons links claims about impredicativity to thoughts about the scope of induction: but as we'll see, the link takes some teasing out.

What, though, does Parson mean by impredicativity? Oddly, he doesn't come out with a straight definition of the notion. Nor does he really explain why it might matter whether definitions of the natural numbers have to be impredicative. So before tackling his discussion, we'd better pause for some preliminary clarifications and reflections.

The usual sort of account of impredicativity, in the same vein as Russell's original (or rather, as one of Russell's originals), runs roughly like this: 'a definition ... is impredicative if it defines an object which is one of the values of a bound variable occurring in the defining expression', i.e. an impredicative specification of an entity is one 'involving quantification over all entities of the same kind as itself'. (Here,the first quotation is from Fraenkel, Bar-Hillel and Levy, Foundations of Set Theory, p. 38, one of a number of very similiar Russellian definitions quoted by Alexander George in his 'The imprecision of impredicavity; the second much more recent quotation is from John Burgess Fixing Frege, p. 40.) Thus Weyl, famously, argued against the cogency of some standard constructions in classical analysis on the grounds of their impredicativity in this sense. (And because ACA0 bans impredicative specifications of sets of numbers, it provides one possible framework for developing those portions of analysis which should be acceptable to someone with Weyl's scruples. Now, as Parsons in effect notes, a theory like ACA0 which lacks an impredicative comprehension principle is often described as being, unqualifiedly, a predicative theory of arithmetic: but that description takes it for granted that its first-order core -- usually first order Peano Arithmetic -- isn't impredicative in some other respect.)

But why should we care about avoiding impredicative definitions for Xs? Why should such definitions lack cogency? Well, suppose we think that Xss are in some sense (however tenuous) 'constructed by us' and not determined to exist prior to our mathematical activity. Then, very plausibly, it is illegitimate to give a recipe for constructing a particular X which requires us to take as already given a totality of Xs which includes the very one that is now being constructed. So at least any definition which is to play the role of a recipe-for-construction had better not be impredicative. Given Weyl's constructivism about sets, then, it is no surprise that he rejects impredicative definitions of sets. I'll not pause to assess this line of thought any further here: but I take it that it is a familiar one. (By the way, I don't want to imply that constructivist thoughts are the only ones that might make us suspicious of impredicative definitions: though as Ramsey and Gödel pointed out, it is far from clear why a gung-ho realist should eschew impredicative definitions.)

Now, on the Russellian understanding of the idea, a definition of the set of natural numbers will count as 'impredicative' if it quantifies over some totality of sets including the set of natural of numbers. Modulated into property talk, we'd have: a definition of the property of being a natural number will count as impredicative if it quantifies over some totality of properties including the property of being a natural number. Some familiar definitions are indeed impredicative in this sense: take, for example, a Frege/Russell definition which says that x is a natural number iff x has all the hereditary properties of zero. Then, the quantification is over a totality which includes the property of being a natural number, and the definition is impredicative in a Russellian sense. But are all explanations we might give of what it is to be a natural number impredicative in the same way?

Take, for example, what I'll call 'the simplest explanation': (i) zero is a natural number, (ii) if n is a natural number, so is Sn, and (iii) whatever is a natural number is so in virtue of clauses (i) and (ii) -- and hence, almost immediately, (iv) the natural numbers are what we can do induction over. This characterization of the property of being a natural number which Parsons gives in Sec. 47 does not explicitly involve a quantification over a class of properties including that of a natural number. And though it might be claimed that an understanding of the extremal clause (iii) requires a grasp of second-order quantification, I've urged before that this view is contentious (and indeed the view doesn't seem to be one that Parsons endorses -- see again the discussion of his Sec. 47). So here we have, arguably, an explanation of the concept of number which isn't impredicative in the Russellian sense. But does the quantification in (iii) make the explanation impredicative in some different, albeit closely related, sense?

Well here's Edward Nelson, at the beginning of his book, Predicative Arithmetic. In induction we can use what he calls 'inductive formulae' which involve quantifiers over the numbers themselves. This, he supposes, entangles us with what he calls an 'impredicative concept of number':

A number is conceived to be an object satisfying every inductive formula; for a particular inductive formula, therefore, the bound variables are conceived to range over objects satisfying every inductive formula, including the one in question.
Dummett, quoted approvingly by Parsons, says much the same:
[T]he notion of `natural number' ... is impredicative. The totality of natural numbers is characterised as one for which induction is valid with respect to any well-defined property, ... the impredicativity remains, since the definitions of the properties may
contain quantifiers whose variables range over the totality characterised.
So the thought seems to be that any definition of the numbers is more or less directly going to characterize them as what we can do induction over, and that `a characterization of the natural numbers
that includes induction as part of it will be impredicative' (to quote Parsons's gloss). But note, Dummett says that there is impredicativity here, not because the totality of natural numbers is being defined in terms of a quantification over some domain which has as a member the totality of natural numbers itself (which is what we'd expect on the Russellian definition), but because the totality is defined in terms of a quantification whose domain is (or includes) the same totality. To quote Parsons again:
Because the number concept is characterized as one for which induction holds for any well-defined predicate or property, there is impredicativity if those involving quantification over numbers are included, as they evidently are.
However, to repeat, that involves a non-Russellian notion of impredicativity. In fact it seems that Parsons would also say that an explanation of the concept P -- whether or not couched as an explicit definition -- is impredicative if it involves a quantification over the totality of things of which fall under P. It is perhaps in this extended sense, then, that our 'simplest explanation' of the property of being a natural number might be said to be impredicative.

But now note that it isn't at all obvious why we should worry about about a property's being impredicative if it is a non-Russellian case. Suppose, just for example, we want to be some kind of constructivist about the numbers: then how are our constructivist principles going to be offended by saying that the numbers are zero, its successors, and nothing else? Prescinding from worries about our limited capacities, the 'simplest explanation' of the numbers tells us, precisely, how each and every number can be 'constructed', at least in principle, and tells us not to worry about there being any 'rogue cases' which our construction rules can't reach. What more can we sensibly want? We might add that, if we are swayed by the structuralist thought that in some sense we can only be given the natural numbers all together (whether by a general method of construction, or otherwise), then perhaps we ought to expect that any acceptable explanation of the property of being a natural number will -- when properly articulated -- involve us in talking of all the numbers, at least in that seemingly anodyne way that is involved in the extremal clause (iii) above.

These preliminary reflections, then, seem rather to diminish the interest of the claim that characterizations of the property natural number are inevitably impredicative, if that is meant in the in the Parsons sense. But be that as it may. Let's next consider: is the claim actually true?

To be continued

No comments: