Read an Excerpt
Foundations of Mathematical Logic
By Haskell B. Curry
Dover Publications, Inc.Copyright © 1977 Haskell B. Curry
All rights reserved.
It is appropriate to start the study of mathematical logic by inquiring what mathematical logic is. This question will be answered in a preliminary manner in Sec. A. We shall then turn to a somewhat deeper consideration of the nature of mathematics and its relation to logic. This consideration will begin, in Sec. B, with a discussion of the paradoxes of logic and of the lessons that are to be drawn from them in regard to the logic of mathematics. We shall then proceed, in Sec. C, to a critique of the various views as to the nature of mathematics. Finally, in Sec. D, we shall return to the relation of mathematics and logic. The chapter is intended to give some background for the formal developments which begin in Chap. 2.
A. THE NATURE OF MATHEMATICAL LOGIC
We open this inquiry by examining three senses which the word 'logic' has in ordinary discourse.
The first sense is that intended when we say that "logic is the analysis and criticism of thought." We observe that we reason, in the sense that we draw conclusions from our data; that sometimes these conclusions are correct, sometimes not; and that sometimes these errors are explained by the fact that some of our data were mistaken, but not always; and gradually we become aware that reasonings conducted according to certain norms can be depended on if the data are correct. The study of these norms, or principles of valid reasoning, has always been regarded as a branch of philosophy. In order to distinguish logic in this sense from other senses introduced later, we shall call it philosophical logic.
In the study of philosophical logic it has been found fruitful to use mathematical methods, i.e., to construct mathematical systems having some connection therewith. What such a system is, and the nature of the connection, are questions which will concern us later. The systems so created are naturally a proper subject for study in themselves, and it is customary to apply the term 'logic' to such a study. Logic in this sense is a branch of mathematics. To distinguish it from other senses, it will be called mathematical logic.
In both of its preceding senses 'logic' was used as a proper name. The word is also frequently used as a common noun, and this usage is a third sense of the word distinct from the first two. In this sense a logic is a system, or theory, such as one considers in mathematical or philosophical logic. Thus we may have classical logics, modal logics, matrix logics, Aristotelian logics, Kantian logics, etc.
We may clarify somewhat the relation between these three senses of 'logic' if we consider the corresponding senses of 'geometry'. In the first sense geometry is the science of space. Etymologically the word means the measurement of the earth, and the oldest geometry is said to have been the rules of measurement of the ancient Egyptian surveyors. So conceived, geometry is a branch of physics. But alongside this there is geometry as a branch of mathematics. In this one considers mathematical systems which have some connection with the study of space. Finally, we have many sorts of geometries: we can speak of a projective geometry, a differential geometry, a nonarchimedean or a nondesarguesian geometry, a four-dimensional geometry, and so on.
Mathematical logic, then, is a branch of mathematics which has much the same relation to the analysis and criticism of thought as geometry does to the science of space.
This is as far as it is desirable to go, at present, in defining 'mathematical logic'. As a matter of fact, it is futile to attempt to define any branch of science by delimiting precisely its boundaries; rather, one states the central idea or purpose of the subject and leaves the boundaries to fall where they may. It is an advantage that the definition of logic is broad enough to admit different shades of opinion. Furthermore, it will be permissible to speak of "logical systems," "logical algebras," without giving a precise criterion for deciding whether a given system is such; it suffices that such systems have a connection of one sort or another with the analysis of thought.
There are, however, several remarks which it is appropriate to make now to amplify and clarify the above discussion.
In the first place, the connection between a geometry and actual space may be quite remote, as, for example, in the case of a finite geometry, a nondesarguesian geometry, or a geometry with infinitely many dimensions. Indeed, it is not clear just when a system is a geometry and when it is not. In this respect the situation in regard to a logic is analogous. We can and do consider logics as formal structures, whose interest from the standpoint of philosophical logic may lie in some formal analogy with other systems which are more directly applicable.
In the second place, current usage restricts 'geometry' to the mathematical aspect of the subject. Indeed, this mathematical aspect has developed to such an extent that, if one wishes to speak of the physical aspect, one is forced to use some other term. An analogous development in the case of logic has not yet taken place—whether or not it will do so in the future, as some maintain, it is not our business to decide. It is quite in accord with current usage to speak of philosophical and mathematical logic in the way it has been done here.
In the third place, although the distinction between the different senses of 'logic' has been stressed here as a means of clarifying our thinking, it would be a mistake to suppose that philosophical and mathematical logic are completely separate subjects. Actually, there is a unity between them. Mathematical logic, as has been said, is fruitful as a means of studying philosophical logic. Any sharp line between the two aspects would be arbitrary.
Finally, mathematical logic has a peculiar relation to the rest of mathematics. For mathematics is a deductive science, at least in the sense that a concept of rigorous proof is fundamental to all parts of it. The question of what constitutes a rigorous proof is a logical question in the sense of the preceding discussion. The question therefore falls within the province of logic; since it is relevant to mathematics, it is expedient to consider it in mathematical logic. Thus the task of explaining the nature of mathematical rigor falls to mathematical logic, and indeed may be regarded as its most essential problem. We understand this task as including the explanation of mathematical truth and the nature of mathematics generally. We express this by saying that mathematical logic includes the study of the foundations of mathematics.
B. THE LOGICAL ANTINOMIES
We now proceed with the program of discussing, on an intuitive basis, the nature of mathematics and its relation to logic as ordinarily conceived. We shall begin with considerations affecting the nature of mathematical rigor as it was understood at the close of the nineteenth century.
To the mathematicians of that time a mathematical proof was rigorous when it was "strictly logical." Take, for example, the theorem that if the real function f(x) is continuous for a ≤ x [much less than] b, and if further f(a)< 0 < f(b), then there is a value c such that a< c< b and f(c) = 0. Before the era of arithmetization, one could only "see" that this was true from the fact that the graph of f(x), being a continuous curve which was above the x axis at one end and below it at the other, must cross the x axis at some point. Experience with contradictions derived from such reasoning (and especially from arguments regarding infinite series without adequate investigation of convergence) showed the need for a more precise treatment. This was achieved, as is well known, by conceiving a function as a set of ordered pairs, by an arithmetical definition of continuity, and by a "strictly logical" proof of the above theorem in terms of these definitions.
But now what was the logic in terms of which such a logical proof could be defined? Certainly it was not the traditional logic, for that was inadequate to express reasonings in terms of relations (such as inequality) which were the very soul of such a proof. Indeed, it seems that the mathematicians of that time carried out their reasoning in terms of logical intuitions which were never formulated as explicit principles. Apparently it was tacitly assumed that everyone had such intuitions and that they formed an absolutely reliable criterion of rigor.
Into this situation the discovery, about the beginning of the twentieth century, that there are arguments which, although perfectly sound from the intuitive point of view, nevertheless lead to contradictions, fell like a bombshell. Such arguments are now called paradoxes, or antinomies. Some of them had been known since antiquity, but their relevance in this particular connection was not appreciated. Because of their importance for mathematical logic, it will be expedient to consider some of them here.
Russell's paradox. Our intuition tells us that we can consider classes of objects as forming new objects. Thus we can consider the class of all chairs in this room, the class of all men, of all houses, of natural numbers. Likewise we can consider classes of classes, and even such notions as the class of all classes, or the class of all ideas. Among these classes there will be two sorts, which we shall call proper and improper classes. Proper classes are those, like men, houses, numbers, which are not members of themselves; improper classes are those which, like the class of all classes or the class of all ideas, are members of themselves. Now let R (the Russell class) be the class of all proper classes. If R is a proper class, then, since R is the class of all such classes, R is a member of R, and hence R is not a proper class. On the other hand, if R is not a proper class, then R is not a member of R, and therefore R is a proper class. Either assumption leads to a contradiction.
It is instructive to express the paradox in symbols. Let the statement that x is a member of the class y be symbolized by the notation
x [member of] y
'x' and 'y' being variables for which names of arbitrary notions can be substituted, and let [??] and [??] be symbols for negation and logical equivalence, respectively. Then, by the definition of R, we have, for arbitrary x,
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
Thus the statement that R [member of] R is equivalent to its own falsehood, and hence if it is true it is also false, and vice versa.
The following two arguments, although not paradoxical, are of a nature similar to that of the Russell paradox and shed some light upon it.
Barber pseudoparadox. The council of a certain village is said to have given orders that the village barber (supposedly unique) was to shave all the men in the village who did not shave themselves, and only those men. Who shaved the barber?
Catalogue pseudoparadox. A certain library undertook to compile a bibliographic catalogue listing all bibliographic catalogues, and only those catalogues, which did not list themselves. Did the catalogue list itself?
These arguments are here called pseudoparadoxes because there is no actual contradiction. In the first case the village barber could not obey the law, which was therefore ridiculous, like that said to have been passed by an American state legislature to the effect that, when two trains approach a crossing at right angles, each one must wait until the other one passes by. Likewise, the library simply could not make a catalogue satisfying the stated requirements. But such explanations as these do not apply to the Russell paradox. In terms of logic as it was known in the nineteenth century, the situation is simply inexplicable. This is true in spite of the fact that in the greater sophistication of the present time one may see, or think he sees, wherein the fallacy consists.
Burali-Forti paradox. This, the first of the mathematical paradoxes to be published, is of a more technical nature. It involves the theory of transfinite ordinal numbers. For readers acquainted with that theory the paradox can be stated as follows. It is shown in that theory that (1) every well-ordered set has a (unique) ordinal number; (2) every segment of ordinals (i.e., any set of ordinals arranged in natural order which contains all predecessors of each of its elements) has an ordinal number which is greater than any ordinal in the segment; and (3) the set B of all ordinals in natural order is well ordered. Then, by statements (3) and (1), B has an ordinal ß; since ß in B, we have ß < ß by statement (2), which is a contradiction.
Cantor paradox. This paradox, although not published until 1932, was known to Cantor as early as 1899; it had a great influence in leading Russell to construct his paradox, in fact rather more than did the earlier paradox of Burali-Forti. It is based on the theory of cardinal numbers. According to that theory the set of all subsets of a set M has a cardinal number higher than that of M. This is a contradiction if M is the set of all sets.
We now consider paradoxes of a different sort, involving a notion of description and definition.
Liar paradox. This paradox takes several forms. The simplest is that of the man who says "I am lying"; if he lies, he is speaking the truth, and vice versa. Another version is that of Epimenides the Cretan, who is alleged to have stated that all statements made by Cretans were lies, it being understood that all other statements made by Cretans were certainly false. Modern versions give a statement to the effect that a proposition described in such and such a way is false, the description being constructed so as to apply uniquely to the statement itself. The paradox caused a great commotion in antiquity, and is said to have caused the death of a certain Philites of Cos. The first-mentioned form of the paradox seems to be due to Eubulides of Miletus; any actual connection of Epimenides with any form of it is doubtful.
Richard paradox. The following argument is often used to prove that the set of all numerical functions is nonenumerable. Suppose there were an enumeration; let fm(n) be the value, for the argument n, of the mth function in the enumeration. Form the function g such that, for any n,
g(n) = fn(n) + 1
Let p be the index of g in the enumeration, so that
g(n) = fp(n)
fp(p) = g(p) = fp(p) + 1
Since this is a contradiction, we conclude that the numerical functions are not enumerable.
Now suppose that we consider, not the set of all numerical functions, but the set of all definable ones. By 'definable' is meant, of course, definable in some fixed language, such as (mathematical) English, with a fixed dictionary and grammar. Since the number of words in the language is finite, the number of expressions is enumerable, and hence the expressions which constitute definitions of numerical functions, and thus the definable functions themselves, must also be enumerable. Now such a language can be so constituted that the above argument can be carried out in it. This again is an insoluble contradiction.
Berry paradox. The number of natural integers which can be named in English in less than a fixed number of syllables (or letters) is certainly finite; hence there must be a least number which cannot be so named. But "the least integer which cannot be named in English in less than 50 syllables" is an English name of less than 50 syllables. Various modifications exist.
Grelling paradox. Among English adjectives there are some, such as 'short', 'polysyllabic', 'English', which apply to themselves. Let us call such adjectives autological; all others heterological. Thus 'long', 'monosyllabic', 'green' are heterological. Then if 'heterological' is heterological, it is autological, and vice versa.
Skolem paradox. This argument, although not strictly a contradiction, and therefore not relevant to the main point of this section, is appropriate for consideration here because it is frequently associated with the paradoxes and, in the broad sense, has a paradoxical character. It requires some anticipation of matters which we shall take up later. According to a celebrated theorem of Löwenheim and Skolem, any system which can be formalized in the first-order predicate calculus will be such that, if it has a model at all, it will have an enumerable model. Now various systems of higher logic and set theory, within which standard proofs of nonenumerability can be formalized, come under this theorem. Of course, this means simply that, when a nonenumerable set has an enumeration obtained from the model, that enumeration cannot be obtained, so to speak, within the system, and therefore one can conclude that it is impossible to characterize the situation by means of a system of the kind considered. This conclusion appears so counterintuitive to many people, that the application of the name 'paradox' seems justified.
These examples are typical of a number of paradoxes. I shall not pause to consider more of them here, nor to discuss the great variety of attempted explanations. There are, however, a few general remarks which it is expedient to make because of their bearing on our future program.
Excerpted from Foundations of Mathematical Logic by Haskell B. Curry. Copyright © 1977 Haskell B. Curry. Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.