JAAKKO HINTIKKA

A REVOLUTION IN THE FOUNDATIONS OF MATHEMATICS?

1. FIRST-ORDER LOGIC AND ITS SHORTCOMINGS The standard contemporary view of the foundations of mathematics and of the role of logic in it is well known and firmly entrenched. The ground floor of the edifice of mathematics is on this view our basic logic, that is to say first-order logic, a.k.a. quantification theory or lower predicate calculus. It has various desirable features, such as completeness, compactness, L¨owenheim–Skolem property and the validity of the separation theorem. Indeed, it is the strongest possible logic in the sense of abstract (model-theoretical) logic that has the pleasant properties of compactness and L¨owenheim–Skolem property, assuming only the usual behavior of propositional connectives plus a few plausible structural properties. This is what the famous theorem of Lindstr¨om’s shows.1 This theorem seems to assign a special position to ordinary first-order logic. At the same time, it is a kind of impossibility theorem, showing that we cannot hope to strengthen first-order logic without losing some of its desirable properties. First-order logic was first formulated explicitly by Frege as a part of his more comprehensive Begriffsschrift. Frege had to go further, however. His logic is not first-order, but higher-order.2 In other words, Frege’s logic allows quantification not only over individuals (particulars), but also over higher-order entities, such as functions and other concepts applying to individuals. The problems caused by this transgression beyond first-order concepts will be discussed later in this paper. It is sometimes said that the idea of a freestanding first-order logic was not known to Frege and that it crystallized only later, for the first time apparently in Hilbert’s and Ackermann’s 1928 textbook (Moore 1988). Maybe so. But even if Frege should have entertained the idea of pure first-order logic, he would have had plenty of good prima facie reasons to go beyond what is in our days known as first-order logic. The most basic reason is that ordinary first-order logic does not suffice for mathematics. Another reason is that it is not even self-sufficient. The first of these two failures is illustrated by the fact that several of the most basic concepts of

Synthese 111: 155–170, 1997. c 1997 Kluwer Academic Publishers. Printed in the Netherlands.

156

JAAKKO HINTIKKA

all mathematics cannot be expressed by means of ordinary first-order logic. Perhaps the most fundamental concept in the foundations of mathematics, the concept of equicardinality, cannot be expressed in first-order terms. When do the extensions of two concepts A and B have the same cardinality? If and only if there are functions f and (its inverse) g such that (1)

(8x)(8z)((A(x)  B(f(x))& (B(z)  A(g(z)))&((z = f(x)) $ (x = g(z))))

Here we cannot dispense with the quantification over the functions f and g. Other concepts that likewise cannot be expressed in first-order terms include infinity, continuity in the sense of general topology, mathematical induction, etc. No wonder that Frege resorted to higher-order logic in his attempted reduction of mathematics to logic. For one thing, he needed the concept of equicardinality for his definition of number. For another thing, first-order languages are not self-sufficient in the sense that the model theory of a first-order language or first-order axiom system cannot be formulated in first-order terms. The most central concept of all model theory (logical semantics), the concept of truth, can be defined for first-order languages along the lines Tarski staked out (Tarski 1956). Alas, these lines lead us away from a first-order language to the corresponding second-order language. A Tarski-type truth predicate for a first-order language is a second-order predicate asserting the existence of a suitable kind of valuation, that is, of a function from the expressions of the language to their potential values in the given model.

2. TRADITIONAL PICTURE OF THE FOUNDATIONS OF MATHEMATICS Hence we apparently need higher-order logic in our mathematical theorizing. But higher-order logic is not only inevitably incomplete. It is entangled with all the problems with the existence of higher-order entities like sets and functions. Hence it might seem only fair to fess up and admit that Quine is right in calling higher-order logic set theory in sheep’s clothing. The proper framework for mathematical theorizing therefore appears to be set theory – a view which is currently shared by many, perhaps most, mathematicians. Because in set theory we need axioms over and above those of first-order logic, it is usually considered a mathematical rather than logical theory.

THE FOUNDATIONS OF MATHEMATICS

157

The study of set theory is usually conducted in the same way as that of any other mathematical theory, that is to say, in the form of an axiomatic theory using first-order logic. Higher-order logic is not used, for the whole idea of axiomatic set theory is to dispense with it. Instead, the only logic used to regulate the consequences of set-theoretical axioms is the ordinary first-order logic, once again reflecting the dogma that this logic is our natural basic logic. First-order axiomatizations of nontrivial mathematical theories are nevertheless inevitably incomplete, no matter whether set theory is being resorted to or not.3 For one thing, first-order set theories cannot do the same job as higher-order logics in one important respect. No explicit firstorder axiomatization can capture the intended standard interpretation of higher-order quantifiers. In the (ordinary first-order) axiomatization of set theory, there will inevitably be models in which e.g. functions variables (like the f , g of (1)) do not range over literally all extensionally possible functions, but only some specified subset of the set of all such functions. But this means that formulas like (1) cannot quite do the job they were drafted to do in all models of the underlying language. For instance, the extensions of A(x) and B(x) might be equinumerous, and yet there might not exist any functions f , g (in the sense of the first-order theory) doing the one-to-one correlation expressed by (1). Now the first-order character of the usual axiomatizations of set theory means that set theory cannot capture the standard interpretation of higherorder quantifiers.4 Model-theoretically speaking, any first-order axiomatization of set theory admits of nonstandard models which violate the standard interpretation of set theory thought of as a substitute for higher-order logic. Moreover, since first-order logic cannot even capture the principle of mathematical induction, even first-order theories such elementary mathematical theories as arithmetic are bound to be incomplete, as G¨odel showed in 1931 (G¨odel 1986a). This holds of course also when elementary number theory is reconstructed within first-order axiomatic set theory. Thus the usual line of thought results in a two-tier model of the foundations of mathematics. The ground floor according to this view is first-order logic, which is semantically complete but not strong enough to cope with actual mathematical conceptualizations. The next floor is set theory and/or higher-order logic. On this level, we can express the basic mathematical concepts, but we cannot hope to achieve completeness. Nevertheless, axiomatic set theory is in this view the best general framework for mathematical theorizing that we have available to us.

158

JAAKKO HINTIKKA

On this view, the main foundational problems can be located They pertain to the higher levels of the structure I have described. In other words, practically all the difficulties in the foundations of mathematics seem to lie in formulating complete mathematical theories. The task of studying the logical consequences of axiomatic theories can apparently take place by means of a simple logic that can be mastered once and for all in the sense of admitting a semantically complete axiomatization, that is, a recursive enumeration of all valid formulas. Even though on this view logic is unproblematic, its scope is severely limited. One might even say that the picture I have painted is overshadowed by several impossibility results, including G¨odel’s incompleteness theorem, Tarski’s result that truth can be defined for a first-order theory only in a stronger theory, Lindstr¨om’s theorem, and the impossibility of expressing notions like equicardinality on the first-order level. This generally accepted picture has one thing against it. It is wrong. It rests on a woefully inadequate analysis of the entire problem situation in the foundations of logic and mathematics. It is based on an unnecessarily restrictive idea of what our basic logic is like. It relies on an ambiguous and consequently misleading picture of what completeness means. Moreover, and perhaps most fundamentally, it relies on an unclear idea what the ends of mathematical theorizing are in the first place. I will explain these four points in the rest of this paper.

3. INDEPENDENCE-FRIENDLY FIRST-ORDER LOGIC To take the first point first, whether we credit the ordinary first-order logic to Frege or to Hilbert and Ackermann, it does not do the job fully adequately that it was calculated to do.5 For what is first-order logic supposed to do? It is supposed to be the logic of quantifiers. Now the source of the expressive power of quantifiers is their interplay. Quantifiers cannot be adequately characterized as higher-order predicates as Frege thought, or as “ranging over” a class of values, as most philosophers seem to think in these days. Quantification theory is essentially a study of the interplay of different quantifiers, their dependencies and independencies. And the construal of quantifiers as higher-order predicates cannot do justice to this interplay. It has turned out that Frege’s approach to logic, including the formation rules for the first-order fragment of his total logic, rules out certain combinatorially possible and easily interpretable patterns of dependence and independence between quantifiers. The simplest instances of a pattern not expressible in ordinary first-order logic are the so-called Henkin quan-

THE FOUNDATIONS OF MATHEMATICS

159

tifier formulas expressible as the following two-dimensional “branching quantifier” formula: (2)

(8x)(9y) (8z)(9u)

> S[x; y; z; u]

Here the truth making value of y depends only on x and the similar value of u only on z. Hence (3) is equivalent to the following second-order formula (3)

(9f)(9g)(8x)(8z)S[x; f(x); z; g(z)]

which is easily seen to be irreducible to any ordinary first-order formula. In practice, it is simplest to introduce a special symbol to indicate the independence of a quantifier, say (9y ), of another one, say (8z ), of which it otherwise depends on, by writing it (9y=8z ). Then (2) = (3) can be written on the first-order level linearly as (4)

(8x)(8z)(9y=8z)(9u=8x)S[x; y; z; u]

When this slash notation is extended also to propositional connectives, we obtain what has been called independence-friendly (IF) first-order logic (Hintikka 1995a; Hintikka 1996, Chaps. 3, 7). This logic has a better claim to be our true basic logic than ordinary first-order logic, in that it is free from the needless and arbitrary restrictions that beset ordinary first-order logic. IF first-order logic has several of the same desirable metalogical properties as its received counterpart. It is compact and has the L¨owenheim–Skolem property. Separation theorem holds in it in an even stronger form than before. The reason it does not violate Lindstr¨om’s Theorem is that the law of excluded middle fails in IF first-order logic, which it is one of the apparently minor premises of Lindstr¨om’s Theorem but which turns out to be crucially important for its applicability. Both ordinary and IF first-order logic admit of a simple translation to the corresponding second-order language. The translation t(S) of a sentence S simply asserts that its Skolem functions exist. In other words, if S is of the form S[(9x)S1 [x]], where (9x)S1 [x] occurs within the scope of the universal quantifiers (8y1 ), (8y2 ) : : : , it is replaced by

(9f)S[S1[f(y1; y2; : : :)]] where f is a new function symbol expressing one of the Skolem functions of S . (It is of course assumed that S is in the negation normal form, i.e.,

160

JAAKKO HINTIKKA

that all its negation signs are prefixed to atomic sentences and that the only propositional connectives in S are &, _.) In order to reach t(S), this elimination of first-order existential quantifiers must be applied to all of them. likewise, whenever S is of the form

S[(S1 _ S2)] where (S1 _ S2) occurs within the scope of (8y1 ), (8y2 ), : : : , it is replaced by

S[((S1 & g(y1 ; y2 ; : : :) = 0) _ (S2&g(y1 ; y2 ; : : :) 6= 0)]: In other words we must also associate a “Skolem function” to each disjunction dependent on universal quantifiers. It is immediately seen that the translation t(S) belongs to what is known as the 11 fragment of the second-order language in question, that is, its only second-order ingredient is an initial sequence of second-order existential quantifiers. The remarkable thing here is that this fragment can be translated back into the corresponding IF first-order language. The failure of the law of excluded middle is an inevitable consequence of the most obvious and most natural semantical rules for IF logic (Hintikka 1996, Chap. 7). Admittedly, I can extend the IF first-order logic by introducing contradictory negation by fiat. But then it turns out that this contradictory negation : cannot be given any semantical rules except for saying that it is the contradictory negation. As a consequence, it can occur only sentence-initially (or fronting an atomic formula). In the resulting extended IF first-order logic, most of the “nice” metatheorems listed above fail. One of the most remarkable things about IF first-order logic is that it extends what can be done in the foundations of mathematics by purely logical means. Consider for instance, the following statement

(5)

(8x)(8z)(9y=8z)(9u=8x)((Ax)  B(y))& (B(z)  A(u))&((y = z) ! (u = x))

The second-order translation of (5) is

(6)

(9f)(9g)(8x)(8z)((A(x)  B(f(x)))& (B(z)  A(g(z)))&((z = f(x)) ! (x = g(z))))

THE FOUNDATIONS OF MATHEMATICS

161

A comparison with (1) shows that (6) in fact expresses the equicardinality of the extensions of A(x);and B(x). At the same time, (5) is perfectly first-order. Its quantifiers “range over” individuals, not over higher-order entities. It expresses a combinatorial fact about the model (“world”) in question. It could even be expressed by merely revising the received scope conventions of first-order logic. Indeed, we could reach the entire IF firstorder language in this way, merely by allowing that the scope associated with a quantifier need not be a continuous segment of the formula in question. For instance, the Henkin quantifier formula (2) (or (4)) could then be written as

(8x)f(9y)(8z)g(9u)fS[x; y; z; y]g where the brackets fg indicate the scope of (8x). (7)

Consider next the statement (8)

(8x)(8z)(9y=8z)(9u=8x)((y 6= x)&(u 6= z)& ((x = z) ! (y = u)))

This is easily seen to be equivalent to (9)

(9f)(8x)(8z)((f(x) 6= x)&((x = z) ! (f(x) = f(z))))

which clearly is true if and only if the universe of discourse is infinite (or empty). Likewise, the topological notion of continuity can be expressed by means of IF first-order logic, as can be several other basic mathematical concepts that could not be expressed in terms of ordinary first-order logic. In extended IF first-order logic, even more concepts become expressible. They include mathematical induction, well-ordering, power set, etc. One might nevertheless doubt the power of IF first-order logic as a tool in mathematics. It corresponds after all only to a small fragment of secondorder logic, viz. to its 11 fragment. Even extended IF first-order logic does not extend any further than to the 11 [ 11 fragment of second-order logic. Neither one goes beyond second-order logic in contradistinction from a full higher-order logic. I will return later to this apparent restriction. 4. DIFFERENT KINDS OF COMPLETENESS AND INCOMPLETENESS In any case, IF first-order logic extends significantly the range of what logic can do in the foundations of mathematics. But it seems to have an important

162

JAAKKO HINTIKKA

shortcoming: It is incomplete. It is impossible to give a list of axioms from which all the valid formulas of IF first-order logic can be derived by purely formal rules. Or, to speak the language of mathematical logicians, the set of all valid formulas of IF first-order logic is not recursively enumerable. Far from being a defect, however, this feature of IF first-order logic can be turned into a forceful reminder of the fact that the notion of completeness traditionally used in the foundations of mathematics is a mess, albeit perhaps not a hopeless mess. If the reader has found it hard to grasp what is meant by different references to completeness and incompleteness earlier in this paper, he or she has had a good reason to feel at sea. As I have pointed out on an earlier occasion (Hintikka; 1989, 1996, Chap. 5), there are at least three entirely different notions of completeness and incompleteness. They even apply to different kinds of theories: (i) Descriptive completeness applies to nonlogical axiom systems. It means that the models of the system include all and only intended models. This is a model-theoretical notion in the sense that only the notions of truth and validity are involved in it, but not any axiomatization of logic. (ii) Semantic completeness is a property of a so-called axiomatization of some part of logic. It says that the axiomatization in question effects a recursive enumeration of all valid formulas. (iii) Deductive completeness is a property of a nonlogical axiom system together with an axiomatization of the underlying logic. It says that from the axioms of this system one can logically prove either S or  S for each sentence S of the language in question. The drastic differences between these notions can be illustrated by relaxing our distinctions to G¨odel’s first incompleteness theorem. The theorem establishes the incompleteness of elementary (first-order) arithmetic, but in what sense? The answer is clear. G¨odel showed the deductive incompleteness of elementary arithmetic. But this is not the only incompleteness in town, and it concerns more the computational manipulability of proofs in first-order logic than its power to capture the right structures as its models. This latter power is at issue in descriptive completeness and incompleteness, not in deductive ones. So the sixty-four-thousand-dollar question becomes: Does G¨odel’s result entail the descriptive incompleteness of arithmetic? A closer examination shows that it does so only if the underlying logic is semantically complete. Of course, the logic G¨odel was relying on, ordinary first-order logic, had just been proved complete by G¨odel himself. But there is nothing in G¨odel’s result that precludes the possibility that by using some other kind of logic, which would have to be semantically incomplete, we could formulate a descriptively complete axiomatization of elementary arithmetic.

THE FOUNDATIONS OF MATHEMATICS

163

This is one of the many directions in which IF logic opens new possibilities. Its semantical incompleteness turns out to be a hidden asset, in that it might open new possibilities of formulating descriptively complete theories. Actually, it turns out that although unextended IF first-order logic does not allow a complete axiomatization of elementary number theory, extended IF first-order logic does so. Indeed, one way of obtaining a descriptively complete axiomatization is as follows: Let ' be the sentence

(9z)[(8x)(8y)('11 (_=8y)'12 )(_=8x)('21 (_=8y)'22 )] where

Let

'11 : :(x = y)

'12 : :(x = 0)

'21 : :(y = z)

22 : :(x = y)&:(y = f(x))

be the conjunction of the sentence s

(8x):(f(x) = 0); (8x)(8y)(f(x) = f(y)  x = y); (8x)(x 6= 0  (9y)(f(y) = x)): It has been shown by Sandu and V¨aa¨ n¨anen that M j= (' & ) iff M is a non-standard model of arithmetic (Sandu and V¨aa¨ n¨anen 1992). Hence M j= :(' & ) (where : is contradictory negation) iff M is the standard model. (I owe this observation to Gabriel Sandu.)

5. AXIOMATIZING MATHEMATICAL THEORIES This does not yet show anything about the prospects of formulating descriptively complete axiomatic theories by means of IF logic in general. This matter can be put into a clear perspective by noting that practically all usual mathematical theories admit of a descriptively complete axiomatization in higher-order logic. There are, for instance, scarcely any major unsolved problems in mathematics that cannot be expressed faithfully in terms of second-order or higher-order logic (cf. Shapiro 1991). This is possible because higher-order logics are semantically incomplete. This descriptive completeness is nevertheless bought at a very high price. This price is not the loss of semantical completeness but the vexing problems concerning set existence and more generally the existence of

164

JAAKKO HINTIKKA

higher-order entities that are inevitable in higher-order logic. These difficulties are the justification of branding higher-order logic “set theory in sheeps’ clothing”. For it is in set theory that the questions of set existence come to a head. These problems are often thought of as being mainly about how to avoid paradoxes in making existence assumptions in set theory. In reality, the really puzzling difficulties in set theory concern the formulation of sufficiently strong assumptions of set existence, as will be emphasized below in connection with the requirement of standard interpretation. As a consequence of the haunting difficulties, it becomes important to inquire whether descriptively complete axiomatizations for mathematical theories can be formulated by means of a suitable first-order logic, which of course has to be semantically incomplete.6 Here I can turn an old confusion into a successful strategy. In the light of hindsight it can be said that Frege and Russell dealt – or tried to deal – with higher-order logics as if they were many-sorted first-order logics, with each type constituting a separate “sort”. The interrelations of different sorts can be handled in first-order terms. So what did Frege and Russell miss? What they missed was the intended standard interpretation of higher-order quantifiers. Standardness is here understood in Henkin’s sense, as a requirement that bindable variables of any given type range over all the extensionally possible sets of entities of the appropriate lower type (Henkin 1950; Hintikka 1995a). For instance, set variables range standardly over the entire power set of the domain, that is, all extensionally possible sets, and not only over sets that e.g. exist in the sense of some set theory. Likewise, function variables range over what are sometimes called all arbitrary functions, relation variables over “relations in extension”, as Russell called them, and so on. Standardness cannot be enforced by first-order means, for instance through first-order axiomatic set theory, as is illustrated by the so-called Skolem paradox. Because of this failure of first-order logic to capture the standard interpretation, dealing with higher-order logic as a many-sorted first-order logic cannot ever succeed completely. As was spelled out by Ramsey (1931), many of the shortcomings of Russell’s and Whitehead’s Principia can be traced to their failure to countenance the standard interpretation of higher-order quantifiers. What is remarkable here is that the many-sorted first-order treatment almost succeeds. For the only thing in higher-order theories which cannot be captured by means of ordinary (many-sorted) first-order logic is precisely the requirement that for each extensionally possible collection of lower-type entities there corresponds an entity of the appropriate higher type. This point can be illustrated by reference to what happens in general

THE FOUNDATIONS OF MATHEMATICS

165

topology (Kelley 1955). There all of the most elementary concepts can be formulated in terms of ordinary first-order quantification over points on the one hand and sets on the other hand. This includes such concepts as base, closure, openness, etc. But when we proceed further, at some point we begin to need the assumption that quantification over, say, the subsets of a given set really means quantification over all the extensionally possible subsets. One place where this is likely to happen is in connection with the concept of connectedness. Obviously, the missing standardness requirements can be formulated quite simply (cf. Hintikka 1996, Chap. 9). For each type (higher than that of individuals and n-tuples of individuals), it suffices to require that it contains representatives of all the sets of entities of the appropriate lower type. And such a requirement can be expressed by 11 second-order statements. We have no reason to resort to any higher-type conceptualizations for the purposes of the sortal reconstruction of higher-order logic and higherorder theories. We do not need any more complex second-order formulas, either. With a modicum of stage-setting, all such 11 statements can even be integrated into one single 11 statement. These simple observations have striking consequences. They imply among other things that each mathematical theory that can be formulated by means of higher-order logic can be construed as a 11 theory. The set of structures that the given higher-order theory can capture as the set of its models can be captured by a 11 theory, albeit imbedded in the additional structure which the many-sortal reconstruction introduces. In this sense, 11 theories are all that is needed in ordinary mathematics. Indeed, there is a sense in which the basic form of mathematical reasoning viz. mathematical induction, formulated generally as the closure of a certain set under some mathematical operations belongs to 11 logic and hence to extended IF first-order logic. For it was shown by Moschovakis (1974) that any such inductive theory is equivalent to a 11 sentence. But each such 11 theory can be translated so as to become a theory expressed in extended IF first-order logic. Hence there is a sense in which all ordinary mathematics can be reduced to extended IF first-order logic. Moreover, in the many-sorted first-order reconstruction of a higherorder theory, all the putative theorems can obviously be expressed as ordinary first-order statements. The question of the status of such a putative theorem T in an axiom system X thus becomes a question concerning the validity of

(X  T) where X is 11 and T first-order. But that means that (10) is itself 11 . Hence (10)

it has a translation in IF first-order logic. Hence there is a sense in which

166

JAAKKO HINTIKKA

every problem of ordinary mathematics is equivalent with the problem of validity for a sentence of IF first-order logic. In the sense that appears from these remarks, IF first-order logic is the only logic that is in principle needed in ordinary mathematics. I am not suggesting for a moment that IF first-order logic is a practical framework for doing mathematics. For such purposes, a judicious use of second-order logic, typically restricted to 11 and 11 conceptualizations, seems to be the best bet. In practice, the upshot would probably be something rather like general topology (Kelley 1955). The main advantages of my reduction of mathematical theories to IF first-order level are philosophical and theoretical. The main payoff is a complete liberation of mathematical theorizing from all problems of set existence and of all problems concerning the existence of higher-order entities in general. The question of the validity of a sentence of IF first-order logic is a purely combinatorial one: It concerns the possibility or impossibility of different structures of individuals (particulars). It is nominalistic in Quine’s sense. It is to such combinatorial problems that I am reducing all questions of theoremhood in mathematical theories. This is a tremendous advantage in principle, for the problems of set existence are notoriously the most confused and confusing ones in the foundations of mathematics. 6. IF FIRST-ORDER LOGIC IS SELF-APPLICABLE MODEL-THEORETICALLY So far, I have not said anything of the second massive reason why ordinary first-order logic has not been thought of as a self-sufficient foundation for mathematical reasoning. This reason is that the model theory of ordinary first-order logic cannot be done by means of itself. The crucial concept of all model theory is the concept of truth (truth in a model), and it was noted earlier that for Tarski-type truth definitions we need second-order concepts. In this respect, too, IF first-order logic puts things in a new perspective. The result has been investigated in some detail elsewhere (cf. Hintikka 1995, Chap. 6). Suffice it here to indicate only the most general features of the situation. Both Tarski-type truth-predicates for a given finite first-order language and the game-theoretical ones that are in many ways superior to the Tarskian ones can be expressed as 11 statements in the corresponding second-order language. This holds also for truth-definitions for an (unextended) IF first-order language. But such 11 statements can be translated back into the correlated IF first-order language. In such a language we therefore can formulate a truth-predicate for itself. Paradoxes are avoided because of the inevitable failure of the law

THE FOUNDATIONS OF MATHEMATICS

167

of excluded middle in IF first-order logic (Hintikka 1996, Chap. 7). This failure creates the truth-value gaps that are needed to avoid a contradiction. In extended IF first-order logic we have a contradictory negation present. However, it can occur only sentence-initially. This makes it impossible to apply the diagonal lemma so as to create a liar-type sentence that would give rise to a contradiction. Truth-predicates are not all that there is to the model theory of a language or a theory. However, their possibility is an eloquent indication that we do not need set theory or higher-order logic for the main ingredients of a model theory of a given first-order theory. Furthermore, it is easily seen that many other familiar notions of model theory can be formulated in terms of a (possibly extended) IF first-order language.

7. A NEW PERSPECTIVE ON THE FOUNDATIONS OF MATHEMATICS The total picture of mathematical thinking that is suggested by these results differs sharply from the usual one. The core of mathematical thinking is not set theoretical. We can in principle dispense with set-theoretical assumptions and concepts altogether. Instead, mathematical thinking can – and perhaps should – be thought of as combinatorial, dealing with the structures of particular objects, especially with questions as to which configurations of individuals are possible and impossible. These are essentially the same kinds of questions or are dealt with in received first-order logic. These results might in one respect seem too good, or perhaps too simple, to be true. If all of ordinary mathematics can be done in extended IF firstorder logic or, equivalently, in the 11 [ 11 fragment of second-order logic, what use and what interest does the rest of higher-order logic have? Surely it has some content and use beyond its simplest special case. I am not denying that higher-order logic has uses beyond the 11 [ 11 case. But the crucial question is: What kind of use? By and large, logic has two kinds of uses in its applications, especially in mathematics (Hintikka 1996, Chap. 1). They can be characterized as follows: (a) Descriptive use. This is the contribution of logic to the specification of the kind of structure or structures that a mathematician or a scientist wants to study. One’s aim in this direction can for instance be to formulate a descriptively complete axiom system. An example might be offered e.g. by the use of quantifiers and other logical constants in the axioms of a mathematical or scientific theory. The descriptive function of logic could and perhaps should be called its theoretical function.

168

JAAKKO HINTIKKA

(b) Deductive use. In this employment, logical concepts are used to study valid inferential relationships between propositions. This function might also be called the computational or explicative function of logic in axiomatic theories. What has been seen is that the task (a) can typically be performed by logic already on the first-order level. But from this it does not follow that the deductive task can be so performed. Indeed, it can be seen that the deductive task is awkward to fulfil as soon as we go beyond ordinary first-order logic. For what a logician would like to do is to express in his or her language the proposition that says that if S1 is true, then S2 is true. In ordinary propositional logic, this is expressed by (11)

(S1  S2)

But in IF first-order logic (11) does not semantically speaking say that S2 is true if S1 is. What it says is that either S1 is false or S2 is true. Since in IF first-order logic there are propositions that are neither true nor false, this is an unnecessarily strong requirement. What is needed in the study of logical inference is a statement whose truth authorizes us to infer the truth of S2 from the truth of S1 . Such a statement can be formulated in higher-order terms. Expressed in game-theoretical jargon it will say that there is an effective (recursive) functional  which from a winning verifier’s strategy ' in the game S1[', ] associated with S1 yields a winning verifier’s strategy (') in the game S2 [', ] associated with S2 (Hintikka 1993). Winning strategies are in each case characterized by the fact that they result in a win even when one’s opponent is aware of them. The possibility of infering the truth of S2 from the truth of S1 will thus be expressible by (12)

(9)((9')(8 )S1 ['; ]  (8)S2 [('); ])

However, it is natural to require also that the knowledge of a strategy falsifying S2 should enable us to find a strategy falsifying S1 . This is captured by changing (12) into (13)

(9)(9 )(8')(8)(S1 ['; ('; ]  S2[('); ])

which is G¨odel’s functional interpretation for conditionals (G¨odel 1986b). It can be seen that (12) is of a higher order (type) than S1 or S2 . When conditionals are nested in a sentence, as we might very well want to nest them for purposes of inference, we are pushed to even higher types. What this means is that for inferential and deductive purposes, there can be plenty of reasons to use higher-order logics. The overall picture of the foundations of mathematics which we thus arrive at is almost diametrically opposite to the traditional one, explained above. The descriptive,

THE FOUNDATIONS OF MATHEMATICS

169

that is, model-specifying tasks in mathematics can be accomplished by means of relatively elementary (first-order) logic. These descriptive tasks are paramount on the level of theorizing, be this theorizing mathematical, scientific or philosophical. It is the inferential, deductive and computational aspects of the task of a mathematician that force us to consider increasingly higher-order logics and draft them to our service. What these computational aspects amount to is to elicit consequences of a theory which has already been formulated concerning a class of structures (models) which already have been captured by the theory, assuming of course descriptive completeness. Hence the use of higher-order logics belongs to the technology of logic rather than its theory. Obviously neither the descriptive nor the deductive task of logic should be neglected. In our day and age, which is overwhelmingly the age of computers and computing, equally obviously it is the descriptive and theoretical function that is in danger of being neglected.7

NOTES 1

See Per Lindstr¨om, (1969), pp. 1–11. The most accessible formulation of his result is found in H. D. Ebbinghaus, J. Flum and W. Thomas, 1984, chapter 12. 2 An important qualification needed here is that Frege adopted a nonstandard interpretation (in Henkin’s sense, see Note 4 below and Henkin 1950), which means that his higher-order logic could be dealt with like a many-sorted first-order logic. See Jaakko Hintikka and Gabriel Sandu. 3 Indeed, if a first-order theory is deductively incomplete, then it is also descriptively incomplete as pointed out. On the other side, if a theory is descriptively complete, in the sense of e.g. characterizing up to isomorphism the standard model of arithmetic, then the theory is semantically incomplete, hence it cannot be a first-order theory. This follows from facts proved in Jon Barwise and S. Feferman (1985). 4 For the standard vs. nonstandard distinction, see Jaakko Hintikka (1995a), pp. 21–44. 5 With the following, cf. Jaakko Hintikka (1996), chapters 3–4 as well as “A revolution in logic?” (forthcoming). 6 By the results mentioned at the end of Section 4 above, if we have a descriptively complete axiomatization of a non-trivial mathematical theory, the theory must be semantically incomplete, hence it cannot be an ordinary first-order theory. (Of course it can be an IF first-order theory.) 7 In working on this paper, I have greatly profited from the advice of Dr. Gabriel Sandu.

REFERENCES Barwise, J. and S. Feferman: 1985, Model-Theoretic Logics, Springer-Verlag, New York. Ebbinghaus, H. D., J. Flum, and W. Thomas: 1984, Mathematical Logic, Springer-Verlag, New York.

170

JAAKKO HINTIKKA

¨ G¨odel, K.: 1986a, ‘Uber formal unentscheindbare S¨atze der Principia Mathematica und verwandter Systeme’, in K. G¨odel (ed.), Collected Works, Vol. 1, Oxford University Press, New York, pp. 144–195. G¨odel, K.: 1986b, Collected Works, Vol. 2, Oxford University Press, New York. Henkin, L.: 1950, ‘Completeness in the Theory of Types’, Journal of Symbolic Logic 15, 81–91. Hintikka, J.: 1989, ‘Is there Completeness in Mathematics after G¨odel?’, Philosophical Topics 17, 69–90. Hintikka, J.: 1993, ‘G¨odel’s Functional Interpretation in a Wider Perspective’, Yearbook 1991 of the Kurt G¨odel Society, The Kurt G¨odel Society, Vienna, pp. 5–43. Hintikka, J.: 1995a, ‘Standard vs. Nonstandard Distinction: A Watershed in the Foundations of Mathematics’, in J. Hintikka (ed.), From Dedekind to G¨odel, Kluwer Academic, Dordrecht, pp. 21–44. Hintikka, J.: 1995b, ‘What is Elementary Logic? Independence-Friendly Logic as the True Core Area of Logic’, in K. Gavroglu, J. Stachel, and M. Wartofsky (eds.), Physics, Philosophy and the Scientific Community, Kluwer Academic Publishers, Dordrecht, pp. 301–326. Hintikka, J.: 1996, The Principles of Mathematics Revisited, Cambridge University Press, Cambridge. Hintikka, J. and G. Sandu: 1992, ‘The Skeleton in Frege’s Cupboard: The Standard vs. Non-Standard Distinction’, Journal of Philosophy 89, 290–315. Kelley, J.: 1955, General Topology, D. van Nostrand, Princeton. Lindstr¨om, Per: 1969, ‘On Extensions of Elementary Logic’, Theoria 35, 1–11. Moore, G.: 1988, ‘The Emergence of First-Order Logic’, in W. Aspray and P. Kitcher (eds.), History and Philosophy of Modern Mathematics, University of Minnesota Press, Minneapolis, pp. 95–135. Moschovakis, Y.: 1974, Elementary Induction on Abstract Structures, North-Holland, Amsterdam. Ramsey, F. P.: 1931, ‘The Foundations of Mathematics’, in R. B. Braithwaite (ed.), The Foundations of Mathematics and Other Logical Essays, Routledge and Keegan Paul, London. Sandu, S. and J. V¨aa¨ n¨anen: 1992, ‘Partially Ordered Connectives’, Zeitschrift f¨ur mathematische Logik und Grundlagen der Mathematik 38, 631–72. Shapiro, S.: 1991, Foundations without Foundationalism, Clarendon Press, Oxford. Tarski, A.: 1956, ‘The Concept of Truth in Formalized Languages’, in Logic, Semantics, Metamathematics: Papers from 1923 to 1938, Clarendon Press, Oxford, pp. 152–178. Department of Philosophy Boston University Boston, MA U.S.A.