1

In his provocative article for this issue, Geoffrey Hellman has astutely attacked the philosophical grounds for predicativity from several angles. Though I am not now nor never have been a predicativist, I have to admit to being a sympathizer since I am an avowed anti-platonist, at least insofar as set theory is concerned, and I grant the natural numbers a position of primacy in our mathematical thought. Philosophically, the predicative position may be characterized as the restriction to that which is implicit in accepting the natural number structure. The subject has thus been of great interest to me and has periodically commanded much of my attention research-wise over the last forty years, especially as concerns its logical and mathematical potentialities. A caveat : a confirmed predicativist - if there be any such - would perhaps have stronger reasons than those marshalled here to defend the position on philosophical grounds.

2

In format, I shall follow Hellman's article section by section.

3

Let me begin with some amplifications of sec. 1, in which Hellman fairly set forth some of the main ideas of predicativity and relevant logical and mathematical results. Predicativity began with the rejection by Poincare and Russell of impredicative definitions, which involve quantification over a presumed "completed" totality of arbitrary sets.

4

On the face of it, such definitions are justified only by a thorough-going platonistic philosophy of mathematics. Impredicative definitions occur in the set-theoretical account of the real number system (a la Dedekind) where the fundamental least upper bound principle rests ultimately on quantification over a presumed totality of arbitrary subsets of the natural numbers. By contrast, predicatively acceptable definitions of sets are those that can be successively generated by quantification over previously accepted totalities. For Poincare, this included quantification over the natural numbers, which he accepted as basic. Russell, on the other hand, in pursuit of the revised logicist program, sought to define the natural numbers predicatively within ramified type theory, but his effort was compromised by assumption of the Axiom of Reducibility.

5

The modern logical analysis of predicativity given the natural numbers (stemming from a proposal due to Georg Kreisel) is that given by provability in an autonomous transfinite progression of ramified theories of sets (FEFERMAN, 1964). This is couched in classical logic and assumes the natural numbers N as given and treated as a completed totality. The language of ramification is used to meet the requirement that at each level a, sets are asserted to exist only via definitions in which quantification over N may be unrestricted but quantification over sets must be restricted to various levels (3 lower than a. The condition of autonomy requires that one may ascend to a level a only if the existence of a well-ordering of order type a has been established at some level (3 lower than a; this provability requirement is an essential modification of earlier accounts in terms only of ramified definability. As Hellman has recalled (sec. 1), Kurt Schiitte and I independently characterized the least non-autonomous ordinal for this progression of theories as a certain countable ordinal ro.2 Set-theoretically, the minimal model of this progression consists of the constructible sets up to ro, or their restrictions to sets of natural numbers if one considers only second-order formal systems for predicativity.

6

The redevelopment of mathematics under predicative strictures in practice is better represented logically in terms of unramified formal systems which are shown to be predicatively justified by their prooftheoretical reduction to the autonomous progression of ramified systems. The first substantial work on predicative foundations of analysis (where, as pointed out above, the set-theoretical account immediately leads to impredicative definitions) was carried out by Hermann Weyl in

7

Das Kontinuum (1918).3 He showed that all of the 19^Ih century analysis of (step-wise) continuous functions could just as well be done predicatively. In my (1988) I brought Weyl's work up to date with use of a system W of variable finite types; in it much of 20^th century functional analysis can also be developed. Surprisingly, the system W is of the same proof-theoretical strength as the system PA of Peano Arithmetic, which is just the base of the above progression of systems.4 Also, as explained there, it appears that all of scientifically applicable analysis can be formalized in W and hence rests on ultimately purely arithmetical foundations.5

8

In sec. 2, Hellman argues that the negative views (N1)-(N3) of the predicativist lead to limitative theses (LS), (LO) and (LE) whose acceptance is inconsistent with the predicativist stance. The claimed views (N1 )-(N3) are actually a mixed bag and are better replaced by the single stronger view :

9

(N)* Purported definitions of sets by reference to a totality of sets of which they are supposed to be a member are (as they stand) illegitimate.

10

Hellman asks on what deeper claim or principle such negative views rest : is it a form of nominalism (semantic, LS), or a matter of ontology (LO) or one of epistemology (LE)? My answer would be that it is by way of rejection of the set-theoretical platonistic ontology, and more specifically of that part of it which warrants reference to the supposed totality of arbitrary subsets of any infinite set, that one is led to an alternative definitionistic view of sets as the extensions of properties successively seen to be defined in a non-circular way, where two sets are taken to be extensionally the same if their definitions can be proved to be equivalent. I believe that accepting this view by way of informal motivation for the predicative position does not require the (ideal) predicativist to accept any of the given limitative theses. For the argument that such acceptance leads to inconsistency presumes - as Hellman does - the Feferman-Schutte characterization of predicative provability and definability described above. But the predicativist could not accept the form of this characterization in its use, at the outset, of the notion of arbitrary countable ordinal as given by arbitrary well-ordering relations in the natural numbers; to be such a relation on the face of it requires impredicative quantification over the presumed totality of subsets of the natural numbers. In other words, this is a non-starter.6

11

In sec. 3, Hellman in effect vitiates his own "jujitsu-like manoeuvres" to establish the supposed incoherence of the predicativist stance by pointing out that these contortions appeal to "the precise explications afforded by modern logic of such notions as 'the predicative universe', 'limit of predicativity', etc." He then rightly avoids incoherence by restating the motivating predicativist stance "in favor of a general expression of skepticism - or malaise, one might say - regarding the predominant platonistic practice of treating mathematical objects as mindindependent and statements about them as objectively true or false...". This is followed by a discussion of my own anti-platonism, which would be relevant only if I were to be regarded as the standard-bearer for predicativity. However, as an aside, let me address what he has to say about that. He points out that I am even an anti-platonist regarding the natural numbers but that I accept classical logic concerning arithmetic statements on the basis of the objectivity of truth values for them. My reason for doing so is that I regard the mind-dependent conception of the natural number sequence as intersubjectively robust, just like various other human conceptions, mathematical or otherwise. That is not an answer to "[w]hy doesn't the predicativist go all the way with intuitionism (or, at least, Bishop constructivism...)?" Indeed, an argument might be made that the logical characterization of predicativity should be based on intuitionistic reasoning; however, I have shown in my article (1979) that nothing is lost thereby, in the sense that the system obtained by dropping the law of excluded middle is of the same prooftheoretical strength as that with classical logic.

12

Hellman goes on in sec. 3 to ask whether the predicativist position is a stable one, if it does not go down the slippery slope to constructive mathematics, why it does not extend "along a slippery, if steeply ascending, slope - to full classical analysis." Aside from trying to struggle with this peculiar inversion of gravity,7 Hellman offers a vivid thought-experiment involving independently randomly decaying particles placed along the natural numbers that can turn on little lights, as a way to push us (predicativists) up that slope. The thought experiment is supposed to get us to accept talk about arbitrary "arrays" or "wholes" (aka subsets) of the natural numbers in terms of what lights are on in a given time period. I've not been able to decide whether Hellman is serious about this mix of physical and mathematical imagery, but in any case, it does not do what he wants it to do. At most, it makes plausible the concept of being a subset of the natural numbers regarded independently of how such may be defined, but it does not justify talk about the supposed totality of all subsets as a domain of quantification.

13

In the brief sec. 4, Hellman tosses in a moderate thesis (ME), according to which predicative mathematics is more secure than impredicative mathematics. He says this is almost tautological and even "cheerfully" acceptable to an arch-platonist. But if I were an arch-platonist I would be so unshaken in the security of my mathematics that I would not subscribe to (ME) simply because impredicative systems are much stronger prooftheoretically than predicative ones. In any case, Hellman asks us to ignore such moderate claims as (ME), since "it does not seem promising for articulating a distinctive predicativist philosophical position." On that we can agree, as the claim (ME) could equally well be applied to finitist and constructive mathematics in place of predicative mathematics.

14

To my mind, the most substantial challenges in Hellman's piece are those raised in the final sec. 5, but they are largely misdirected, since they are not specifically challenges to predicativity as a philosophical position but rather to various views I have advanced. To be sure, as I have said, there is a connection between those positions via the shared anti-platonistic stance, and there is some relevance of the logical work on predicativity, but I would like to stress that the following are my answers to the challenges rather than those of a mythical predicativist.

15

A number of points are raised in Hellman's sec. 5 and need to be adressed one by one; I have separated them as (a)-(f).

16

(a) Having dismissed the 'grand philosophical theses that he behind the work on predicativity, Hellman still finds philosophical interest in two aspects of that work itself.

17

The first is in helping to delineate "what rests on what" in mathematics.

18

He mentions, approvingly, my work showing that the system W suffices for the predicative development of substantial parts of classical and modem analysis, the body of which - by the proof-theoretical reduction of W to PA (Peano Arithmetic) - rests on purely arithmetical grounds. Of course I am pleased with the approbation, but the point should have been considered in a much more general context, as I have argued in my paper "What rests on what ? The proof-theoretic analysis of mathematics" (1993a). In it I pointed out that there are several different senses in which the question can be answered, some quite venerable in mathematics. But in pursuit of a relativized Hilbert program, proof theory has allowed one to give precise sense to a new sense which should be of philosophical interest. Namely, if formal systems T{ and T, are justifiedprima-facie by foundational frameworks Fj and F, respectively, and T, is shown to be proof-theoretically reducible to T2 then one has a partial foundational reduction ofFj to F,, and thence the body of mathematics M that can be formalized in T( is justified or secured on the grounds of the fraemework F2. A number of examples were given op. cit. of reduction of (i) infinitary to finitary systems, (ii) uncountably infinitary to countably infinitary ones, (iii) impredicative to predicative ones, and (iv) non-constructive to constructive ones.

19

(b) The second aspect of the logical work that Hellman finds of philosophical - though more controversial - interest is that concerning various indispensability arguments for accepting some body of mathematics. He mentions two such lines : on the one hand that advanced by Quine and Putnam according to which all and only that part of mathematics is justified that is scientifically applicable, and on the other, that advanced by Godel - and much more recently (Harvey) Friedman - which is supposed to justify the assumption of large cardinal axioms in view of their elementary consequences. After mentioning it, he sets the Quine-Putnam thesis aside, but in this respect he could have spelled out the relevance of the work on predicativity, again as a result of the reduction of W to PA and the verification that all current and prospective scientifically applicable mathematics can be formalized in W. As I have argued in my paper "Why a little bit goes a long way : Logical foundations of scientifically applicable mathematics" (1993), those results completely vitiate the substance of the Quine-Putnam indispensability arguments which are supposed to lay claim - more or less - to full Zermelo set theory.

20

(c) Prior to turning to the full-scale Godel-Friedman program, Hellman goes into Friedman's finite form FKT ("FFF" in Hellman's designation) of Kruskal's theorem on embeddings in infinite sequences of finite trees.

21

Friedman showed that FKT implies the consistency of a system ATR0 of proof-theoretical strength T0 and thus requires assumption of impredicative principles. I had criticized FKT on several grounds, the first that it did not arise naturally in the course of mathematical work but was "cooked up" for the specific purpose. In this respect, Hellman rightly cautions me (and us) to "[b]eware of an intentionalist fallacy !"

22

One should examine the mathematical content of statements such as FKT on their own merit. Indeed I have retreated on this to an extent, having written more recently on p. 406 of my part of the symposium "Does mathematics need new axioms ?" (Feferman, et al., 2000) as follows : Friedman's statement FKT independent of predicative S, and a somewhat stronger extension of Kruskal's theorem EKT independent of a system S involving co-iterated impredicativity,8 are of mathematical interest in that as mathematical facts they are each shown true by ordinary mathematical means, in a way understandable to mathematicians without invoking any mention of what axioms they depend on, or of any metamathematical notions; moreover, EKT was an important ingredient in the so-called Graph Minor Theorem of Robertson and Seymour mentioned by Hellman. This is certainly in contrast to the "cooked up" statements shown independent of rather general systems S in Godel's first incompleteness theorem, and the consistency statements Con(S) shown independent by the second incompleteness theorem, which are of definite metamathematical interest but not of mathematical interest in the usual sense. That FKT and EKT are shown to be independent of the relevant S by proving the consistency of S is, I agree, neither here nor there in respect to mathematical interest or naturality.

23

(d) In my view, the situation is quite different with respect to the latest work of Friedman in pursuit of the Godel program for the indispensability of new axioms of set theory in deriving finite combinatorial statements, in particular axioms positing the existence of very large cardinal numbers, or Large Cardinal Axioms (LCAS), which Hellman takes up next. The example from Boolean Relation Theory (BRT) drawn from Friedman's work concerns a Proposition (so designated by Hellman), call it (*), which asserts the existence of infinite sets A, B, C of natural numbers satisfying certain Boolean relations between them and their images fA, fB, gA, gB under given linearly expansive multivariate functions f and g. Friedman's Theorem quoted by Hellman is that (*) is provable in the system ZFC augmented by the LCA of the form (V/ie N)(MCn), where MCH expresses the existence of an ;;-Mahlo cardinal, but (*) is not provable in ZFC augmented by the scheme consisting of the MC; ifor each n e N (provided that system is consistent). Questions of mathematical naturality of the statement (*) aside,9 Hellman apparently agrees with my general criticism of such efforts to establish the indispensability of LCA's': what is shown to be indispensable is not the LCA in its own right as a first-class mathematical principle but rather the (1-) consistency of the system ZFC augmented by that LCA (cf. Feferman et al. 2000, p. 407).

24

(e) In this respect Hellman accuses me of a kind of double standard ("a certain irony") in my pointing out (since some time) that the undecidable statements produced by Godel and that underpin the undecidable mathematical results produced by Friedman and others follow from suitable Reflection Principles (R) which one ought to accept and that are metamathematical rather than mathematical in character. The point of using (R) and the like was rather to try to capture the idea in theoretical terms of what one ought to accept if one has accepted given notions and principles. Since formulating it initially in several ways in terms of a notion of reflective closure, I arrived in my paper (1996) at a rather general notion of the unfolding of schematically presented axiom systems that does not require metamathematical principles for its formulation. Here there is a direct relevance to predicativity : in my work with Thomas Strahm (2000) we have proved that the unfolding of a basic system of non-finitist arithmetic is equivalent in proof-theoretical strength to the ramified progression up to T0; this confirms the idea of predicativity as what is implicit in accepting the natural numbers as a completed totality. As announced in the abstract (2001) we have gone on to establish the proof-theoretical strength of the unfolding of a basic system of finitist arithmetic to be the same as that of PRA, Primitive Recursive Arithmetic, argued by Tait (1981) to be the limit of finitism.

25

And in my (1996) I have initiated the application of the idea of unfolding to a basic schematic system of set theory in order to yield large cardinal axioms of Mahlo type; that work is still in progress. This would spell out Godel's idea in his famous 1947 paper on "What is Cantor's continuum problem ?" that such axioms "show clearly, not only that the axiomatic system of set theory as known today is incomplete, but that it can be supplemented without arbitrariness by new axioms which are only the natural extension of those that have been set up so far" (GODEL, 1990, p. 182). All of this suggests the notion of unfolding as a natural generalization of both predicativity given the natural numbers and Godel's program for new axioms, and thus merits serious philosophical attention.

26

(f) In conclusion, in further support of Friedman's work on BRT, Hellman turns to the possible unifying "explanatory role" of new axioms originally advanced by Godel in his 1947 paper. As he says - and I agree completely - the jury is still out on BRT in this respect.10 Not mentioned by Hellman but perhaps more compelling in this direction is the striking work of the set theorists-Tony Martin, John Steel and Hugh Woodin among others - showing that the assumption of the existence of certain "large" large cardinals (i.e., those which, unlike cardinals of Mahlo type, are not consistent with the axiom of constructibility) leads to a "unification" of descriptive set theory in that "nice" results about Borel and analytic sets such as measurability, determinacy, etc., extend to the full projective hierarchy (cf. Steel's account of this work in his part of the symposium, Feferman et al. 2000). An essential difference from BRT is that for the set-theorists it is not the consistency but the very existence of the large cardinals in question that must be assumed. In any case, the analogy, also due to Godel, with the invocation in physics of highly theoretical "unobservables" in order to explain certain phenomena, is not at all persuasive, since in the case of BRT and the descriptive set theory of the projective hierarchy, the phenomena were not there to be obsei-ved in advance of their proposed "explanations" in terms of suitable large cardinal axioms.

27

It may well be, as Hellman says in his conclusion, that there is no natural philosophical or mathematical boundary to what is required for "genuine mathematics"; certainly predicativity does not supply such.

28

But the two examples discussed above of programs for demonstrating the necessity of large cardinals force us, qua philosophers, to confront the question : what exactly counts as genuine mathematics and why ?

Solomon Feferman

Stanford University

Notes

[ 1] As Hellman has explained in (the initial footnote to) his article, an earlier version of it was presented at a symposium, "Predicativity : Problems and Prospects'", for a joint APA-ASL meeting held in Seattle, March 28,2002, for which Jeremy Avigad and I were the cosymposiasts. Avigad's presentation dealt with questions concerning the mathematical significance of predicativity. Mine, on the other hand, dealt with the idea of predicativity in its historical development and particularly its logical analysis; a write-up of that is to appear as a chapter in the volume. Handbook of the Philosophy of Mathematics and Logic, being edited by Stewart Shapiro. Given the limited space available here for my response to Hellman's article, the reader will have to look to that for a fuller appreciation of the issues involved. For the reader who can't wait, a draft of the chapter is to be found at the website <http ://math stanford.edu/-feferman/papers/predicativity.pdf>.

[ 2] r is by definition the least ordinal y=<p ,(0) in the Veblen hierarchy of critical functions (pa of ordinals, where cp()(x)=co^; and for each a, (pa enumerates the common fixed points of all <p„ for (3 < a. Note by way of comparison that the Cantor ordinal e0=tp,(0), which measures the proof-theoretical strength of the system PA of Peano Arithmetic, is much smaller than r„.

[ 3] See Feferman (1988).

[ 4] The stated result on W was established in Feferman and Jager (1993 and 1996).

[ 5] See also Feferman (1993).

[ 6] The argument that the characterization of predicativity requnes one to go beyond predicative notions and principles is a standard one and the argument in response is also standard. It does not depend essentially on the initial characterization via transfinite progressions of theoiies Alternative characterizations of predicativity without the explicit or implicit use of ordinals have been given in Feferman (1979) and, more recently. Feferman and Strahm (2000); the reason why the predicativist cannot accept those takes a different line in those cases. It is quite a different matter whether the ideal predicativist would accept each stage (short of ro) of the systems providing these characterizations, in other words whether, perhaps, they go too far. See my (1979) for further discussion of that issue.

[ 7] In the words of the squibs in the New Yorker magazine : "Block that metaphor !"

[ 8] This is the system usually labelled FI'j-CA, which, though it involves iterated impredicativity, on the one hand is a relatively weak subsystem of full second order arithmetic, and on the other is known to be justified through the proof-theoretical woik of W. Buchholz and W. Pohlers by a constructive system of co-iterated inductive definitions, a system which is among those that I accept and that go far beyond the predicative ones

[ 9] I am made suspicious in that respect by the fact that (*) is strangely unrobust in that - as shown by Friedman and mentioned by Hellman - any alteration of the pattern of letters A. B, C in its statement leads to a statement that is provable in a finitanly reducible system RCA().

[ 10] Friedman argues that the mathematical community will eventually be forced to accept large cardinal axioms as a result of his work on BRT; cf. his part in the symposium Feferman et al. (2000).