Outlines of a Formalist Philosophy of Mathematics

OUTLINES OF A

FORMALIST PHILOSOPHY OF MATHEMATICS

HASKELL B. CURRY Professor of Mathematics State College, Pa. U.S.A.

~c

m ~

195 1 NORTH·HOLLAND PUBLISHING COMPANY AMSTERDAM

PRINTED IN THE NETHERLANDS DRUKKERIJ HOLLAND N.V., AMSTERDAM

PREFACE In the opening days of September, 1939, just as the Second World War was breaking out, an International Congress for the Unity of Science was held at Cambridge, Massachusetts. The committee in charge of that congress invited me to submit a paper there. This invitation suggested that I write out, in a more or less systematic form, the philosophical opinions which I had formed in a little more than a decade of study in mathematical logic. I found the task a longer and more difficult one than I had anticipated; nevertheless I persisted in it. The resulting manuscript was, of course, too long for presentation at the congress; but it formed the basis of the paper presented there, and of several other papers, cited below, which have been written since. The present monograph represents the publication of the manuscript prepared in 1939. It is published here in essentially the same form in which it was originally written down. The only changes are a revision of Example 9 in Chapter V and some footnotes. These changes date from 1942. In view of the foregoing origin of this monograph, the reader should bear in mind the following points concerning it. In the first place, this monograph represents the views which I held in 1939; it does not represent accurately the views which I would defend right now. The later papers, already mentioned, overlap with it greatly and supersede some parts of it. However, the more amplified presentation which is possible in this monograph will presumably be an advantage for some readers; furthermore, the statement of what lies back of the opinions expressed in the later papers may help to make them better understood. A similar caution should be observed in regard to the views of other persons which are quoted or criticized here. This is particularly true in the case of Carnap and other leaders of the

VI

PREFACE

Unity of Science movement. Later publications of these persons show considerable changes in their views also. The citations of other papers are made in a special manner which is explained at the end of Chapter I. For the most part, however, acquaintance with these references is not presupposed. Except for the fact that criticism of views of other persons requires some acquaintance with those views as expressed by the authors themselves, this monograph is self-contained, and thus is in accordance with the aim of this series. For this reason it does not seem to be necessary to replace these citations with others made in a more orthodox form. The matters of notation request comment. In a review published in the Journal of Symbolic Logic, vol. 6, pp. 100-102, Kleene pointed out that the uses of the prefix "meta-" and the adjective "recursive" differ from those which are made elsewhere. (The review had reference to a later paper, but it applies to this one, which Kleene had seen in May, 1940). To remedy any possible ambiguity in regard to the first point, I shall in the future use the prefix "epi-" to replace the prefix "meta-" in the sense used here (Chapter IX), reserving "meta-" for use in connection with semiotical matters. It would, however, only add to the confusion to make this change in the present text. In regard to the word "recursive", the point seems to be that Kleene (and others), taking the notion of recursive function as fundamental, applies the term "recursive" to a class only when its characteristic function is recursive; whereas here a class is referred to as recursive when it can be exhausted by a recursive enumeration or construction. This is an oversight; it would indeed be better to call this kind of class "recursively generated". Thus, in a definite formal system, as defined in Chapter IV, the notions of term, proposition, proof, and other definite concepts could be described as recursive, while the theorems are recursively generated. Here again it seems undesirable to change the present text, but merely to call attention to the situation and bear it in mind for future use. The later papers referred to above are the following, with place of publication or presumed publication:

PREFACE

VII

"Remarks on the Nature and Definition of Mathematics", (Abstract of address before International Congress for the Unity of Science, September 5, 1939), Journal of Unified Science, 9, pp. 164-169. "Some Aspects of the Problem of Mathematical Rigor", Bulletin of the American Mathematical Society, (1941), 47, pp. 221-24I. "The Paradox of Kleene and Rosser", Transactions of the American Mathematical Society, (1941), 50, pp. 454-516, (especially pp. 457-462). "Mathematics, Syntactics, and Logic", (Address before International Congress for the Unity of Science, Chicago, 1941). To appear (1) in Journal of Unified Science. "Languages and Formal Systems", (Abstract of address delivered August 16, 1948), Proceedings Tenth International Congress of Philosophy, 1949, pp. 770-772. "Language, Metalanguage, and Formal System", (Full form of the preceding). Philosophical Review (1950) 59, pp. 346-353. "A Theory of Formal Deducibility", Notre Dame Mathematical Lectures No.6, (Delivered April 12-15, 1948). Notre Dame, Indiana. 1950, 126 pp. "L-Semantics as a Formal System", Congres International de Philosophie des Sciences, Paris, 1949 (Actual. Sci. et Ind., no. 1134), Paris, 1951. "Las Systemes formals et les langues", Colloque de Logique Symbolique, Paris, 1950 (forthcoming). "Leeons sur la logique algebrique" Paris (Gauthier Villers) and Louvain (Nauwelaerts) (forthcoming).

State College, Pennsylvania, U.S.A. May, 1951

HASKELL B. CURRY

I

INTRODUCTION This book deals with the philosophy of mathematics, not from the point of view of a philosopher, but from that of a mathematician who has had occasion to reflect on the nature of his science. That there is a danger in writing such a book lam fully aware; philosophers will doubtless find that these views are naive, and that too much space is devoted to formal matters, whereas mathematicians may feel that their time is better spent in creating new mathematics. But, aside from the fact that criticism has from time to time had a stimulating influence on research, there appears at the present time to be a special need for discussions of this kind. Owing to the departmentalization of our educational system, mathematicians and philosophers have little contact with one another; on the other hand the rise of mathematical logic has made especially patent the need of a rapprochement between the two. Such a rapprochement was indeed one of the aims which the founders of the Association for Symbolic Logic had in mind. If, then, this book ventures a bit from safe, familiar shores, it is because an attempt to meet the philosophers half way is made in it. I hope that the result will be interesting to both mathematicians and philosophers. This book does not attempt to cover the whole range of mathematical philosophy, but contains merely a discussion of certain special topics. The choice of these topics has been determined partly by my own interests, partly by contacts - oral or otherwise - with my colleagues; and I have laid special emphasis on questions in which these contacts showed that comment would be appropriate. Subject to these limitations, however, the book is intended to be self-contained. There is no attempt to confine attention to what is novel. Moreover I have not tried to do justice to the history of the subject, nor to trace ideas to their sources; the book is based more on direct reflection than on a survey of

2

INTRODUCTION

the literature. References are given here and there in the text; but I may have been influenced by contacts long since forgotten. Finally, although the book carries the word 'philosophy' in its title, yet considerable space is taken up by essentially mathematical considerations for which a philosophical interest is presumed. Since we have in various journals excellent bibliographical information concerning the literature, it is possible to abbreviate citations. I shall use the following scheme: The letter 'J' refers to the Journal oj Symbolic Logic; it is followed by volume and page reference either to the original paper or to a review of it. The letter 'C' refers to Church's bibliography in J 1, 121-218 and J 3, 178-212; this 'C' is followed by symbols referring to the individual authors or papers according to the scheme of Church's indices (e.g. J 3, 193). The letter 'Z' refers to the Zentralblatt j1lr Mathematik, the reference being by volume and page.

II THE PROBLEM OF MATHEMATICAL TRUTH

The central problem in the philosophy of mathematics is the definition of mathematical truth. If mathematics is to be a science, then it must consist of propositions concerning a subject matter, which propositions are true in so far as they correspond with the facts. We are concerned with the nature of this subject matter and these facts. The ordinary mathematician bases the idea of truth upon that of rigor; he regards a mathematical proposition as true when he has a rigorous proof of it. But when we examine the nature of this "rigor", we find there is something vague and subjective about it. This is true to such an extent that intelligent persons have maintained that mathematics is not a science at all; that it has no subject matter nor any criterion of truth; and that in the last analysis it is based on purely aesthetic considerations. Now although there are doubtless aesthetic elements in mathematics, yet most of us cannot be satisfied with such an account of our subject. There must be an objective criterion of truth, and the first task of the mathematical logician is to find it. The first thesis of this book is that such a definition can be found. Indeed mathematics can be conceived as a science in such a way as to be independent of any except the most rudimentary philosophical hypotheses. So conceived, mathematics forms, like every other science, part of the data of philosophy. There are three main types of opinion as to the nature of this subject matter, viz.: 1) realism, or the view that mathematical propositions are true insofar as they correspond with our physical environment; 2) idealism, which relates mathematics to mental objects of one sort or another; and 3) formalism. The realist point of view is now not taken seriously by most mathematicians. Of course it must have been the original view as to mathematics; among primitive peoples mathematics is

4

THE PROBLEl'.I OF MATHEMATICAL TRUTH

essentially empirical. Today, however, the view is untenable; for one reason because there is nothing corresponding to infinity in the external environment. It is unnecessary to go into this here; for the point is generally recognized. Everybody thinks of mathematics as "abstract"; and it is a truism for every serious student of the subject that its theorems hold independently of any relation to external reality. This leaves us with the idealist and formalist positions. The idealist position will concern us in the next section; after some discussion of the nature of formalism we shall return to the formalist definition of mathematical truth in Chapter X. The remaining sections of this book will deal with the relations of mathematics to its applications.

III IDEALISTIC VIEWS OF MATHEMATICS On the idealistic view mathematics deals with mental objects of some sort. There are different varieties of this view according to the nature of these mental objects. On the one hand there is the view, here called Platonism 1, which ascribes an independent existence to all the infinitistic conceptions of classical mathematics; on the other hand there is intuitionism, which makes everything depend on an a priori basic intuition of temporal succession 2. All forms of idealism are subject to the same fundamental criticism: viz., that the resulting criterion of truth is vague at best, and depends on metaphysical assumptions from which mathematics, if it is to have the pre-philosophical character above mentioned, must be free. That this criticism applies against Platonism has been shown very effectively by its intuitionist critics. But it also applies against intuitionism itself3, at least in the form espoused by Brouwer and his school. In fact, as to the vagueness we have Heyting's own statement 4, "Uber dies ist es an sich widersinnig, die Mogliohkeiten des Denkens in das Mieder bestimmter zuvor angegebener Konstruktionsprinzipien zwangen zu wollen. Man muss sich also darauf besohranken, durch mehr oder weniger vage Umschreibungen in dem Horer die mathematische Geisteshaltung hervorzurufen". (Cf. also Church's criticism, J 2, 89). As to the metaphysical character it is clear from the intuitionist writings that their fundamental intuition must have the following properties: 1) it is essentially a thinking activity ("eine konThis name was suggested by Bernays (0 287.17). Both Platonism and intuitionism have many sub-varieties. In either case the different writers often disagree with one another. 3 Of. Hahn, 0 419.2. 4 0 385.10, p. 12. 1

2

6

IDEALISTIC VIEWS OF MATHEMATICS

struktive Tatigkeit unseres Verstandes") 1, 2) as a criterion of truth it has a priori character ("Die mathematischen Gegen stande werden von dem denkenden Geist unmittelbar erfasst; die mathematische Erkenntnis ist daher von der Erfahrung unabhangig) 2, 3) it is independent of language 3; and 4) it has objective reality, at least in the sense that it is the same in all thinking beings 4. Now it seems at least doubtful if there is any such thing as an intuition satisfying these specifications or even the first three of them. It is doubtful, for instance, if there is any priori knowledge; and it has been rationally maintained that thought of any kind is impossible without language. Moreover the fourth condition is absolutely vital for intuitionism if it is to give a definition of mathematical truth at all; and the assumption that it is satisfied is an out and out postulate 5. The upshot of this is that the intuitionist definition of mathematics has meaning only for one who postulates an a priori intuition which is both objective and prelinguistic. Although this assumption is agreeable to certain types of philosophy, yet it is an assumption for all that, and one which, from other points of view, is highly dubious and metaphysical. Similar, and perhaps even more dubious assumptions are involved in other idealistic theories. (It is not necessary to repeat well known arguments on this point). Consequently I maintain that an idealistic definition of mathematics is untenable. It should be emphasized that the reason for this is not that 1

ius; p. 2.

Ibid., p. 3. Ibid., p. 13. 4 A fifth characteristic, its relation to time, is irrelevant for us. 5 The intuitionists make much of the fact that they do not ascribe any existence to mathematical objects independent of their construction by the basic intuition. But on the other hand they speak of the complete objectivity of mathematics. This objectivity enters because, although the independent existence of mathematical objects is not assumed, that of their god, Intuition, is. But the existence of Intuition is just as problematical an assumption as that of the mathematical objects them. selves. 2

a

IDEALISTIC VIEWS OF MATHEMATICS

7

these assumptions are invalid. There is, in fact, much to be said for these assumptions. One can make out a good case even for Platonism on somewhat the following lines 1. On what grounds do we infer the reality say of the table on which I am writing? I understand that one can consistently maintain the view, called solipsism, that physical objects have no reality; i.e., that the sole reality is my sensations. In fact, one does not prove the existence of an external world, one postulates it. Even so, one can postulate a reality of a different sort for the concepts of mathematics. I see nothing absurd or nonsensical about this. But the point is that the questions involved is not a mathematical one, and a definition of mathematical truth should not depend on the solution of such a problem. To return to intuitionism I have treated it as a kind of idealism. That appears to be the view of at least Brouwer and Heyting (note the above quotations). But it is possible to defend an essentially intuitionist mathematics on entirely different grounds 2. All these forms of quasi-intuitionism are subject to the pragmatic objection, viz. that they do not give an account of all of methematios as we know it. Of course it is an essential point of this objection that all of mathematics can be justified for other reasons 3; but this once granted the objection is fatal. (See also below, Chapter XI). 1 To remove all possibility of doubt I should emphasize that I am not undertaking to defend the thesis in the text. S E.g., see Dienes in Z 20, 98. 3 Cf. Hedrick (C 476.1, p. 337), who compares the pragmatic argument to the argument for immortality based on our dislike for mortality. The point is that immortality has no independent justification whereas classical mathematics does (see Chapter IX).

IV DEFINITION AND STRUCTURE OF A FORMAL SYSTEM

Before we proceed to the discussion of the formalist definition of mathematics, it will be necessary to consider the definition of its fundamental notion, that of a formal system. This topic will occupy us in the next few sections. The conception here expounded differs superficially from the usual one in that such a system is conceived not as a game but as a body of propositions. To avoid any possibility of misunderstanding, we begin with certain preliminary explanations. The first point is that the words 'proposition', 'true', 'predicate', etc., used in the following, are intended in the sense of ordinary discourse. It is not necessary to go into the question of what this sense of ordinary discourse is, but only to make a few remarks. A proposition is something which is capable of being understood as an assertion, - of saying something - with a constant intuitive meaning. It indicates certain conditions for verification; when the proposition is asserted - taken as true -, that means that these conditions are fulfilled, so that processes of verification are what determine, essentially, the meaning of the proposition. On the other hand, what it means to deny such a proposition is a matter for further analysis; we have on hand in the processes of verification certain sufficient conditions for truth, but whether we have necessary conditions or not is not stated. As for 'predicate', this refers to a propositional function of any number of arguments; - i.e, such that when these arguments are given definite values the result is a proposition in the above sense. The word 'theorem' will be used in the sense of 'true proposition'. The second point relates to the distinction, pointed out by Frege and emphasized by Carnap, between an entity and its linguistic designation. In this book all symbols are to be taken,

DEFINITION AND STRUCTURE OF A FORMAL SYSTEM

9

unless otherwise indicated, as designating the entities talked about, not as specimens of them 1. When I wish to talk about a linguistic expression as such (rather than about its meaning), I shall, following Frege, use a specimen of the expression enclosed in single quotation marks as its name. Single quotation marks will be reserved for this technical use; when quotation marks are intended for the uses of ordinary discourse (which are sometimes but not always in agreement with the above practice), I shall employ double ones. In this paper I shall also use Quine's "quasi-quotes" 2 in a similar manner as a device for naming the meaning of a linguistic expression when the expression is not itself a name. This enables us to take into account the naive and admittedly vague distinction between a proposition and the linguistic expression - called a sentence - which asserts it, between a predicate and an adjective, and so on. Thus if 'A' is an abbreviation for a sentence we shall use 'A' when we want to assert the proposition, "A" as a name for the sentence as a linguistic object, and -rAl ' as a name for the 1 It is not possible to be absolutely rigorous in maintaining this distinction. There are two reasons for this. In the first place, it is sometimes convenient to use an abbreviated form of speech in which an expression may be used in both senses at once; this case arises in connection with definitions and does not necessarily lead to confusion (cf. the discussion in Chapter VIII). Again the usage may conflict with our usual linguistic conventions for indicating the same thing. Thus, suppose that 'A' is an abbreviation for a description of some object. Then the sentence 'A is called B' would ordinarily be understood as meaning that 'B' is the name of the object described by 'A'; if we were to replace 'B' by "B" this would introduce, rather than eliminate confusion, because we should be uncertain as to whether 'B' or "B" was the name of A. For the sake of definiteness I state here that in the case of 'call' I shall follow ordinary usage; this means, too, that I may say on occasion 'the A's are called B's' with its ordinary significance. It is impossible to catalog all cases of this kind; but in general quotation marks will not be used where ordinary language makes the distinction clear. 2 J 2, 146. In connection with intuitive variables these are to be treated as Quine treats them. The reader should note, however, that the present use of "quasi-quotes" differs in some respects from Quine's.

10

DEFINITION AND STRUCTURE OF A FORMAL SYSTEM

proposition which is the meaning types of expressions 2.

1

of 'A'. Similarly for other

Note that we can also speak of the meaning of a proposition. 'Meaning' here has another meaning, of course. Since this is not a work on epistemology I am content to use 'meaning' somewhat vaguely. 2 Although I employ this device to distinguish between an expression and its meaning yet I do not wish to advocate any particular view as to the philosophical nature of this distinction. On the contrary, the purpose of the notation is to avoid discussion of that question, which I consider outside of my province. For the reasons discussed in Chapter VIn I am not satisfied with the view that no distinction whatever is to be made between, say, a sentence and a proposition. The following examples illustrate some points not made in the text: 1. rThe moon is made of green cheese l is contrary to scientific knowledge. 2. That the moon should be made of green cheese is contrary to scientific knowledge. 3. 'The moon is made of green cheese' has seven words. 4. 'The moon is made of green cheese' and 'Der Mond ist aus grunem Kase aufgebaut' have the same meaning (i.e. they express the same proposition). 5. rThe moon is made ofgreen cheesel implies rmy wife is a Presbyterianl. 6. If the moon is made of green cheese then my wife is a Presbyterian. 7. rThe moon is made of green cheesel is true if and only if the moon is made of green cheese. These examples suggest the following remarks: Examples 5 and 6 show that whether quasi-quotes are used or not depends on the context i.e. on grammatical considerations. In fact, the effect of quasi-quotes (like 'that') is to transform a sentence into a noun (i.e. noun-clause); when the context is syntactically suitable for nouns quasi-quotes are used, when it is suitable for sentences they are not. Hence the essential distinction between a quoted and an unquoted sentence is that between a noun and a sentence; the one names its object, the other states it. On the other hand a single-quoted sentence and a quasi.quoted sentence are alike in both being nouns; as to the semantic difference (cf. Morris, J 3, 158) between them I take, as above explained, no definite position; but in this paper, at least, there is the following pragmatic difference: - we use the former when we are thinking of linguistic considerations and the latter when we are thinking of considerations which are invariant, so to speak, of linguistic change (they have reference to meaning) and therefore pertain to a higher order of abstraction. Frege, who emphasized the need for distinguishing between a symbol and its meaning, also observed the distinction between a sentence and

DEFINITION AND STRUCTURE OF A FORMAL SYSTEM

11

Finally, it will be convenient to introduce certain technical expressions. These will be italicized where they first occur and are to be regarded as defined by that context. After these considerations we may proceed to the definition of a formal system. For this purpose it is now unnecessary to lead up to the most abstract conception through consideration of the semi-formal postulate systems of a generation ago. We may plunge in medias res and study at once the definition of a completely abstract system. From the point of view here suggested, such a system is defined by a set of conventions, which I shall call its primitive frame, specifying the following: first, a set of objects, which I shall call terms; second a set of propositions, which I shall call elementary propositions, concerning these terms; and third, which of these elementary propositions are true. The first and third of these specifications are essentially recursive definitions. Thus the primitive frame does not say what the terms ultimately are, but gives simply a list of primitive terms together with the operations and rules according to which all further terms are to be constructed. Likewise the third set of conventions constitutes essentially a recursive definition. We have a set of axioms, which are true immediately by definition, together with rules of procedure for deriving all others. Let us examine the structure of a formal system more in detail. In order not to complicate matters we shall not think of the most general formal system but one of a slightly restricted type. In order notto be too special, however, we admit systems in which there are different kinds ("categories" or "types") of terms. Then the primitive frame will look like this:

1. TERMS A.

Tokens

1

or primitive terms. This is simply a list,which

a noun clause. He reversed the above procedure by prefixing 'f-' to a noun clause to make a sentence out of it. 1 Note that 'token' is the cognate of German 'Zeichen'.

12

DEFINITION AND STRUCTURE OF A FORMAL SYSTEM

may be infinite, of the terms of each kind. Nothing else is specified concerning them.

B. Operations, i.e. modes of combination for forming new terms. There is a list of these with the number and kind of the arguments for each. C. Rules of formation 1, specifying how new terms are to be constructed. These will be of the form: 'Tf such and such an operation is applied to a sequence of terms of the proper number and kind, the result is a term of such and such a kind1.

II.

ELEMENTARY PROPOSITIONS

The specifications here will be simply a list of the elementary predicates with the number and kind of the arguments for each; the elementary propositions are then formed by applying such predicates to sequences of terms of the proper number and kind 2.

III.

ELEMENTARY THEOREMS

A. Axioms, i.e. elementary propositions stated to be true unconditionally. There may be a finite list of these, or they may be given by rules 3 determining an infinite number in an effective manner 4.

B. Rules of Procedure, i.e. rules for derivation of further theorems. These rules are of the following form :rIf PI> P 2 , ••• Pm This name is used by Carnap in his Logical Syntax (C 352.12 or J 4, 82). One can here separate the specifications into a list of predicates and the rules for predication. But the rules are evident when the kind of arguments has once been stated. 3 Such rules may be given by axiom schemes (von Neumann C 299.3) from which an unlimited number of axioms arise by substitution. Cf. Example 2 below. 4 I.e. it must always be finitely ascertainable whether an elementary proposition is or is not an axiom. 1

2

DEFINITION AND STRUCTURE OF A FORMAL SYSTEM

13

are elementary theorems subject to such and such conditions, and if Q is an elementary proposition having such and such a relation to P v P 2 , ••• Pm' then Q is true." The number m is finite; moreover the conditions on the PI' ... Pm and their relation with Q are of a definite structural character; i.e. it must be effectively ascertainable in terms of the notions introduced in I, whether they hold or not 1. For some purpose it is advisable to require that Q be uniquely determined, but not in general 2. Let us now consider some comments about this definition. These comments do not concern the philosophical nature of a formal system - that topic will be discussed in Chapter VI, - but they 'are intended to clear up certain points which are to be understood as implied in the definition of a formal system as such. In the first place, along with the definition of any formal system, we must represent the various notions by symbols, and the definition of these symbols is part of any statement of the primitive frame. Thus the specification I A will consist of a list of the names for the tokens; in I B and II we shall have not only the names of the operations and predicates, but an indication of the way their application is to be symbolized. We may also have further specifications of a purely symbolic import. It is not my intention to maintain that a formal system can be conceived apart from some symbolism for it. Again, the specifications are intended to be exhaustive; i.e, the terms are specified exhaustively by I, the elementary propositions by II, and the elementary theorems by III. This means that whatever is a term is either a token or else is constructed from tokens by a succession of processes in accordance with I C. As to elementary theorems let us be even more explicit: An elementary proposition is true if and only if there exists a finite 1 Note that the rules of procedure do not allow us to derive any theorems without the axioms. If there were no axioms there would be no elementary theorems. 2 This is Rosser's suggestion. Cf. Church in C 359.7, footnote on p. 358.

14

DEFINITION AND STRUCTURE OF A FORMAL SYSTEM

sequence of propositions PI' P 2 , ••• P n such that P n is Q and every Pi is either an axiom or is derived from some of its pre~ decessors by a rule of procedure. It is not necessary to state such closure specifications in each case. Since the specifications I and II have a different character from those in III, it is convenient to allude to them as morphological; the considerations relating to them constitute the morphology of the formal system. In contradistinction the considerations relating to III can be called theoretical. Of course there are propositions involved in the morphology (e.g. rX is a term of such and such kind", rX is an elementary proposition1. These are, however, such that in any given case we can determine by a finite (and in most cases relatively trivial) process whether the proposition is true or not 1. This brings up a certain definite character of the specifications which is worth emphasizing. Following Carnap, let us call a property (or other predicate) definite if and only if we have given a finite process for determining in any particular case in its range of significance whether the property holds or not. Accordingly the following are all definite: all morphological predicates 2, the property of being an axiom, and the relation of the conclusion of a rule of procedure to its premise(s). On the other hand, the property of being an elementary theorem is not always definite - when it is, the system has a relatively trivial character, (cf. Example 5, below); but, given any finite sequence of elementary propositions, it is always a definite question whether it constitutes a proof of the last one 3. Let us now turn from the consideration of a typical, but restricted, kind of formal system to some generalizations. First, there are those generalizations which do not affect the 1 The separation of morphology from theory is an arbitrary matter. See Chapter VII. ~ The morphological propositions must be definite in the sense that given any term the method of its construction from the tokens is uniquely determined. 3 Cf. end of Chapter VI.

DEFINITION AND STRUCTURE OF A FORMAL SYSTEM

15

definiteness of the specifications as stated above. The system may have a more complicated morphology. We may need not only kinds of terms, but also relations between terms, e.g. in Example 6, below; or operations (or predicates) simultaneously applicable to different kinds of terms (e.g. the a in Example 7); or even with a variable number of arguments (the derivability relation in a formalized syntax might be an example ot this) 1. Again we may need, in the formulation of the rules, operations or other auxiliary 2 morphological notions (e.g. the substitution operation of Example 6). Such complications might affect the rules II; so that we might need to formulate rules of predication which in the simpler systems are superfluous. All such generalizations are to be regarded as included in the definition of a formal system, provided they do not affect the definite character of the specifications as emphasized above. Again Carnap and others have found a use for generalizations, such as operations with infinitely many arguments and rules with infinitely many premises, which can introduce indefiniteness into the formulation of the specifications. It is not advisable to exclude these from the definition of rformal systeml, but we must distinguish them sharply from the formal systems considered hitherto. Let us call the former indefinite formal systems, the latter definite formal systems. In this paper only definite formal systems will be considered, unless indefinite ones are explicitly mentioned. Finally, a few matters of terminology. The tokens, operations, and elementary predicates of a formal system we may refer to collectively as primitive ideas, while the axioms and rules of procedure collectively we shall call postulates. The primitive propositions of the system then consist of the postulates and certain 1 Such an operation can always be analyzed into a set of simpler ones, but this is not always convenient. 2 We shall call an operation, predicate, etc. auxiliary when it is not necessary either for the definition of elementary proposition or for the statement of any particular elementary proposition. The term 'morphology' is to be understood as including all such notions.

16

DEFINITION AND STRUCTURE OF A FORMAL SYSTEM

morphological propositions. These primitive propositions are true

by definition

1.

[May 2, 1942] It now seems desirable to modify the terminology of the preceding section so as to distinguish between the names of constituents of the formal system and those for certain classes of symbols. To this end the suggested changes are as follows: 'Token': in the sense above to be replaced by 'primitive term'; henceforth 'token' to be used for the symbols denoting primitive terms. 'Operator'; to be used for symbols (and symbolic devices) indicating operations. 'Predicator': similarly for symbols denoting predicates. These words can then be used in an analogous way in a syntactical system. Of course these distinctions are not adhered to in the present book; in particular 'operator' and 'operation' are sometimes confused.

v EXAMPLES OF FORMAL SYSTEMS Before going further, let us consider some examples. In the presentation of these examples it will be convenient to use a certain systematic notation. The following four symbols

, ,

=,

, ,

~,

,~,

~,

'&'

will be reserved for technical uses as follows: '=' is for definitional identity; when placed between two expressions the resulting sentence means that the expression appearing on the left is defined to be an abbreviation of the one appearing on the right. The other three symbols are propositional connections; when they are placed between two sentences, the resulting expression is a sentence having a meaning according to the following definitions: (here 'A' and 'B' are supposed to be abbreviations of sentences - for the dots, see below) A-B A & B A;=B

.=.

if A then s.» A and B. A_ B. & .B_A.

The ordinary technique of dots 2 will be used in connection with these symbols; moreover '=' will be taken senior to '_' and ';=', and these in turn senior to '&'. It is important to realize that these connectives have a meaning, as supplements to ordinary language, independent of any formal system. Besides using these connectives I shall observe the following special conventions. German letters will be used for unspecified terms; they are the 1 The actual use of '~' in this and some of my other papers, is more specific than this. It is used in stating rules of procedure and metatheorems which follow directly from them; i.e. metatheorems of type B I (see Chapter IX). 2 As in J 2, 26-28.

18

EXAMPLES OF FORMAL SYSTEMS

variables by which rules are expressed. Greek letters will be reserved for indicating operations, when so used they will be prefixed, i.e. placed before their arguments; parentheses are then unnecessary as Lukasiewicz has shown. Other binary operations and binary predicates will be infixed (placed between their arguments) in the customary manner.

Example 1.

(A rudimentary arithmetic).

I A. One token: O. I B. One unary operation, denoted by priming. I C. If a is a term then a' is a term. II A. One binary predicate, = (Elementary propositions are those of the form r a = b1, where a and b are terms). III A. One axiom: 0 = O. III B. One rule: a = b ~ a' = b'. The terms of this system are the natural numbers. We ordinarily use the abbreviations: 1=0';

2=1'=0";

3=2'=0'"etc.

We may, if we like, think of these terms as the names of symbols as follows (the symbol on the left being the name of that which occurs on the right).

o 1 2 3

Example 2.

o

(1)

(11) (111)

etc.

(Part of Hermes's formalized syntax).

I A. One token: O. I B. 1. A set of unary operations f{JI' •• "' f{Ju" 2. One binary operation, A (infixed). I C. 1. If a is a term, f{J; a is a term. 2. If a and b are terms, a A b is a term. II.

One binary predicate,

=

(infixed).

19

EXAMPLES OF FORMAL SYSTEMS

III A. 1. 2. 3. III B. 1. 2. 3. 4. 5.

0

=

O.

If a is a term, a A 0 = a 1. If a and 6 are terms, a A fPi 6

a = b -+ b = a. a = b & b = c -+ a = c. a

=

b -+ fPja

=

fPi b.

a = b -+ C A a = c s b. a = b -+ a A c = b A C.

=

fIJi (a

i

=

A

6). 1, 2, ... , n.

This is essentially a formulation of the basic part of Hermes's Semeiotik 2. The operation rA1 corresponds to concatenation 3 of linguistic expressions. When n = 1, the system reduces to a form of arithmetic in which r fP1 is the successor function and rA 1 is addition; it is then essentially Example 1 with postulates for addition adjoined.

Example 3.

(Two valued propositional algebra, first form).

IA. An infinite series of tokens, PI' P2' ..•. IB. Two operations: -,- unary and :> binary. r c. If a and b are terms, then -,-a and a :> b are terms. II.

One unary predicate: f-. (The elementary propositions are those of the form rf-al, where a is a term) 4.

1 A 2 and A 3 are axiom schemes from which an unlimited number of axioms arise by substitution. For other examples see III A of Example 3. t J 4, 87. a This term is due to Quine (Z 15, 50, J 1, ll6). • Note that this usage of 'f-' differs from Frege's. From the formal point of view the terms of this system are not propositions but objects of an unspecified kind (cf. the discussion below); they might be marbles. Under these circumstances Pl :>PI (for instance) is not a proposition, but a term; 'PI:> PI' is not a sentence, but a noun. When we place 'f-' in front of this noun we get a sentence expressing the fact that PI :>PI (which is a term) belongs to a certain subclass of terms defined recursively by the postulates. Huntington would express the same fact by 'PI:> PI is in T'; Hilbert by 'PI:> PI ist beweisbar", That I have used 'f-' consistently in this sense (see C 396.2, p. 520 Festzetzung 1) is due to the fact that this seems the natural meaning to give to 'f-' when such a theory is strictly formalized. The possibility of so interpreting 'f-' appears to have been

20

EXAMPLES OF FORMAL SYSTEMS

III A. If a, 0, I. 2. 3.

III B. 1.

C

are any terms, then

f- a ::> . 0 ::> a. f- a ::> • 0 ::> C • ::>: a ::> 0 . ::> . a ::> c. f- r-r- a ::> 0 . ::> . 0 ::> a. f- a & f- a ::> 0 -+ f- O. -r-r-

Example 4. (Second form of the two valued algebra). I, II as in Example 3. III A. Three specific axioms: I 1. f- PI ::> . P2 ::> Pl' 2. f- PI ::> • P2 ::> Pa· ::>: PI ::> P2' ::> . PI ::> Pa' 3. f- -rr- PI ::> r--r- P2' ::>. P2 ::> Pl' III B. 1. as in Example 3. 2. A rule of substitution thus: if ,\) is a token and a, o are terms, then

f- 0 -+ f- Subst (~) 0 where Subst (~) 0 is defined recursively in a manner analogous to that in Example 6 below. Example 4 differs from Example 3 in the the axiom schemes are replaced by axioms with a rule of substitution.

Example 5.

(Matrix formulation of the two-valued algebra).

I, II as in Example 3.

III A. With each term a associate a polynomial a* in the in-

determinates

Xl' X 2' .•• 2

defined recursively as follows:

pi

(-,- a)* (a ::>0)

Xi'

1+ a*.

(I

+ a*) b*.

overlooked by B. A. Bernstein (C 239.17). The use of 'f-' to distinguish an asserted from an unasserted proposition is not a formal matter; and the necessity for the distinction only arises when one considers the philosophy of the situation. I These are derived from the axiom schemes of Example 3 by taking a =0 PI' b =0 P2' C =0 Pa' 2 Cf Example 9.

r-

21

EXAMPLES OF FORMAL SYSTEMS

Then a if and only if a is identically 0 mod 2 (when the indeterminates are taken as unspecified values in the field). III B. None (This is one formulation of a matric type of algebra of propositions; the idea is due to Herbrand (C 382.5 Chap. I). There are, of course, other equivalent formulations).

Example 6.

(Church's theory of conversion)

1.

I A. An infinite sequence of tokens: IB. Two binary operators: a, A.. The operation r a1 is applicable to all terms, to a token and a term in that order 2. I C. We define by recursion, not only the word 'term' but also a relation between a token f and a term a expressed by 'f occurs free in a', as follows: 1. Xi is a term; Xi occurs free in Xi' Xi (j i) does not. 2. If a and b are terms, a a b is a term; the tokens occurring free in a a b are precisely those which occur free in either a or b (or both). 3. If a is a term and Xi occurs free in a; then A Xi a is a term, also Xi does not occur free in A Xi a and Xi (j i) occurs free in A Xi a if and only if it occurs free in a. II. One binary predicate: cnv (read "is convertible to"). III. In order to state the axioms we must formulate the substitution 3 operation, as follows:

rx,

*-

*-

J 2, 39, Chap. I. The term ). x a represents the function which a is of x. If we were to use this in ordinary calculus ). x x 2 would be the square function, Ax log x the logarithm, etc. 3 Note that substitution is an operation on terms, not on their names. It corresponds to a syntactical operation in the following sense: if a is a term then the specifications I assign to a a certain expression which we shall call its standard name; thus 'a Xl Xl' is the standard name of' c z, Xl" Let us denote the standard name of a term a by 'ii'. Let us suppose that x 2 is not bound in a. then x 2 occurs free in a if and only if there is an 1

2

22

EXAMPLES OF FORMAL SYSTEMS

(~i)

Xi

b. Subst (~i)

Xi

a. Subst

a.

¥- i). (Subst ~i) b (Subst ~i) c. (j

-

Xi

c. Subst (~) abc -

a

d. Subst (~i) A. Xi b -

A. Xi b.

e. Subst if i

(~i)

¥- j and

A. Xi xi

e-

A. Xi Subst

(~) b.

does not occur free in a 1.

We also need the relation between a token ! and a term a expressed by the sentence '! occurs bound in a'. This is defined as follows: a. No token is bound in x,.. b. The tokens bound in a a b are precisely those bound in a or b or both. c. The tokens bound in A. Xi a are Xi together with those bound in a.

III A. Axioms.

1. If a is a term, a env a. 2. If a is a term in which Xi occurs free and occur bound or free, then A.

Xi

a cnv

A.

Xi

xi

does not

(Subst ~:) a.

3. If a and b are terms such that Xi occurs free in a but not bound, and no token which occurs free in b occurs bound in a, then a A.

Xi a b cnv Subst (:i)

a.

instance of 'x a' in ~. Let b be any other term whose standard name is b. Then 'Subst (b/x a) a' is an abbreviation for the expression got from a by

replacing 'xa' by b throughout. 1 If Xi does occur free in a Church does not use Subst (a/xi) A xi b; hence he requires no definition for it. It is, however, possible to so define Subst (a/xi) A xi b that this restriction is removed; but this point will not be gone into here.

EXAMPLES OF FORMAL SYSTEMS

23

III B. Rules of Procedure.·

1. If a cnv b, then b cnv a. 2. If a cnv band b cnv c, then a cnv c. 3. If a cnv b, then a a c cnv abc.

4. If a cnv b, then a c a cnv a C b. 5. If a cnv 0, then A Xi a cnv A Xi b.

Example 7. (Oodel's system P). I A. There are two kinds of tokens, constants and variables. The variables are in an infinite sequence of types, there being an infinite sequence of variables in each type. The tokens are 1. constants: O. 2. variables of the n'th type x;, x;, ... (n = 1, 2, ... ). I B. There are two unary operations, q; and - r , and three binary ones, a, Y, st, I C. The rules for application of these involve several categories of terms, as follows: 1. Elementary terms. These are classified into types. The rules are a. 0 is an elementary term of type 1. b. A variable of type n is an elementary term of type n. c. If a is an elementary term of type 1, then q; a is also. 2. Formulas. a. If a and b are elementary terms, and b is of type n while a is of type n + 1, then a a b is a formula. b. If a and b are formulas then - r a and a Y b are also. c. If a is a formula and ~ is a variable, then n ~ a is a formula. II. The only predicate is a unary predicate expressed by Godel by the words "ist beweisbar" 1. III A. The axioms are stated by Godel in the form of axiomschemes as in Examples 4 and 6. In order to state the 1 This mode of expression is used by Hilbert and his followers generally. The Frege sign 'f-' thus expresses the same idea as Hilbert's 'ist beweisbar'. Cf. note on Example 3.

24

EXAMPLES OF FORMAL SYSTEMS

axioms one requires recursive definitions of substitution and of free and bound occurrences of variables. Although this process is more complicated, there is no principle involved beyond what was exemplified in Example 6. I shall therefore not state the axioms in full.", III B. 1. If a ist beweisbar and --..- a v b ist beweisbar (where a and b are formulas), then b ist beweisbar. 2. If a ist beweisbar and ~ is a variable, then n ~ a ist beweisbar. This example is typical of logistic systems. Other examples of systems which may be set up in a similar fashion are Tarski's formulation of the Principia Mathematica (C 285. 13), Carnap's languages I and II (Logische Syntax), and von Neumann's formulation of the Hilbert system (C 299. 3).

Example 8. I A. I B. I C. II.

(A revised form of combinatory logic)

2.

Six tokens: E, E, B, C, W, K 3. One binary operation: a 4. If a and 6 are terms, then a a b is a term. One unary predicate: f-.

1 Note that Godel (along with Hilbert and his followers) uses the word 'axiom' in a different sense from that used here. Cf. Chapter VII. 2 C 396.2 The revision was suggested by Rosser (C 546.1). In the system of C 396.2 "rules" for E, C, W, K were, from our present point of view, axiom schemes. Rosser proposed (Lc.) a system with rules analogous to those given here. I plan to discuss the revision more fully in a paper, now in preparation, entitled "A revision of the fundamental rules for combinatory logic". The primitive frame may be made more perspicuous by introducing certain definitions. [The paper referred to has since been published; see J 6, 41-53]. 3 Additional tokens and axioms may be required for further development. The primitive frame contains only constituents needed for C 396.2. 4 In the papers cited the operation r a 1 is expressed by juxtaposition (with parentheses). This notation is more perspicuous for most persons; however the 'a' -notation is here used for systematic reasons. For the other notation reference should be made to the original papers; a brief summary is given in my address "The combinatory foundations of mathematical logic", forthcoming in the Journal of Symbolic Logic. [J 7, 49-64].

25

EXAMPLES OF FORMAL SYSTEMS

lIlA. 1. Four axioms of the form ~

aEI,

where I is B, C, W, or K. 2. For a certain defined term Q (the definition complicated to be given here), ~

IS

too

aaEEa WQ.

3. Sixteen axioms (the combinatory axioms) of which the following are typical examples: ~

a a Q a a C a a B B a a B B B B a a B a B B B.

~aaQaaBaaBaBCCaBCaaBaaBCaBCC.

a Q a aBC W a a B a a B a B aaQaBa W Ka WK.

~ a ~

III B. Twelve

1

rules as follows:

E a & ~ a E 11 --+ ~ a E a a 11. a a E a 11 & a a c --+ ~ a 11 c. a ;= ~ a I a, where I = a W K. a b a a a B a 11 c ;= ~ a b a a a 11 c. a b a a a C a 11 c ;= ~ a b a a a c 11. a b a a W a 11 ;= ~ a b a a a 11 11. a E a & ~ a b a a K a 11 ;= ~ a b a.

~ a ~ ~ ~ ~ ~

~

Example 9. I.

r

(Elementary theory of polynomials).

We distinguish in this system three categories of terms, viz. positive constants, constants, and polynomials. A. Tokens. 1. One positive constant: 1. 2. One constant: O. 3. A set of special polynomials, called variables; B.

1

we aBC.

Xv x 2' ....

1. Two binary operations: +, x. 2. Two unary operations. The first is denoted by prefixing the sign '-', the second by the exponent '-1'.

Rules expressed by

';='

are counted as two rules.

26

EXAMPLES OF FORMAL SYSTEMS

C.

1. Rules for positive constants (p.c.)

a. b. c. d.

If a and If a and If a is a If a is a

bare p.c., then a + b is a p.c. bare p.c., then a x b is a p.c. p.c., then a-I is a p.c. p.c., and a = b 1, then b is a p.c.

2. Rules for constants.

a. b. c. d.

If a is a If a is a If a is a If a is a

p.c., then a is a constant. p.c., then - a is a constant. p.c., then (- at 1 is a constant. constant and a = b then b is a constant.

3. Rules for polynomials (poly). a. Every constant is a poly. b. If a and b are poly. so is a + b. c. If a and b are poly. so is a x b. d. If a is a poly., so is - a. II. One binary predicate, =. IlIA. Axioms. 1. A set of axiom schemes for a commutative ring with unit, without the existential assumptions as to 0, I, and - a, whose existence is already guaranteed. 2. If a is a p.c. or - a is a p.c., a x a-I = 1. B. Rules of Procedure. 1. a = b ~ b = a. 2. a = b & b = c ~ a = c. 3. a 4. a

= b ~ a + c = b + C. b ~ a x c = b x c.

=

N.B. For polynomials mod 2 referred to in Example 5, we can enumerate the constants completely, and so obliterate I C I 1 Here we have a theoretical hypothesis in a morphological rule, This is an eventuality not explicitly considered in Chapter IV. Since the hypothesis in question is definite there should be no objection to this in principle. Moreover it is evident that the rules ld, 2c, 2d may be dispensed with without altering the system so as to affect its acceptability. See also the Appendix.

EXAMPLES OF FORMAL SYSTEMS

27

and 2. a-I is not necessary. We have the additional axiom schemes:

a+a=O a x a = a. Since a good deal has been said about the similarity between mathematics and chess, it may be interesting to see how chess would look if formulated as a system. For tokens we should have the various kinds of pieces and pawns (in two colors) and blanks. There would be no operations, - all terms would be tokens. There would be one predicate of 64 arguments; an elementary proposition would be a statement to the effect that each of the 64 places was filled by a piece, a pawn or a blank. There would be one axiom, the initial position. The rules would state the possible moves. An elementary proposition would be true if and only if the position stated were possible. Evidently the system presents no interest, and the game element has vanished completely.

VI ONTOLOGICAL DISCUSSION OF A FORMAL SYSTEM

Having seen the detailed definition of a formal system (from the present viewpoint) together with some illustrations, we shall now inquire in what sense the primitive frame of a formal system is a definition, and what is the fundamental nature of that system and its constituents. As a starter for this discussion let us leave aside, for the moment, the question of the nature of the terms, and tum to the theoretical aspects. On the face of it the conventions III give one the impression that what is really being defined there is the word 'true'. Far from it. As pointed out at the beginning of Chapter IV, 'truth', 'proposition' and similar words are expressions of ordinary discourse. In III we are concerned with defining the elementary predicates of the system. For in III we have a recursive method of generating all the elementary theorems, and this gives a recursive definition of all the true instances of all the elementary predicates. On the other hand, in II we have a similar enumeration of all the sets of arguments for which those predicates are significant. The two together define the predicates in extension. In extenso then - assuming that we know what the terms are the predicates are uniquely defined by the primitive frame. In regard to the terms, however, the situation is entirely different. We have seen that concerning the tokens the primitive frame says nothing whatever. We can therefore take for those tokens any objects we please, and similarly we can take for operators any ways of combining these objects which have the requisite formal properties 1. We can, for instance 2, take the 1 The only formal property of any significance is the number of objects to be combined by each operator. The classification of terms into kinds and other morphological notions are then defined. 2 Cf. Lewis C 215.9, Chapter VI, Section iii.

ONTOLOGICAL DISCUSSION OF A FORMAL SYSTEM

29

tokens to be buttons of different kinds I, and the operators to be rods with the proper number of strings, to which buttons or other objects can be attached, and with a loop for attachment to a string from another operator. Then the terms will all be determined; they will be certain combinations of buttons, rods, etc., in which no strings are left unattached. Then - just to emphasize the preceding paragraph - the predicates will be certain classes, relations, etc., of these artifacts which are determined recursively and uniquely by the primitive frame. Let us call any way of looking at a formal system in which the tokens and operators 2 are interpreted in some way, but the predicates are defined by the primitive frame 3, a representation of the system. There are four types of such representations which are or have been of some importance. In the first place the tokens 4 may be thought of as physical objects, as in the above example, Secondly, they may be regarded as the symbols of an underlying object language; this will concern us in Chapter VIII. Thirdly, the names of the tokens may be taken as variables 5 (cf. Keyser's notion of "doctrinal function"). Finally, we may have a conceptualistic representation with, perhaps, a definite philosophical position in regard to the nature of such things; this is a relatively sophisticated notion, but is sometimes suggestive 6. It is evident 1 We require different instances of the tokens, and therefore we think of a token as a species of object rather than as an individual. I Strictly it is the names of these objects which are interpreted. 3 Note that the primitive frame leaves open possibilities for varying the predicates in "intension" - whatever that may mean - and there may conceivably be variations in such meaning of the predicates in different representations. t In the following I shall speak of a representation as determined by the nature of the tokens, although of course operations must be considered also. a This word is used here in an intuitive sense. It is to be distinguished from 'variable' as denoting a category of tokens. The description is somewhat inexact - see the next paragraph. • For instance the Example 8 above was suggested by an essentially conceptualistic view (of, the introduction to C 396.1 and C 396.2). On the other hand it has had uses quite independent of that representation.

30

ONTOLOGICAL DISCUSSION OF A FORMAL SYSTEM

that every formal system - even apart from such questions as consistency, - has a representation in one or more of these ways. The third of these representations requires some special comment. It is motivated by the simple consideration that since the tokens are unspecified, the symbols for them must be variables. But one who adopts this view must change somewhat the language in which he describes a formal system. Strictly speaking, we now have no tokens; in the specifications I A we no longer have a list of objects, called tokens, but a list of names. Furthermore what we have called propositions will become propositional functions. Neverthelesss it is evidently possible to translate the formulation of Chapter IV into a language suitable for this point of view. Such a translation will change nothing essential. The token names will still be used as if they were the names of specific obje.cts. Moreover, since the truth of the propositions will be determined without regard to the values given to the variables, it will be permissible to regard these variables as apparent, and the propositions will still be propositions. In this generalized sense the doctrinal function can be regarded as one of the representations of a formal system. The upshot of this is that although a formal system may be represented in various ways, yet the theorems derived according to the specifications of the primitive frame remain true without regard to changes in representation. There is, therefore, a sense in which the primitive frame defines a formal system as a unique object of thought. This does not mean that there is a hypostatized entity called a formal system which exists independently of any representation. On the contrary, in order to think of a formal system at all we must think of it as represented somehow. But when we think of it as formal system we abstract from all properties peculiar to the representation. Human beings can think abstractly about quite concrete things without inventing mystic abstracta to account for the phenomenon. It is unnecessary to inquire further into the meaning of a formal system. It is characteristic of mathematics that it considers only certain essential properties of its objects, regarding others as

ONTOLOGICAL DISCUSSION OF A FORMAL SYSTEM

31

irrelevant. One of these irrelevant questions is that of the ontology of a formal system I. The question of which representation is the real or essential one is a metaphysical matter with which mathematics has no concern. Moreover, since one point of view will sometimes suggest ideas which are closed to another, it is not in the interests of progress to insist on one sort of representation. On the contrary, we should adopt something analogous to the Tolerance Principle of Carnap in regard to ontological questions. For the purposes of mathematics it is sufficient to have criteria for recognizing a formal system as such, and for deciding which propositions are true; and for this we can simply say that we shall think of the tokens as objects of some sort, - what objects, we neither know nor care. A few remarks concerning the nature of elementary propositions will close this discussion. It is evident that an elementary proposition affirms as part of its meaning the existence of a proof of itself. We have noticed, too, that the question of whether a given series of propositions constitutes such a proof is a definite question. Let us be more explicit about this. Suppose that Q is an elementary proposition, and that P v ... , Pm are elementary propositions constituting an alleged proof ofQ. How do we check this up? Thus: first we ascertain if Pm is the same as Q; if it is we go on, if not, we are through. Next we examine PI; if we have a proof it must be an axiom and this we can decide by a finite process. Next we examine the other Pi in order. For Pi (having checked P v P 2 , ••• PH) we first find out if Pi is an axiom; if not, and the number of rules is finite 2 we can tell by a finite process whether Pi is a consequence of some subsequence of P v P 2 , ••• Pi-I' by virtue of a rule of procedure 3. If we continue this process through Pm and everything 1 The exact relation between a proposition and a sentence is another cf. above. 2 If this is not true then we should require of a proof not only that the steps be given but the reason for the inclusion of every Pi' This is what we require of proofs in practice anyway. 3 It is conceivable that we might want to include the case where the

32

ONTOLOGICAL DISCUSSION OF A FORMAL SYSTEM

checks, then Q is verified. It is evident that this is an essentially mechanical process. The intuitive information involved depends of course on the complexity of the structural relations; but in the case of a simple system like Example 8, this intuition is extremely rudimentary. By no stretch of the imagination can it be claimed that there are any logical principles involved - it is a demonstratio ad oculos, It is difficult to imagine a process more clear cut and objective. On the other hand what meaning does Q have when no demonstration is at hand? In general we have no finite criterion for deciding whether a proof can be found; in fact, we have often no finite criterion for establishing the denial of Q, so that (apart from idealistic assumptions) the negation of Q has no meaning. But Q does have a meaning as a problem; we can tell when we have the answer 1. Whether it is proper to call such a notion as this by the name 'proposition' is a purely linguistic question, but we must have some name for it. Propositions of that sort form the very soul of mathematics. A final remark is that an elementary (or other formal) proposition is relative to the system. Strictly speaking, when we set up a formal system we should use wholly new symbols for the names of its primitive constituents; the primitive frame then defines, in the sense we have just discussed, the meanings of these symbols and of the sentences stating the elementary propositions. Apart from the primitive frame, these sentences would be literally meaningless. In practice, however, we often use symbols which are already significant in some other connection, e.g, as the names rules gave a sufficient condition that Pi should be a consequence of P 1" •• ,Pi without there being an obvious method of deciding whether a preassigned Pi has that property. For an example of such a system see my paper "A formalization of recursive arithmetic", American Journal of Mathematics 63, pp. 263 -282 (1941). In this system the rule of mathematical induction has a premise which refers to the existence of a proof in a more elementary formal system. In such a case the argument in the text must modified in an obvious manner. 1 Cf. Carnap, Logical Syntax (C 352.12 or J 4, 82), § 43.

ONTOLOGICAL DISCUSSION OF A FORMAL SYSTEM:

33

of analogous notions in another system. When we do this these symbols, and hence the sentences containing them, become ambiguous; they are sentential functions which state propositions only when the system is specified. An elementary proposition makes an assertion about its system.

VII REDUCTION OF A FORMAL SYSTEM The examples considered in Chapter V have a very varied structure as to the number of primitive ideas and the complexity of their morphology. There are various ways by which these constituents can be reduced without altering the essential character of the system. In this section I shall give an account of some of the simpler of these reductions, with some remarks about formal theories of special forms. The first of these reductions is the elimination of all predicates except a single unary one. This can be accomplished as follows. Suppose the predicates in the original system are FI> F 2 , ••• where F i has n i arguments 1. With each F i let us associate a new 2 operation Cf!i applicable to the same sort of arguments as F i • Let r- be a new unary predicate. Then if throughout the primitive frame we replace 'Fi 01 02 ..• lln/ wherever it occurs by 'r- Cf!i 01 02 ... lln/ the new system will have the character required. The elementary theorems in the two systems will be intertranslatable; but the terms in the newer system will be more extensive than those in the old, owing to the presence of the new operations; and the same is likely to be true of the elementary propositions unless we restrict them - by introducing a new kind of terms called formulas - to the form rr- Cf!i 01 02 ... a~il where 01> 02' ... , Oni are arguments suitable for F i • This reduction is so simple that it has been generally used in the case of formal systems with a logical significance. Where it is used it allows a rather different form to be given to the theoretical rules III. In outline this is as follows. Let us say that We assume that each predicate has a prescribed number of arguments. Predicates with a variable number of arguments can be reduced to an assemblage of predicates each with a fixed number. 2 It is conceivable that for 'Pi or r- we can take notions already formulated in the system. Similarly for analogous cases below.

35

REDUCTION OF A FORMAL SYSTEM

rr-

a is a formula when and only when a1 is an elementary proposition; a is an axiom formula when and only when a1 is an axiom, and b is directly derivable from al> a2 , ••• , an when and only when a l & t-- a2 & ... & an-+ b1 is a rule of procedure. In terms of these definitions we can recast the conventions III 80 as to deal with formulas instead of elementary propositions, i.e. we can take III A as defining the axiom formulas and III B the relation of direct consequence. The two together define by recursion a class of deriveable formules, and we can replace a1 by (or interpret it as) fa is a deriveable formula", This is, essentially, Hilbert's conception of a formal system. From what has been said in the preceding paragraph it is evident that the differences between it and the conception of Chapter IV are inconsequential. Yet the latter conception seems to me to have two advantages: 1) it is more natural to think of a theory as a set of propositions than as a set of formulas, and 2) it fits directly to such a system as that of Example 9, which is a formulation of some facts of high school algebra. It is thus the more elementary notion of the two. The second reduction is to a single binary operation. Suppose the operations of the system are TI' T2' ... - where Ti has n i arguments. Let a be the new binary operation, and let fI' f2' ••• be a series of new tokens. Then replace 'tp, al a2 ••• an/ wherever it occurs by 'ani t, a l a 2 ••• an/ where 'a n/ stands for 'a' repeated n i times. The resulting system has only the operation a. Of course the notion of term will be more extensive in the new system than in the old, unless the application of a is restricted by (presumably) complicated morphological rules. This reduction is due to Schonfinkel '. A third reduction, also due to Schonfinkel, is to a single token. Let the tokens be aranged in a sequence ~,a2' aa . . .. Let c be a new token, then if we define

fr-

r-

rr-

r-

fr-

8. 1

-

acc

-

aC8.2

8. 2 1

C 304.1.

aa

a~

36

REDUCTION OF A FORMAL SYSTEM:

we have a system with only one token. If we combine all three of these reductions we reduce to a system with one token, one binary operation, and one unary predicate 1. The reductions just discussed do not essentially simplify the morphology of the system - i.e, they do not remove the necessity of having separate categories of terms, or the necessity of having variables - in fact they tend to complicate it, as we can see by applying the second reduction to Example 4. But it is evident that we may simplify the morphology in any reasonable case by transferring it, so to speak, into the theory proper. That is, we can add the morphological predicates and operations to the elementary ones and formulate the rules concerning them in the form of postulates (e.g., Example 2 formulates part of the morphology of the system in § 2 of Tarski's Wahrheitsbegriff) 2. In that case there would be only one category of terms, and it would not be necessary to state any rules of formation beyond giving the number of arguments for each operation and predicate. The natural formulation of the primitive frame on such a basis would be I. Primitive Ideas. A. Tokens. B. Operations, classified as to number of arguments. C. Predicates, classified as to number of arguments. II. Primitive Theorems. A. Axioms. B. Rules of Procedure. This formulation removes some of the vagueness inherent in the definition of Chapter IV. Because the morphology is formalized as well as the theory, let us call such a system a completely formal1 Chwistek in some of his recent work, seems to have a system with this minimum of primitive ideas. He uses '.' for 'a'. I C 285.16.

REDUCTION OF A FORMAL SYSTEM

37

ized system 1. I had considered taking it as a definition of formal system as such. But in most theories there is a certain class of theorems, of a relatively trivial nature, which it is convenient to take unformalized. Hence the formulation of Chapter IV is more easily fitted to existing theories than that of a completely formalized one. The system of Example 8 is an example of a completely formalized system in which the first two reductions have been carried out - the third offers no advantage in that case. There is, however, another reduction which has been accomplished in Example 8, viz. the elimination of variables. This matter is too complicated for us to go into here. However, it has been shown that Example 6 can be reduced, in a certain sense, to a sub-system of Example 8. I conjecture that practically any system can be formulated without variables by making appropriate additions to Example 8. 1 We can characterize a completely formal system as one in which all non-trivial recursive definitions necessary to define the system are made theoretically.

Vln FORMAL SYSTEMS AND SYNTAX A notion closely related to that of a formal system and now, thanks to Carnap, widely prevalent, is that of a syntax of a language. In this chapter we inquire into the relationships of that notion to the formal systems in the sense of Chapter IV. I shall argue that the two notions are essentially equivalent, and then shall turn to some criticisms of the syntactical point of view in general. These criticisms may be skipped without affecting anything in what follows. According to Carnap a language consists of a certain stock of symbols from which can be formed certain finite linear series called expressions. A rule, theory, or the like is called formal if it deals with these expressions as objects in such a way as to take account solely of the kind and arrangement of the symbols of which they are composed. Certain rules of this character are given to us in advance, and the syntax of the language is the systematic study of these rules and their consequences. The given rules are of two kinds. The first kind, called formation rules, determine a certain category of expressions called sentences, and also a classification of other expressions into categories with reference to their role in forming sentences; the second kind, called transformation rules, specify under what circumstances a sentence (we may call it the conclusion) is a direct consequence of a set of sentences called the premises. There may also need to be, in connection with these, definitions of auxiliary kinds of expressions. In all discussions of syntax we are concerned with two languages - or rather two different senses of 'language'. On the one hand there is the language under discussion, called the object language or O-language, - which mayor not be a language in the ordinary sense. On the other hand there is the language in which the discussion is conducted - which is a language in the ordinary sense

FORMAL SYSTEMS AND SYNTAX

39

- let us call it the S-language (i.e. syntax language). I shall use the prefixes '0' and'S' to distinguish notions belonging to these two languages. Is every formal system representable as the syntax of an 0language? Well, we can certainly find a representation in which the tokens are O-symbols and the operations are ways of combining O-expressions into linear series along with other O-symbols, i.e, we can assign to each operator q; an O-symbol, say '/' and then say that if aI' as, ... , an are any O-expressions, q; al as . .. a" is the O-expression got by writing in a row first '/' then the aI' az, ... ,an in order 1. The terms of the system will then be expressions of an O-language; but in general they will not constitute all the expressions of that language, so that at best we have only a part of the syntax. For the most general kind of formal system this is as far as we can go; because, although the predicates are formal in Carnap's sense, it is undetermined whether any of them will correspond to rO-sentencel, or whether there will be rules defining a term as a direct consequence of a class of other terms. Suppose, however, that we have a formal system with only one unary predicate. Then we can make the following definitions (for the terminology see Chapter VII): an O-sentence is the same as a formula; an O-sentence is a direct consequence of the null class when and only when it is an axiom formula; it is a direct consequence of the non-null class K when it is directly derivable from the members of K. Then the formal system will in fact become a part of the syntax of an O-language. It is evident that this will apply even for an indefinite system, since Carnap allows indefinite consequence rules. We note in passing that this language may be strangely and wonderfully made. In the case of a completely formalized system every term will be an O-sentence; and the O-symbols will consist of sentences and co-ordinating conjunctions only. This is not 1 This requires of course that the number of arguments to every operator be fixed. Then parentheses are unnecessary. Alternatively we may place the between commas, enclose the resulting expression in parentheses and prefix an '/' to the whole - this is the ordinary notation.

n,

40

FORMAL SYSTEMS AND SYNTAX

surprising in the case of Example 3 because - taken intuitively as a logic - it had that character to start with; but in the case of Example 8 it is a little strange in view of the properties of that system mentioned at the end of Chapter VII. Incidentally, for systems just alluded to, the O-expressions which. are not terms are intrinsicly meaningless, like 'Bats live in caves and or'. Let us now consider the converse question, can the syntax of a language be set up as a formal system? The first step in such a procedure would be the formal definition of expressions as a category of terms. The fundamental operation in the given syntactical theory is combining two expressions by writing them consecutively; let us call this, after Quine, concatenation. This is an associative operation. Hence if we take it as a fundamental operation in our formalized syntax, we run into the difficulty that an expression is not formed from the O-symbols in a unique manner. This would make it necessary to take as terms not the analogues of the expressions themselves, but of methods of constructing them, and then to formulate, morphologically or theoretically, a relation of equality. However Hermes has shown that we can take instead a set of unary operations, one for each symbol, whose interpretation is writing that symbol after the operand 1. The idea of this is shown in Example 2; but it is not necessary to be so formal here, - we can simply take III A 2 and 3 as a recursive definition of a morphological operation. We then have the O-expressions formalized as expression terms. The formation rules can then be taken over bodily into the system, replacing each category, etc. of expressions by the corresponding category, etc. of expression-terms. Corresponding to the 0sentences we have the formulas among the expression-terms. Next take the rules of consequence. Let the axiom-formulas correspond to those O-sentences which are direct consequences of the null class, and let the other rules of direct consequence be set up as rules of procedure. We then have the syntax set up as 1 Of course one can take instead the symbols as tokens and a single operation of affixing a token to an expression. (This is an instance of the second reduction of § 7).

FORMAL SYSTEMS AND SYNTAX

41

formal system, definite or indefinite; if the rules of the syntax are definite the formal system will be definite also. The preceding argument has necessarily a somewhat heuristic character. It is therefore instructive to see how it goes through in a special case, say Carnap's Language II. In this case we have a type structure so complicated that it is advantagoous to take a special category of terms to represent the types. Then we take as syntactical predicates: r- is a variable', r- belongs to ---l, r_ is a type", r_ is a sentence'. We shall need in connection with argument series concatenation of types as well as of expressions. Using 'A' for the concatenation operation we get a series of rules of which the following are samples: There is one special type: Z (numbers). If t 1 and tz are types, so are t 1 A tz, t 1 : tz, and (t1 ) . If Q 1 belongs to t1 and ~ belongs to tz then Q1 A ',' A Q2 belongs to t1 A tz. If Q1 belongs to (t1 ) and b belongs to t 1 , then Q1 A '('A b A')' is a sentence. If Q1 is a sentence, Q2 belongs to Z and Q2 is a variable, then '('A K A ~ A')' A Q1 belongs to Z. It appears from the above discussion that "formal system' and rsyntax of a language' are essentially equivalent notions. Aside from the representation, the only difference is that a syntax is by definition tied to the fundamental operation of concatenation. From an abstract point of view, "the syntax of a language .... is concerned, in general, with the structures of possible serial orders (of a definite kind) of any elements whatsoever"; from the same point of view a formal system is concerned with the structures of arbitrary combinations of any elements whatever. The notion of formal system is thus more general; but this generality is rather trivial since an arbitrary formal systen can be embedded in a syntactical one. The syntax of a language is then, essentially, a formal system represented in a certain way. It is now necessary to deal with the view, which seems to be prevalent among those addicted to syntax, that a discourse is only formal insofar as it is syntactical, - or in other words that 8.

42

FORMAL SYSTEMS AND SYNTAX

a formal system must be represented syntactically if it is significant at all. If this were to mean simply that a reader, in considering a formal system, must have some such representation in mind, then it would be superfluous to add anything to what has been said in Chapter VI. But the syntacticians appear to have something more specific than this in mind. Thus Carnap writes as follows: 1 "In a treatise by a distinguished logician, the following sentence occurs: ,(~) a is a formula which results from the formula a when the variable x (if it occurs in a) is replaced throughout by the combination of symbols p' 2. Here we are from the beginning completely uncertain as to the interpretation. Which of the symbolic expressions in this statement are used as autonymous designations and are accordingly to be enclosed in inverted commas if the correct mode of expressing the author's meaning is to be achieved? '" We do not know to which object-language all the formulae, as syntactical formulae, are to refer." It appears that Carnap is demanding that a formal system be the syntax of a particular, explicitly stated, language 3. If so, there are several special criticisms to be added to those of Chapter VI. To begin with this would require a duplicity of symbolism. One must have the a-expressions themselves and also their Sdesignations, and if we are to be exact these must be kept distinct. Logical Syntax, p. 159. The sentence quoted does not occur in any logical treatise that I know of, and neither does the German translation of it in the original edition. But in Heyting's paper C 385.3, p. 58 the following sentence 1

2

occurs: "Zweitens fiihren wir die Bezeichnung

(~) a ein fur 'der Ausdruck,

der aus a entsteht indem man die Veranderliohe x uberall, wo sie auftritt, durch die Zeichenzusammenstellung p ersetzt' ". I am assuming this is what is referred to. 3 This language must be such as can be represented in the printed page, and not counters, noises, etc. of which Carnap indicates the possibility (Logical Syntax § 2). Such will be considered non-linguistic in what follows).

FORMAL SYSTEMS AND SYNTAX

43

Moreover the usual procedure is to take for a-language some more or less familiar set of marks; then for the S-designations of these we are confronted with wholly unfamiliar symbols of an outlandish kind. But - assuming the discussion is a formal one - the a-symbols do not appear in the main part of the argument at all; they only occur in the introductory discussions. This greatly increases the difficulties of comprehension 1. Why not, then, abolish the object language altogether! Certainly the theory would be more perspicuous if the ordinary symbols were used syntactically, while the object language is left to the reader's imagination or explained by means of other symbols 2. This would also be more in accord with our mathematical habits; for in mathematics we do not talk about our symbols, we use them. Again the syntactical point of view leads to an extreme nominalism which is foreign to mathematics. By this I mean that syntax tends to make purely linguistic accidents appear on a par with more substantial considerations. In mathematics we abstract not only from meanings of our symbols - from the nature of the objects which they denote - but also from the peculiarities of their external structure. Our symbols are not intrinsically meaningless, but their meaning is unspecified; and considerations which do not have a reference to such meaning are ignored. In doing such ample justice to the first of these abstractions the syntacticians perform only lip-service 3 to the second. Take for instance the matter of commas, parentheses, etc. To the ordinary mathematician these are just devices for symbolizing an operation not readily symbolized by concatenation alone; whereas to the syntactician they are symbols which are 1 A striking example of this is the system of Tarski, for example in C 285.13 or § 2 of C 285.16). In the case of systems using quotation marks we have a further confusion in that these symbols are used in a slightly different manner in ordinary discourse. S These symbols could be words of ordinary language. Thus we can say that if 'A' and 'B' are abbreviations of the sentences p and q (named by 'p' and 'q') respectively, then 'Opq' (or 'p:J q') is a name of 'if A then B'. a Cf. Logical Syntax, pp. 5 - 6.

44

FORMAL SYSTEMS AND SYNTAX

capable of being joined with other symbols to form expressional monstrosities 1. In a formal system we can leave these useless combinations out. Our terms then have a closer relation to the essential content of our ideas. A point much belabored by the syntax-addicts is the ambiguity of the "autonymous" mode of speech, - viz. that in which a symbolic expression is used to designate itself. If the expression already has a meaning in its own right, there then arises the possibility of doubt as to whether the expression refers to itself or to its original meaning. This is a particularly serious difficulty when the original meaning is itself symbolic in character. Frege pointed out this possibility of confusion, and introduced the systematic use of quotation marks to avoid it; but the idea can scarcely have originated with him, since the same difficulty arises whenever we talk about a language within that language, and English grammars were written in English long before Frege's parents ever dreamed of the blessed event. Yet, although the distinction is important, it is not necessary to make it constantly. In particular, when the subject under discussion is non-linguistic our occasional uses of the autonymous mode of speech are usually made clear in connection with the context by a careful use of the ordinary conventions of language. Again in the syntax of a wholly uninterpreted object-language - i.e. of a system of marks without meaning - there can be no confusion in using these marks as their own names, since they have no other meaning 2. Only in case we are dealing with the syntax of an actual, interpreted language is the danger of obscurity serious. These considerations suggest that if, in dealing with a formal system, we bear in mind the possibility of a non-linguistic represenr

1 In the syntax of a language these monstrous expressions are excluded by the formation rules. Hence in seting up a syntax as a formal system we have an alternative mode of procedure to that considered above defining only such categories etc. of terms as are significant in the formation in rules. In this way Example 6 arose from Church's system. The terms there are his "well formed expressions". I This appears to be the representation which Hilbert has in mind.

FORMAL SYSTEMS AND SYNTAX

45

tation, then we may be allowed a certain liberality, which we otherwise would not have, in connection with the autonymous mode of speech. This mode has long been customary in dealing with substitution; the sentence from Reyting, quoted above, is a definition in which he follows tradition. The trouble which Carnap has with it seems to be due to his trying to force a syntactical representation where it does not belong. If he were to admit a non-syntactical representation I think he would be able to understand what Reyting means. Reyting's statement, to be sure, is incorrect; but it is clear how it is to be made correct (Cf. Example 6, above). In such cases it is often a matter of considerable inconvenience to make the analysis necessary for absolute correctness, and to insist it be done at every stage is to hamper research. All we need is to know that the correct analysis can be made. The consideration of a non-syntactical representation - perhaps alongside a syntactical one - may therefore be in the interests of progress 1. Again, in the case where the object language is an interpreted language, then we do not need a syntax language at all. For we can regard the primitive frame as being the definition (by recursion, of course) of the symbols for the formal predicates 2; these are to be regarded, then, as new technical words of the object language. Of course these predicates may be liable to confusion with intuitive predicates already in the a-language; and in that case a syntax language may be a convenience; but it is not a necessity. I do not agree that the only things which can be treated formally are symbols. This process involves certain difficulties if the object language contains variables, but we now know, in principle at least, how variables can be eliminated. In most cases in which we are actually interested in the syntax of a language, we are interested, directly or indirectly, in its subject matter also; then there is always the possibility of representing a formal system 1 I have benefited by some discussion with Church in regard to these matters; but he is not to be held responsible for the views expressed. 2 Including morphological as well as theoretical predicates. The notion of "term" must also be so defined.

46

FORMAL SYSTEMS AND SYNTAX

directly in terms of the subject matter, rather than through the somewhat artificial medium of the syntax of the language. These considerations have a bearing on the discussions in the last part of Carnap's book. As to the philosophical aspects of that discussion I am not competent to speak. I can only say, however, as a mathematician, that the fundamental thesis viz. that the confusion mentioned is due to the material mode of speech - is not proved. For the sentences listed as examples are in many cases intrinsically vague - they contain words not defined in the context, - and it is conceivable that it may be this vagueness, rather than the material mode of speech per se, which is at fault. Moreover the translations into the syntactical mode of speech do not, in all cases, have the same meaning as the original 1. To illustrate these points consider the two sentences: (1) Seven is a number. (2) Seven is an odd number. If I understand Carnap correctly he would say that (1) is a "quasisyntactical sentence in the material mode of speech" while (2) is an object-sentence. Let us examine them more closely. In the first place it is necessary to inquire after the meanings of 'seven', 'number', 'odd number'; for without these meanings both (1) and (2) are nonsense. These meanings may naturally depend on the context in which the sentences are embedded. Let us first analyze these sentences on the hypothesis that they occur in the midst of an ordinary, non-technical discussion in the English language. Now in English 'seven' is primarily an adjective; when used as a noun it is essentially only a name for the adjective. Hence 'seven' in both (1) and (2) is autonymous. As for 'number' we find in the dictionary that a number is one of a series of words 1 For example the sentences 'Yesterday's lecture was about Babylon' and 'In yesterday's lecture "Babylon", or some synonymous word, occurred', are not equivalent. For suppose the lecture had been about the breeding habits of the polar bear, but the professor had told a joke in which there was an instance of 'Babylon'; then the first sentence would be false and the second true.

FORMAL SYSTEMS AND SYNTAX

47

(or symbols) used for counting, hence it is practically synonymous with 'number word'. (1) is therefore a syntactical sentence and expresses, practically, the same meaning as (3) 'seven' is a number word. Now what about (2)? Given any series of numbers in the above sense, we can define which ones are even and which odd by a recursive definition, and this can be made intelligible to a Chinaman having no knowledge of English provided that the explanations were made in Chinese. (2) is therefore just as much a syntactical sentence as (1) is. We get some light on the relations of (1) and (3) if we translate them into German 1. The translation of (1) is evidently (4) Sieben ist eine Zahl. In considering the translation of (3) consider the sentence' 'Seven' has five letters'. To translate this as "Sieben' hat fiinf Buehstaben' would evidently be incorrect, since the latter sentence does not have the same truth value; to preserve the meaning we should have to regard "seven" as its own translation. But if we translate (3) in this way we get a sentence which would be meaningless in a German context, and we have to add a phrase of explanation. Hence we get as translation of (3): (5) In der englischen Sprache ist 'seven' ein Zahlwort.

It is evident that (4) and (5) are not synonymous for the one refers to a fact of the English language, while the other does not. Yet it is evident that (4) is the translation of (1) in the sense of non-technical discourse. Therefore (3), - which, incidentally, would not occur in non-technical, but only in linguistic discourse - is not a true translation of (1). The difference is that (1) has an abstract connotation; 'seven' there refers, not to 'seven' as a linguistic phenomenon, but to the meaning of 'seven', i.e. to rsevenl. Whether one thinks of this as an abstract concept of seven-ness or as a class of equivalent words, or what not, is an 1

This suggestion is due to Langford.

48

FORMAL SYSTEMS AND SYNTAX

irrelevant matter. But in any case to replace (1) by (3) is to distort its meaning 1. Suppose now, we take (1) in a different context. Church has shown how to define numbers in the system of Example 6 2 • In fact, let One S

=

Axl Ax2 ax l x 2 • I AX2 Axs ax2 aaxl x 2 xs'

= AX

This S is the successor-function, and in terms of it the other integers are defined successively 3. Now, suppose we take for object language the English language together with the technical words and symbols defined in the primitive frame of Example 6. Then 'number' can be defined recursively as follows: a) One is a number. b) If a is a number, aSa is a number. c) If a cnv b and a is a number, then b is a number. In that context 'Seven is a number' is an object-sentence"; Moreover in order to decide whether it is true you would have to know, not only the syntactical rules of the English language, but the definitions of 'seven' and 'number' also 5. In view of these considerations there is something which needs to be added to the indicated part of Carnap's book. The object of Carnap's whole discussion is, as I understand it, to clarify the vague sentences often propounded in philosophy. That the concept of syntax language can be a great help in that connection may 1

Another example is In antiquity seven was regarded as sacred.

'Seven' of course, did not exist in antiquity. What was regarded as sacred was rseven1. 2 This example is used, rather than Example 1, because 'number' is not a "universal word". 3 The definition of seven is then as as as as as as (one) whose normal form (in a sense defined by Church) is AX! Ax2 ax! ax! ax! ax! ax! ax! ax! x z. 4 It does not express an elementary proposition, but a metaproposition. (See below.) 5 These can, of course, be translated into the syntax language.

FORMAL SYSTEMS AND SYNTAX

49

be granted. But one can be formal without being syntactical, moreover the insistence on a syntactical point of view does not solve all the problems. To sum this all up: - the syntax of a language is essentially a formal system represented in a certain way. This representation is an importaht and fruitful one. One of its achievements is that it enables us to think of a formal system as something very concrete without losing sight of abstractness, and so incidentally to show that we do not need to presuppose mystical entities of a logical or other idealistic kind in order to be formal. But it has also certain disadvantages, and the time has come when we should sign a declaration of independence from it also.

IX METATHEORY In the foregoing we have been considering a formal system essentially as a body of elementary propositions. In the study of a formal system, however, we do not confine ourselves to deriving elementary propositions according to the rules of procedure. Rather we take the formal system, defined by the primitive frame, as datum, and then study it by any means at our command. In so doing we may consider propositions of a more complex nature; let us call these metapropositions and the method of study which gives rise to them the metatheoretic method. In this section I shall make some observations concerning these propositions and this method. Let us begin by considering some examples of metapropositions. The following classification lists some of the important types, but is not intended to be exhaustive. Figures in square brackets refer to the examples in Chapter V. A. Simple combinations of the elementary propositions, such as [1]: 0=0 & 1= 1 [1]: 2 = 5 ~ 4 = 7

B. General theorems dealing simultaneously with whole sets of elementary propositions. There are three main classes of these theorems which differ in the extent to which they make use of the closure properties implicitly understood along with the primitive frame, thus: 1. Direct deductions from the rules which are valid no matter how the system be extended, and thus involve no reference to closure properties, e.g. [1]: a = b ~ a" = b". [6]: the sufficiency part of the Church-Rosser Theorem (see below). [8]: If we define a c b . ==. ~ a a Q a b,

METATHEORY

51

then the relation r c 1 is reflexive, symmetric, and transitive 1. 2. Theorems involving a mathematical induction in the morphology, and therefore involving closure properties as to terms only, e.g. [1]: If a is a term, then a = a. [2]: The associative law for A. 3. Theorems involving an induction at the theoretical level: necessary conditions. (Negatives of the elementary propositions belong here, since the only way to prove them is to show by an induction on the rules of procedure that they are not in the class of elementary theorems). E.g, [1]: 0 -=1= 1 (i.e, ro = 11 is false). [3] (Deduction Theorem): If I- a -+ I- b then I- a :J b. (The corresponding theorem is not true for [4] and is vacuous for [5]). [6] (Church-Rosser Theorem): 2 A necessary and sufficient condition that a cnv b is that there exist a term C obtainable by a constructive process such that ra cnv c1 and rb cnv c1 are both theorems even if the symmetric law be omitted. [8]: Suppose a and b are terms. Let the system be enlarged by the adjunction of a new token X not appearing in any postulate; if in the enlarged system

aaX

c

abX

c

b.

then in the original system

a

C. Extension of the system by recursive definition of new operations or relations. In [1] we can set up a complete recursive arithmetic in this way. Other examples are Hermes definition of substitution in [2], the definition of number in [6], etc. D. Properties of the system as a whole, e.g. consistency, completeness, and resolvability. A system is consistent if not 1 Technically this belongs in 2 because these laws involve hypotheses of the type I- E a. Stated subject to these trivial hypotheses they belong in 1. 2 See Church and Rosser J I, 74 or Z 14, 385.

52

METATHEORY

every elementary proposition is a theorem; it is complete if every elementary proposition is either a theorem or implies every elementary proposition; it is resolvable if there exists a definite algorithm which, given an elementary proposition, will determine definitely whether or not it is a theorem. Examples of theorems of this class are:

[l]: The system is consistent and resolvable; it is not complete, but would become so if we adjoined the additional rules 1

o=b-+b=o o=b&b = c-+o=c 0' = b'-+ 0 = b o = 0'-+ 0 = a.

[3] and [4]: The system [4] is consistent, complete and resolvable; the system [3] is consistent and resolvable. [5]; The system is consistent and resolvable; but it is not complete (since it has no rules of procedure we can adjoin new axioms ad libitum without entailing inconsistency). [6]: The system is consistent (by the Church-Rosser Theorem) but is not resolvable 2. [7] (Godel}: If consistent it is incomplete, and its consistency cannot be proved by the methods formalized in the system. Relations between two or more systems, e.g, [3], [4], [5] are all equivalent systems - - if terms with the same designation in the above statement (Chapter V) are placed in correspondence, then the theorems are in correspondence also. [6] is equivalent to a subsystem of [8] in a different sense which cannot be explained here. E.

F. Metatheorems involving relations to extraneous considerations or infinitistic assumptions; such as the semantic investigat1 Note that the adjunction of these rules does not allow us to derive any further elementary propositions. 2 Church, Z 14, 98.

METATHEORY

53

ions of Tarski and G6del's proof of the completeness 1 ofthe elementary calculus of predicates. These examples will illustrate the idea of a metaproposition. It is evident that they involve statements of a very varied character. We shall next turn to some general remarks about metatheory. In the first place there is now no absolute separation between a metaproposition and an elementary proposition. A metaproposition is, so to speak, compounded out of elementary propositions, and is expressed in the same language as they are. This language is the language of ordinary discourse plus the words and symbols to which the primitive frame gives a technical meaning. From the point of view of Hilbert even an elementary proposition is metatheoretic; from that of Carnap it is syntactic. Moreover, some metapropositions may be formalized by extending the system; i.e. by adjoining new primitive ideas and propositions to the primitive frame, a metaproposition of the old system may be replaced by an elementary proposition of the new. Indeed that is one way of defining the metaproposition with precision. Whether we regard a proposition as metatheoretic for a system 6 1 or elementary for an extended system 6 2 is a matter of point of view. Although the latter may be more exact, often we prefer the former for the same reason that we use a meter stick instead of rushing to the international standard at Paris when we wish to measure a meter. As to the criteria of truth for metapropositions, it is evident that we cannot characterize these propositions as definitely as we did the elementary propositions. If we wished to specify the criteria of truth in detail we should have to consider the various kinds of metapropositions separately 2. In a somewhat vague 1 This word is here used in a different sense from that in which it is used above. 2 In a paper "Some properties of formal deducibility" (not yet published - for abstract see Bulletin of the American Mathematical Society 43, p. 615, no. 325). I have analyzed the propositions got from elementary ones by the ordinary propositional connectives. This analysis

54

METATHEORY

way, however, we may distinguish between metapropositions which are constructive and those which are not. A constructive metaproposition is verified by the exhibition of a process which can actually be carried through in any particular case subsumed under the hypotheses; the truth of such a proposition has the same objective character as that of an elementary proposition. A nonconstructive proposition asserts a property depending on some transfinite or other extraneous principle. For that reason such propositions were classified under F above; but of course they may lose this extraneous character by the process of formalization. One can conceive a system which is purely morphological. In fact, if we deal recursively with the conventions I of Example 1 we have such a system in which we can construct all of recursive arthmetic. This system is the prototype of all infinite systems. By a construction due to Gadel l , moreover, we can set up a practically arbitrary system within this pure morphology. Of course this is for most purpose a highly unnatural way of looking at the system; but it has shown itself to be an important conception. The importance of metatheoretic methods has been brought out in recent years by three types of development. The first of these is Hilbert's insistence on consistency proofs. The second factor is the group of incompleteness theorems, whose beginning may be detected in some theorems of Lowenheim and culmination is based on that of Gentzen. The following very special case may make clearer the discussion in the text. Let A and B be elementary propositions of a system 6. Then r A ~ Bl is a metatheoretic proposition which signifies that if A is adjoined to 6 as additional axiom, then in the enlarged system B is true. In view of the criterion of truth for elementary propositions this gives the following: There exists a sequence 01' 2 " •• , 0" of elementary propositions such that 1) 0" is B, 2) every 0i is either A or an axiom of 6 or is derived from certain of its predecessors by a rule of procedure of 6. This is a constructive property of 6 and has the same objective character we talked about in Chapter IV. [The paper was replaced by the seventh item listed in the prefaoe.] 1 C 418.3. The construction can be simplified by the above reduction to c and a. A term may then be thought of as a number in the dyadic system, likewise a series of terms.

°

METATHEORY

55

in the Godel theorem, which show (roughly speaking) that a formal system, regarded intuitively, has properties not expressible by its own elementary theorems. The third is the extreme fineness of the analysis in such systems as Example 8; where the individual steps represented by the rules of procedure are so small that we should be practically helpless without the metatheoretic methods. In the case of a syntactical system, regarded as in Chapter VIII, the elementary propositions state only the derivability of particular O-sentences; the really significant syntactical properties are metatheoretical in character.

X THE FORMALIST DEFINITION OF MATHEMATICS

We are now in a position to turn to problems of the definition of mathematics. The definition I advocate is briefly this: Mathematics is the science of formal systems. This definition should be taken in a very general sense. The incompleteness theorems mentioned at the close of Chapter IX show that it is hopeless to find a single formal system which will include all of mathematics as ordinarily understood. Moreover the arbitrary nature of the definitions which can constitute the primitive frame of a formal system shows that, in principle at least, all formal systems stand on a par. The essence of mathematics lies, therefore, not in any particular kind of formal system, but in formal structure as such. The considerations of the preceding section show futhermore that we must include metapropositions as well as elementary ones. Indeed all propositions having to do with one formal system or several or with formal systems in general are to be regarded as purely mathematical in so far as their criteria of truth depend on formal considerations alone, and not on extraneous matters. The last consideration would exclude all nonconstructive propositions from the domain of mathematics proper. For the truth of these propositions depends on idealistic assumptions of one form or another which do not arise in the case of the constructive propositions. The former are therefore mixtures of mathematics and something else. This does not mean that they do not have mathematical interest. Neither mathematics nor any other science can develop in complete isolation. As a matter of fact the mathematics which is the usual concern of working mathematicians is rarely pure; moreover it is clear that if mathematics is to be defined as above stated it would be a completely sterile subject if it were not constantly in intimate contact with its sister disciplines. Thus the propositions which arise form a

THE FORMALIST DEFINITION OF MATHEMATICS

57

non-constructive argument are not to be dismissed as per se meaningless. They have at least a heuristic value; they show what may result if something more is assumed; and in many cases they may be formalized and so give rise to purely mathematical propositions at a higher level I. Mathematics so defined, has the objective character which we demand of a science. The primary standard of mathematical rigor is the definition of the derivability of an elementary proposition, which we saw, in Chapter VI, had all the objectivity one could possibly demand. Moreover mathematics is a science, not a game, in that it consists of propositions - not formulas but real propositions - "sinnerfiillte Wahrheiten" - whose truth is determined by the fundamental definitions. The essence of mathematics is that we make definitions by recursion, and then draw particular consequences by applying the definition and general consequences by mathematical induction. There is, therefore, a certain amount of justice in the view that mathematical propositions are consequences of definitions; but, since the definitions are recursive, mathematics does not have the trivial character which that seems to imply. As to Poincare's dictum that the presence of mathematical induction gives mathematics a synthetic a priori character, I do not know what it means. Certainly mathematical induction is a corollary of recursive definitions; if we demonstrate by mathematical induction that all members of a recursively defined class have a certain property, that demonstration is constructively valid because by definition every member of the class can be reached by the inductive process. Of course there is intuition involved in all this - if one defines 1 This is the case with ordinary mathematical analysis. If one thinks of theorems of analysis as metatheorems of Example 1 - which is what the ordinary genetic treatment amounts to - then these theorems are non-constructive; but we can formalize them, i.e., we can find formal systems which include (in a certain sense) all of mathematical analysis. Thus the above definition does not exclude anything which is mathematics as usually understood.

58

THE FORMALIST DEFINITION OF MATHEMATICS

intuition properly the statement is tautological. But the question of the metaphysical nature of this intuition is irrelevant. To many of us it seems that the intuition is an empirical, linguistic phenomenon; but if one wishes to associate with it an a priori notion of pure time, or a mystic contemplation of the Absolute, or other such idea, the content of mathematics will not be affected. This account of mathematics agrees with many opinions propounded by the intuitionists and related thinkers; indeed, if we subtract from intuitionism its metaphysics, the differences between it and formalism as to the definition of mathematical truth are superficial. The emphasis on constructive methods Hilbert's "finite Einstellung" -, on recursive definitions and mathematical induction, are made by formalist and intuitionist alike. An intuitionist would insist on the primacy of the natural numbers, which we can take as meaning that he insists on working with the constructive metatheory of Example 1. There is a justification in this from the formalist viewpoint also. For Example 1 is the simplest conceivable infinite formal system, and is involved implicitly in systems like Examples 3-7, which use numerical subscripts; moreover, as remarked in Chapter IX, we can give an arbitrary formal system a numerical representation. As to the intuitionist viewpoint that mathematical reasoning cannot be confined to prescribed principles, we can point out that we have made no such restriction on the metatheoretic level. In short, there is no fundamental incompatibility between formalism and intuitionism as to the definition of truth. The essential peculiarity of the intuitionist is that he regards as important only systems of a certain kind; but this goes beyond the definition of truth and leads to considerations which we shall discuss in the next chapter. The formalist conception of mathematics is thus free from metaphysical bias, and is therefore compatible with practically any sort of philosophy. It is the only conception so far proposed which has that character.

XI TRUTH AND ACCEPTABILITY Up to the present we have been discussing the definition of mathematics as such, and the truth of its individual propositions. Now we turn to the relation of mathematics to its applications. In this connection we encounter another kind of quasi-truth concept which applies to theories as wholes. To distinguish this from truth as understood above let us call it acceptability. By acceptability, then, I mean the considerations which lead us to choose one formal system rather than another. Acceptability is a matter of interpretation of the formal system in relation to some subject matter. Such an interpretation is to be distinguished from a representation (as discussed in Chapter VI): in a representation the predicates are defined by the primitive frame; in an interpretation we associate them with notions pertaining to the subject-matter, so that the question arises as to the agreement between the truth of the propositions of the formal system and that of the associated ones relating to the subject-matter. This agreement is, then, the primary consideration in regard to acceptability. Thus acceptability is relative to a purpose - viz, the study of a subject matter - and consequently - unless the subject matter is itself mathematical - involves extra-mathematical considerations. Nevertheless it is of vital interest to mathematicians; because unless a system is acceptable for some serious purpose, no mathematician will be interested in it. It was pointed out in Chapter X that the formalist definition of mathematics requires no philosophical presuppositions. Therefore the way should be open for any person, no matter what his philosophy, to recognize the formalist definition of mathematics as a basis for discussion. Philosophical differences will then emerge on the level of acceptability. Thus an intuitionist would say that

60

TRUTH AND ACCEPTABILITY

those and only those formal systems are acceptable for which an interpretation exists such that the premises have the proper sort of intuitive evidence; 1 a Platonist would make a corresponding statement from his point of view; and so on. Formalism 2, as such, involves no commitment to any of these viewpoints and is equally compatible with all of them. Its peculiarity is that it splits the problem of the truth of a proposition related to an interpreted mathematical system into two stages: viz. the truth of the corresponding formalized proposition and the acceptability of the system as a whole. The former of these is an objective matter about which we can all agree; while the latter may involve extraneous considerations. The differences between the schools of thought in mathematics are matters of acceptability. But we have seen above that acceptability is relative to a purpose. Hence it follows that the various schools of thought are not necessarily in conflict with one another. There is not one absolutely acceptable system, but for different purposes different systems may be acceptable. In fact, any discussion of acceptability without reference to a stated purpose is pointless. Let us illustrate these points by a discussion of formalized systems of classical analysis. As primary purpose of these systems we shall take applicability in physics, although other purposes will be referred to incidentally. From a Platonistic point of view there exists a world of ideas or concepts corresponding to all the notions, finitistic or infinitistic, of classical analysis; and this world is the subject matter which 1 A rabid intuitionist would object to formalism as such; but a more moderate intuitionist could take such a view as that indicated. The later intuitionists, especially Heyting, have used the formalist methods in presenting their theories. 2 The word 'formalism' is sometimes taken as meaning the views espoused by Hilbert in their entirety, including his opinions in regard to acceptability. Here, however, 'formalism' means the view that mathematics is essentially formal in the sense of Chapter X without regard to acceptability. I suggest that the Hilbert brand of formalism should be known as Hilbertism; the view presented below, which lays greater emphasis on empirical considerations, may be called empirical formalism.

TRUTH AND ACCEPTABILITY

61

gives us an interpretation of classical analysis such that all the interpreted premises are true a priori (because they are tautologies or what not). For the study of the consequences of this assumption the classical analysis is then acceptable a priori. But although such an assumption is important as a motivation for classical analysis, yet it has nothing to do with acceptability for application to physics. To assume a connection between this world of ideas and physical reality is preposterous. The intuitionists on the other hand, claim that such an assumption passes far beyond the bounds of intuitive evidence; in fact, on the ground of intuitive evidence the premises of classical mathematics, interpreted in any reasonable way, are meaningless. They have concocted alternative systems which, they claim, have a far greater degree of intuitive evidence than the classical analysis. I think that we may agree with them in this - without accepting their views as to wherein this intuitive evidence consists --. But all these considerations are irrelevant to the present problem. For physics is an empirical science, and the question of intuitive evidence is secondary. The intuitionistic theories are so complicated that they are utterly useless; whereas the classical analysis has been extremely fruitful. This is the decisive point; and so long as this usefulness persists, classical analysis needs no other justification whatever. The acceptability of classical analysis is thus at the present state of our knowledge an empirical fact; it cannot be explained away. If it does not have direct intuitive evidence that is simply "eine bittere, aber unumgangliohe Tatsache" 1. Let us now consider the position of Hilbert. As is well known he insists on consistency as a criterion for acceptability. I suspect that the reason is that he, like the intuitionists, seeks an a priori justification. But aside from the fact that for physics an a priori justification is irrelevant, I maintain that a proof of consistency is neither necessary nor sufficient for acceptability. It is obviously not sufficient; that is admitted by Hilbert himself2. As to the 1 2

Weyl, C 192.8 p. 87. C 108.13 p. 163 - " .... wenn tiber den Nachweis der Widerspruchs-

62

TRUTH AND ACCEPTABILITY

necessity, of course an inconsistent system is useless because it is trivial. But so long as no inconsistency is known a consistency proof, although it adds to our knowledge about the system, does not alter its usefulness. Even if an inconsistency should be discovered this does not mean a complete abandonment of the system, but its modification and improvement. As a matter of fact, essentially this has happened in the past; for if we were to formulate the mathematics of the eighteenth century we should find that it was inconsistent; yet we have not abandoned the results of the eighteenth century mathematicians. So far as acceptability for physics is concerned, analysis has no more need of a consistency proof than it has of intuitive evidence. It is conceivable that we shall always have uses for systems whose consistency is unproved 1. The acceptability of classical analysis for the purposes of application in physics is, then, established on pragmatic grounds, and neither the question of intuitive evidence nor that of a consistency proof has any bearing on the matter. The primary criterion of acceptability is empirical; and the most important considerations are adequacy and simplicity 2. This does not mean that the intuitionistic formal systems are without interest, nor that there is no significance to a consistency proof. These have an importance for a different purpose, viz. an application to mathematics itself. For the intuitive evidence which goes with the intuitionist theories is closely related to the constructive validity of a metatheorem 3. Hence for formalizing freiheit hinaus noch die Frage der Berechtigung zu einer Massnahme einen Sinn haben 8011, 80 ist es doch nur die, ob die Massnahme von einem entsprechenden Erfolge begleitet ist, In der Tat, der Erfolg ist notwendig; er ist aueh hier die hochste Instanz, der sich jederman beugt". 1 Cf. also my remarks in C 396.7, p. 374 footnote. I In this discussion I have not considered the question of just how an application to Physics should be made - nor indeed of just how classical analysis should be formulated. To go into these would take too long. On the former question cf, papers by Weyl and Gentzen cited below. 3 The intuitionistic theories appear to contain assumptions which are not acceptable from the constructive point of view. Thus Godel showed

TRUTH AND ACCEPTABILITY

63

certain metatheoretic arguments an intuitionistic system, rather than a classical, may be acceptable. On the other hand a constructive consistency proof for classical analysis, if accomplished, would give a method whereby, given a classical proof of an elementary arithmetic theorem, it could be transformed into a constructive proof of the same theorem. These considerations show that while classical mathematics is acceptable for one purpose, the intuitionist mathematics may be acceptable for another purpose. This brings us to a view which has often been expressed by Weyl t, and more recently, by Gentzen 2. These papers should be consulted for analysis of this phenomenon and for a discussion of the role of ideal constructions in physics. The paper by Gentzen points out an interesting parallel between the intuitionist mathematics and the "natural geometry" of Hjelmslev. This situation may, if one likes, be looked upon as a vindication of the Platonist metaphysics. Indeed it is more natural to base an argument for Platonistic metaphysics on the pragmatically demonstrated acceptability of classical analysis than to conclude the acceptability on metaphysical grounds. Such a vindication of a form of idealism appears also to be a part of the underlying purpose of the Hilbert program. To what extent such considerations actually do vindicate idealism is a matter which I leave for the philosophers. But we have as an undeniable fact that classical analysis, motivated though it is on a naive metaphysical basis, is nevertheless acceptable on empirical grounds. This should leave us with an open mind with regard to other considerations - such as systems involving the axiom of choice, non constructive that the consistency of classical number theory could be deduced rather easily from that of the intuitionist system, while a. constructive proof of the same fact involves difficulties. (cf. Godel C 418.11) If one identifies intuitive evidence with constructive validity, then the intuitionistic systems are not acceptable on their own criterion; if not, then they admit some nonconstructive processes. 1 C 192.6-10. 2 Z 19, 97 and 241; J 3, 166.

64

TRUTH AND ACCEPTABILITY

metatheorems, etc. - in which a Platonist metaphysics is the motivation. This leads to my final plea - a plea for tolerance in matters of acceptability. Acceptability is not so much a matter of right and wrong as of choice of subject matter. Such a choice should be entirely free; and some difference of opinion is not only allowable, but desirable. We are often interested in systems for which the acceptability is hypothetical - even sometimes in those which, like non-desarguesian, non-archimedean, non-this-or-that geometries, are not acceptable for any known purpose. As mathematicians we should know to what sort of systems our theorems - if formalized - belong, but to exclude systems which fail to satisfy this or that criterion of acceptability is not in the interests of progress.

XII MATHEMATICS AND LOGIC In the current popular expositions of mathematical foundations it is customary to distinguish three main schools of thought: the intuitionist, the formalist (i.e. Hilbertist) and logistic schools respectively. The third of these view-points is said to be characterized by the fact that it reduces mathematics to logic. This appears to be a thesis in regard to the definition of mathematical truth. On closer examination, however, it is evident that we do not have a theory of mathematical truth parallel to those already considered. For, so long as 'logic' is undefined, to say that mathematics is logic is merely to replace one undefined term by another. When we go back of the word 'logic' to its meaning we find that the logisticians have very varied conceptions of logic and so of mathematics. Thus Ramsey's theory is a form of Platonism, while Carnap is essentially a formalist. Thus the relation of mathematics to logic is a question quite independent of the definition of mathematical truth. It all hinges on what one means by 'logic' - 'mathematics' we have already defined in Chapter X. Let us distinguish two senses of 'logic'. On the one hand logic is that branch of philosophy in which we discuss the nature and criteria of reasoning; in this sense let us call it logic (1). On the other hand in the study of logic (1) we may construct formal systems having an application therein; such systems and some others we often call "logics". We thus have two-valued, three valued, modal, Brouwerian, etc. "logics", some of which are connected with logic (1) only indirectly. The study of these systems I shall call logic (2) 1. 1 The two senses of 'logic' may be compared with the corresponding two senses of 'geometry' - 88 the science of actual space, or 88 the study of mathematical "geometries", some of which, like finite projective geometries, have only a remote connection with physical space. Cf. Carnap, C 352.12, § 84.

66

MATHEMATICS AND LOGIC

The first point regarding the connection of mathematics and logic is that mathematics is independent of logic (1). This point has already been made in Chapter VI and it is not necessary to go into it further. It has, however one connection worth noting: we are able to construct in logic (2) systems which stand more or less in contradiction with our intuitions of logic (1) - just as we can do the analogous thing in the case of geometry. Whether or not there are a priori principles of reasoning in logic (1), we at least do not need them for mathematics. It is evident that logic (2) is a part of mathematics. The discussions of acceptability of the various system of logic (2) belong in logic (1); moreover the facts of logic (2) form part of the data of logic (1). On the other hand the question of whether logic (2) exhausts the whole of mathematics is largely a matter of terminology - the above explanation of logic (2) was sufficiently vague to allow some latitude in that regard. Carnap's position, as I understand it, is that the criteria of validity of reasoning are essentially formal and therefore the essentially significant method of studying logic (1) is through logic (2); he identifies the latter with syntax, which, in view of Chapter VIII is mathematics. On the other hand it is evident that we can construct systems of mathematics which, at least from a naive point of view, have no connection with logic (1). Those who say that mathematics is a part of logic usually take mathematics in the sense of ordinary arithmetic and analysis. Their assertion may be interpreted thus: it is possible to construct a system of logic (2) in the narrow sense such that all arithmetic notions can be set up in it. This is what the Principia Mathematica attempted to do. But the axioms of reducibility and infinity are a difficulty and the matter is not yet entirely cleared up. On the other hand it is possible to construct systems of arithmetic, such as Hilbert's, which an ordinary person would not consider purely logical (since numbers are postulated as individuals). Furthermore, Church has shown that one can define the notions of elementary arithmetic within the systems of Example 6 (and hence also of Example 8); this shows that integers can be defined with

MATHEMATICS AND LOGIC

67

much less logical machinery than had previously been thought necessary. In sum, if one adopts a formalist definition of mathematics the question of the relation of mathematics to logic is more or less a matter of terminology. The important point is that mathematics is independent of logic (1), and can therefore be used as a tool of logical investigations. Perhaps this is the place to deal with the rather silly objection which Ramsey 1 advanced against formalism of the Hilbert type - viz. that in saying "it is two miles to the station", 'two' must have a meaning which the formalist gives no account of. But it is easy to supply such a meaning. In fact this was, in its essentials, done by Dedekind (C 701.1); a class has n members if it is similar to his Z". Of course it was never intended that a formal system should be completely isolated from its applications. Additional terms, etc. - descriptive in the sense of Carnap, - may be adjoined on the metatheoretic level. A somewhat similar objection is the following. It is known that recursive definitions can be replaced by explicit ones in a suitable system of logic. The recursive definitions of its primitive frame of a system can then be eliminated by the aid of such an underlying system. But, unless we assume that the underlying system is given a priori - which smacks of Platonism - we have to make recursive definitions in order to define the underlying system. As to the logistic theories which define 'logic' in terms of tautologies, these have a Platonist character. In fact, they make no distinction in principle between finite and infinite tautologies. Although I have not given the objections to Platonism in this paper, yet it is not necessary to reiterate arguments which are well known. The naive logistic view, which holds that "logic" is given a priori and does not need to be analyzed, has been made untenable by the paradoxes. Up to the present I have said nothing concerning the law of 1

C 295.5, p. 2.

cr.

also Carnap., Loqische Syntax § 84..

68

MATHEMATICS AND LOGIC

excluded middle. Now we cannot discuss that law until we know what it means. What does it mean to say that a proposition is either true or false? Many philosophers define a proposition, explicitly or implicitly, as that which is either true or false, and in that case there is no argument about the Le.m. Mathematicians, however, can and do use the words involved in other senses. We have seen in Chapter VI that an elementary proposition of a formal system is often such that, although we have a finite criterion for checking a proof, we have no such criterion for establishing a denial. Of course, if you take an idealist position, - that the proposition is either true or not true though it may be essentially undecidable which - then naturally the l.e.m. holds; but falsity has, in general, no constructive meaning. But if we take falsity to mean demontrable impossibility, where 'demonstrable' means by some constructive argument, then the l.e.m. holds only for such systems as have a resolution process (Entscheidungsverfahren). It follows that there are cases where the l.e.m, does not hold. The mundane proposition raIl lemons are yellow1 is an example of essentially the same thing; for although you may collect all the lemons in the world and find they are yellow, yet you cannot examine next year's crop of lemons in advance, so that it may be impossible either to prove or disprove the proposition in a finite time. This consideration leads to my final comment - that among the systems of logic (2) we have the same relativity of acceptability that we had in Chapter XII. There is no one system of logic which is acceptable a priori for every purpose under the sun. Of course one is at liberty to say that the statements considered in the preceding paragraph are not really propositions at all 2. If so then we must invent another name for them, let us call them protheses. In mathematics we deal with protheses all the time and therefore we have a need for a logic of protheses along with the logic of propositions 3. When we have enough 1 3 S

Cf. Church C 359.2, p. 77. For such a point of view cf. Goodstein, Z 20, 99 (1939). Again Garrett Birkhoff and von Neumann have argued for the

MATHEMATICS AND LOGIC

69

of such alternative logics we may realize that our religious faith which some people have in the classical logic is largely a matter of habit, and that the acceptability of systems of logic is essentially an empirical matter. This revolution in our logical conceptions is to be attributed to the rise of the formal, mathematical point of view. 1 acceptability, for physical purposes, of a system of logic involving a failure of the distributive law. It is possible that when we apply metatheoretic methods to physical systems we may have a combination of these two ideas. 1 The same point, howerer has also been urged by the intuitionists.

APPENDIX

A REFORMULATION OF EXAMPLE 9 The system of Example 9 formalizes in a rough way what we do in elementary algebra. Indeed the identities arrived at by removing parentheses, multiplying, long division with remainder, factoring, etc. are elementary propositions in that system. Naturally one can pass on to fractions, etc. by making appropriate changes. Thus the system is a counter example for the contention that the notion of formal system is confined to abstruse logical matters; likewise for the idea that logic must be presupposed before one can operate a system of elementary character. To be sure the system does not reproduce with complete adequacy the actual processes of elementary instruction; but there is enough similarity to show that elementary algebra is essentially a study of formal systems which are neither more complicated than, nor dependent on, those of logic itself. However the reasoning in elementary algebra involves the usc of inequalities as well as equalities. Thus the passage from to

a.c

=

b.c

a=b

requires the additional hypothesis c =F 0; and the neglect of this proviso leads to serious fallacies 1. 1 For a case where a fallacy of this general nature occurs in an otherwise reputable book, see G. W. Pierce, Electric Oscillations and Electric Waves. 1922, pp. 57 -58 § 59 "Condition that makes the transient term zero". Since a sine wave and its derivative can never vanish simultaneously it follows that the transient term, in the case considered by Pierce, cannot be zero under any circumstances. The fallacy arises from equating to zero the numerator of a certain fraction and forgetting that then the denominator also vanishes. (This fallacy was also noted independently by D. C. Bourgin when we were graduate students together).

71

APPENDIX

Now of course it can be shown that the system of Example 9 is resolvable, and therefore negation can be constructively defined in the meta-theory. But not only is this foreign to elementary alge bra, but it is thoroughly unsatisfactory from other points of view. Accordingly we consider here a system in which inequalities can also be derived as elementary propositions. This system involves some other changes in Example 9; if we omit everything related to inequality we may regard this system as a revision of that example. The constituents of the primitive frame as grouped in a manner suggested by Chapter VII; this is more in accord with tradition, and I now regard it as more significant than the grouping of Chapter IV. Constituents in parentheses are variants, some of which will be discussed in the comment following the formulation. I. PRIMITIVE IDEAS

A. Primitive Terms: 0, 1, x (other variables, i). B. Operations. Binary operations on a and b: a Unary operations on a: - a, a-I. C.

+ b,

a.b (or ob).

Predicates. 1. Morphological categories: (V); I; C; P. 2. Theoretical binary predicates on a and b:

a

=

b; a =J:. b.

II. POSTULATES or Primitive Propositions. A. Rules of Formation. (0. Variables - x is in V.) 1. Integers - I.

a. 1 is in I.

b. If a is in I, then a + 1 is in I. (c. If a is in I and a = b, then b is in I).

72

APPENDIX

2. Constants -

a. b. (c. d. e. f.

C.

°If isa inis inC. I, then a is in C.

If a and b are in C, then a + b is in C). If a and b are in C, then a. b is in C. If a is in C, then - a is in C. If a is in I, then a-I is in C. (f" If a is in C and a =f:. 0, then a-I is in C). (g. If a is in C and a = b, then b is in C). 3. Polynomials - P. a. If a is in C, then a is in P. b. x is in P (or if a is in V, then a is in P). c. If a and b are in P, then a + b is in P. d. If a and b are in P, then a.b is in P. e. If a is in P, then - a is in P.

D. Axiom Schemes. 1. For all a, b, c in P:

a. a + b = b + a. b. a + (b + c) = (a + b) + c. c. a + 0= a. d. a + (- a) = O. e. c.b = b .c. f. a. (b.«) = (a. b). c. g. a.l = a. h. a.(b + c) = (a.b) + (o .c).

2. For all a in I: a. a.a-1 = 1. b. a =f:. o. c. a-I =f:. o. C. Rules

0/ Procedure.

1. For all a, b, c in P:

a' If a = b, then b = a. b. If a = band b = c, then a = c.

73

APPENDIX

c. If a = b, then a + c = b + c. d. If a = b then c .c = b.c. (e. If a.b = and a then b

°

* 0,

=

2. For all a, b, c in P: a. If a b, then b a. b. If a band b = c, then a c. c. If a then a + c b + c. (d. If a. c b. c, then a b). e. If a*O and b then

* * * b, *

*

*0

*

* *

u.b *0.

3. For all a, b in 0: (a. If a then a.a- l = (b. If a then a-I

1).

4. For a in P, b in 0: a. If a then ax + b

* 0.

* 0, *° * 0,

* 0).

0).

We now consider some comments on this system. In these comments references to the primitive frame are alway to II, and therefore 'II' is unexpressed. 1. Without assuming any of the postulates in parentheses it can be shown that the system is adequate for the representation of polynomials in one indeterminate with rational coefficients. Furthermore, it is a constructive metatheorem that for any two such polynomials a and b, one and only one of the alternatives a=b holds. Thus these two alternatives are the negations of one another in the usual sense. It is a corollary of this that, when everything involving inequality is left out, the system is resolvable, and the metatheoretic inequality in the truncated system coincides with that formulated here.

*

b' is regarded as the negation of 'a = b', then the 2. If 'a rules 02 follow from the corresponding rules 01, and vice versa, by the ordinary logic of negation. This is the point of view of elementary algebra. For this and the metatheorem of the preceding

74

APPENDIX

paragraph it follows that the rules in parentheses (in Cl and 2) are superfluous. Nevertheless, it seems desirable to state them in order to give an adequate account of inequality on the elementary level. We shall see below that if B2 and C3b are dropped, we need C2d 1. It is evident that Cle is precisely the type of inference mentioned in the introduction to this Appendix. 3. The parenthesized postulates in Al and A2 do not affect the adequacy of the system for representing polynomials; but they do affect the content of the classes I and C. Thus if Alc is omitted, I is the class of terms 1, 1 + I, (1 + 1) + 1, ... ; but such terms as (1 + 1) + (- 1), 1 + (1 + 1), (1 + 1) . (1 + ltl , all of which are equal to elements I, do not belong to I; furthermore, if A2gc, are also denied. the first two of there terms do not belong to C. If A2f' is denied, then the inverse a-I is not defined except for a E I. This is an unnatural state of affairs. The only objection to these postulates is that, while morphological, they contain a theoretical premise. But there is no reason for insisting that morphological postulates must be pure. It was pointed out in Chapter VII that the ultimate in formalization is the completely formalized system; the whole distinction between morphology and theoretics is nothing but a concession to practical convenience. As a matter of fact, little has to be done to the system to completely formalize it, irrespective of whether these postulates are assumed or not. The only changes are matters of terminology - Ala, A2a, and A3b become axioms, all the rest become rules of procedure. 4. If we admit the postulates Ale, A2f' (in place of A2f) and A2g, then A2c becomes proveable and B2ac can be replaced by C3ab. Of the latter C3b becomes a consequence of C2d (put a-I 1 Note that if we did not wish to exhibit the parallelism between CI and C2 it would be more convenient to state C2d in the form

If a. b =1= 0, then a =1= 0 Likewise Cle is equivalent to the rule. If a. c = b. c and c

"* O. then a = b.

APPENDIX

75

for c, n for c, and b = 0). (The postulates C2d is then no longer superfluous. ) 5. The postulate B2b corresponds to the algebraic requirement that the characteristic be zero. For a modular field we must replace B2 by something else. We must also drop A2f, but we can use A2f'. 6. The postulate C4 states that x is an indeterminate in the sense of modern algebra. This was done in Example 9 in order to have a connection with Example 5. To represent elementary algebra one should the replace C4 by a substitution rule. In such a system inequalities c =F 0 would only be derivable for constants, and the metatheorem in negation would only apply to equations n =F 0 where a is a constant (i.e., in C or equal to a member of C). 7. It is possible to modify the system in various ways so as

to deal with several variables, algebraic (as opposed to transcend-

ental) extensions, etc. This can be done by modifications of C4. In the case of transcendental extensions with several variables we need to formulate the (morphological) predicate 'x does not occur in a'. This will not be gone into further.