Tuesday, January 13, 2009

Parsons Mathematical Thought: Sec. 50, Induction and impredicativity, continued

Suppose we help ourselves to the notion of a finite set, and say x is a number if (i) there is at least one finite set which contains x and if it contains Sy contains y, and (ii) every such finite set contains 0. This definition isn't impredicative in the strict Russellian sense (as Alexander George points out in his 'The imprecision of impredicativity'). Nor is it overtly impredicative in the extended sense covering the Nelson/Dummett/Parsons cases. We might argue that it is still covertly impredicative in the latter sense, if we think that elucidating the very notion of a finite set -- e.g. as one for which there is a natural which counts its members -- must in turn involve quantification over naturals. But is that right? This is where Feferman and Hellman enter the story. For, as Parsons remarks, they aim to offer in their theory EFSC a grounding for arithmetic in a theory of finite sets that is predicatively acceptable and that also explains the relevant idea of finiteness in a way that does not presuppose the notion of natural number. Though now things get a bit murky (and I think it would take us too far afield to pursue the discussion and further here). But Parsons's verdict is that

EFSC admits the existence of sets that are specified by quantification over all sets, and this assumption is used in proving the existence of an N-structure [i.e. a natural number structure]. For this reason, I don't think that ... EFSC can pass muster as strictly predicative.
This seems right, if I am following. It would seem, then, Parsons would still endorse the view that no explanation of the property natural number is in sight that is not impredicative in a broad sense -- where an explanation counts as impredicative in the broad sense if it is impredicative in Russell's sense, or in the Parsons sense, or invokes concepts whose explanation is in turn impredicative in one of those senses. But the question remains: what exactly is the significance of that broad claim if I am right that even e.g. a constructivist needn't always have a complaint about definitions which are impredicative in a non-Russellian way? It would have been good to have been told.

Back, though, to the question of induction. Dummett, to repeat, says that "the totality of natural numbers is characterised as one for which induction is valid with respect to any well-defined property'' including ones whose definitions "may contain quantifiers whose variables range over the totality characterised''. Likewise Nelson. Now, as a gloss on what happens in various formalized systems of arithmetic, that is perhaps unexceptionable. But does the totality of natural numbers have to be so characterized? Return to what I called the simplest explanation of the notion of the natural numbers, which says that (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). This explanation, Parsons argued, sustains induction for any well-defined property. But as we noted before, that argument leaves it wide open which are the well-definined properties. So it seems a further thought, going beyond what is given in the simplest explanation, to claim that any predicate involving first-order quantifications over the numbers is in fact well-defined. There are surely arithmeticians of finitist or constructivist inclinations, who fully understand the idea that the natural numbers are zero and its successors and nothing else, and understand (at least some) primitive recursive functions, but who resist the thought that we can understand predicates involving arbitrarily complex quantifications over the totality of numbers, since we are in general bereft of a way of determining in a finitistically/constructively acceptable way whether such a predicate applies to a given number. To put it in headline terms: it is a significant conceptual move to get from grasping PRA to grasping (first-order) PA -- we might say that it involves moving from treating the numbers as a potential infinity to treating them as a completed infinity -- and it wants an argument that someone who balks at the move has not grasped the property natural number.

How much arithmetic can we get it we do balk at the extra move and restrict induction to those predicates we have the resources to grasp in virtue of grasping what it is to be a natural number (plus at least addition and multiplication, say)? Well, arguably we can get at least as far as IΔ0, and Parsons talks a bit about this at the end of the present section. He says, incidentally, that such a theory is 'strictly predicative' -- but I take it that this is meant in a sense consistent with saying an explanation 'from outside' of what the theory is supposed to be about, i.e. the natural numbers, is necessarily impredicative in the broad sense. I won't pursue the details of the compressed discussion of IΔ0 here.

So where does all this get us? Crispin Wright has written
Ever since the concern first surfaced in the wake of the paradoxes, discussion of the issues surrounding impredicativity -- when, and under what assumptions, are what specific forms of impredicative characterizations and explanations acceptable -- has been signally tangled and inconclusive.
Indeed so! Given that tangled background, any discussion really ought to go more slowly and more explicitly than Parsons does. And I think we need to distinguish here grades of impredicativity in a way that Parsons doesn't do. Agree that in the broadest sense an explanation of the natural numbers is impredicative: but this doesn't mean that finitists or constructivists need get upset. Induction over predicates involving arbitrarily embedded quantifications over the numbers involves another grade of impredicativity, this time something the finitist or constructivist will indeed refuse to countenance. (I perhaps will return to these matters later: but for now, we must press on!)

No comments: