The Bactra Review: Occasional and eclectic book reviews by Cosma Shalizi   9

Mathematical Logic

by Willard Van Orman Quine

Revised Edition, Harper & Row, 1962
Informal logic is an inescapable part of life as a human being with a plugged-in brain, and not a vegetable or a raving lunatic; even post-structuralists and critical theorists may be observed, off-duty, saying ``That can't be right, because...'' Formal logic is a notoriously dry subject, initiated in the West by the prince of pedants, Aristotle. Mathematical logic, which has emerged only in the last hundred and fifty years, is well known to be abstruse and terrifying, and has made the logician into a creature mathematicians view in much the same way others view mathematicians, i.e. a repository of incomprehensible knowledge. When, in 1995, the Bertrand Russell e-mail list attempted to list all those who had read all three volumes of Whitehead and Russell's Principia Mathematica, they came up with less than two dozen names; two of those people died while the list was being compiled.

A few books on mathematical logic have done well, such as Martin Gardner's Logic Machines and Diagrams, particularly since digital computers appeared. But a paperback of mathematical logic can only be viewed as an act of folly on the part of its publisher, and it would be interesting to know what prompted this one.

That said, if ever such a book deserved to do well, this one did. Quine claims to be accessible to those with no previous exposure to formal logic, or ``special training'' in mathematics, and on the whole he succeeds. (This in contrast to Russell's Introduction to Mathematical Philosophy, which the author falsely billed as requiring ``no more mathematics than is taught in primary schools, or even at Eton.'') Quine's prose has its usual Mandarin elegance, which makes everything he says seem credible, and exactitude and clarity seem easy. Indeed, when he discusses notation I found it impossible not to imagine him taking great pains over Confucian propriety and ritual, and growing his finger-nails very, very long.

The first chapter deals with logical connections between statements; these are reduced first to alternation (Boolean ``or,'' A or B or both), conjunction (Boolean ``and'') and denial (Boolean ``not''). These in their turn may all be derived from either joint denial (Boolean ``nor'', true only if both A and B are false), or from alternative denial (Boolean ``nand,'' false only if both A and B are true). Quine chooses to regard joint denial as the basic connective, and the others as abbreviations for ways of applying it. Here we also are treated to one of Quine's homilies on the distinction between use and mention, and the associated conventions of quotation, which prevent (among other things) the confusion between Boston, which is a city on the Atlantic seaboard, and ``Boston,'' a word of two syllables. Those not put off by five pages on ``Parentheses and Dots'' pass on to an explication of tautology, and thence to the meat of the book.

The second chapter discusses quantification, or how one says what a statement applies to. Universal quantification corresponds roughly to ``every,'' and more precisely to the mathematician's ``for all.'' Existential quantification --- ``some,'' ``a,'' ``at least one,'' ``there exists'' --- reduces to a combination of universal quantification and negations. With quantification goes some notation and apparatus which roughly match the pronouns of ordinary speech. An infinity of tautologous statements about quantification are baptised ``the axioms of quantification,'' and the business of proof begins. The first rule of inference is modus ponens, i.e., if ``If A then B'' is true, and A is true, then B is true, and theorems are explained as statements arrived at from axioms by modus ponens. These are supplemented by meta-theorems, statements ``describing general circumstances under which statements are theorems.''

The third chapter introduces classes, and membership in classes, and thereby an analogue for the ``is'' of common speech. Quine accepts classes as ``entities of a non-spatial and abstract kind,'' and says nominalism ``presents extreme difficulty, if much of standard mathematics and natural science is to be really analyzed and reduced and not merely repudiated.'' Properties, however, are eliminated in favor of classes --- or, as Dennett would say, properties and classes are quined:

It matters little whether we read `x \epsilon y' as `x is a member of the class y' or `x has the property y'. If there is any difference between classes and properties, it is merely this: classes are the same when their members are the same, whereas it is not universally conceded that properties are the same when possessed by the same objects. The class of all marine mammals living in 1940 is the same as the class of all whales and porpoises living in 1940, whereas the property of being a marine mammal alive in 1940 might be regarded as differing from the property of being a whale or porpoise alive in 1940. But classes may be thought of as properties if the latter notion is so qualified that properties become identical when their instances are identical.... For mathematics certainly, and perhaps for discourse generally, there is no need of countenancing properties in any other sense.

Membership thus lets us proceed to abstraction, or the forming of ``the class of all entities such that...'' Here there are notorious difficulties having to do with Russell's paradox. Some classes are members of themselves; say, the class of all classes whose members are exclusively classes. Now consider the class, let us call it w, of everything which is not a member of itself. Is w a member of itself? If it is, then it isn't; and if it isn't, then it is*. This is an altogether unsatisfactory sort of brute to have lodging in your logic, and a number of different means have been suggested to keep it --- and its myriad kin --- from taking up occupancy. Russell's own, rather desperate, expedient was the ``Theory of Types,'' in which one distinguishes between classes simpliciter, classes of classes, classes of classes of classes, etc., and needs (for instance) a different version of joint denial for each level of the hierarchy. This has the look and feel of a kludge. Quine's expedient is to restrict abstraction from ``all entities'' to ``all membership-eligible entities,'' i.e. to entities which are members of at least one class, and these he designates ``elements.'' This leads quickly to the result that w is not an element, and so not eligible to be a member of itself. A general technique for telling what can and cannot be an element is presented under the label of ``stratification.'' This, I think, graduates from kludge to hack, but one cannot help feeling that there must be a better way.

Chapter three ends with an account, following Russell, of descriptions, names, and the logical syntax of ``the.'' Chapter four, following, elaborates on stratification and the theory of classes.

The fifth chapter deals with the theory of relations. Binary relations are identified with the class of all ordered pairs of entities holding that relation. (The extra class-theory of the preceding chapter is necessary for the definition of ``ordered pair,'' which makes (a;b) different from (b;a) --- unless of course a and b are the same.) Thus the relation ``father of'' is identical with the class of all pairs of fathers and children, and ``three times'' with the class of all pairs of numbers, the first of which is triple the second. We see how to combine relations, so as to arrive at (e.g.) ``paternal grand-father'' or ``female first-cousin'' or ``ancestor''; the latter procedure is particularly important, since it underlies mathematical induction. Functions are defined, and those who speak of ``the function 5x'' are shown the error of their ways. (Relations involving three or more terms are entirely analogous, as it is easy to get ordered triples, etc., from ordered pairs.)

In the sixth chapter we derive mathematics from logic, beginning with Frege's famous definition of a natural number, as the class of all classes similar to a given class. Thus zero is the class of all classes with no members, i.e., the class whose only member is the null class. (This is not the same as the null class.) One is the class of all units, two is the class of all pairs, three of all triples, etc. This is not self-referential, since a unit can be defined as a class which, when any element is removed, becomes the null class, a pair as a class which gives a unit when any element is removed, etc.; and in fact Quine so defines them. Having acquired the natural numbers we define addition, multiplication, and raising to powers (and see that they give the expected results), greater and less, etc. We cannot, however, define either division or subtraction, since in general these take us out of the natural numbers. To cover division we define the rational numbers as relations. The fraction 1/2 is the relation between any two numbers p and q such that p=2q, and so on; subtraction and the negative numbers are entirely analogous. The construction of the real numbers is more tricky, but Quine's account is very clear, and much better than that found in most mathematics texts. Having arrived at the reals we are substantially done; complex numbers, vectors, etc. can all be seen as ordered pairs (or triples or...) of real numbers, with the appropriate rules of combination.

The seventh and final chapter is is on syntax, or purely formal properties. For me this is the least satisfactory, despite dealing with the very interesting subject of incompleteness. The initial vague definition of ``formal'' properties and statements is that they ``speak only of the typographic constitution of the expressions in question and do not refer to the meanings of those expressions.'' A more formal definition of formality is: ``translatability into a notation containing only names of signs, a connective indicating concatenation [of those signs], and the notation of logic.'' Syntax is formal discourse; protosyntax is syntax, less the notion of membership. The justification for considering this singularly unpromising beast is twofold. First, it is possible to state all the meta-theorems of the book in protosyntax; second, most discussions of incompleteness focus upon one or another notion of constructivity, such as recursion or computability. Quine considers instead protosyntactic definability, which is broader. (``Non-theorem'' is definable in protosyntax, but not by recursion or computation.) Philosophically, there is much to be said for this. As a matter of expository strategy, it is up there with invading Russia, and this is the only chapter which it is truly painful to work through. The upshot is that protosyntax is protosyntactically incomplete, i.e, ``no protosyntactically definable notion of protosyntactical theorem can exhaust the protosyntactical truths and exclude the falsehoods.'' Logic, too, is protosyntactically incomplete, because protosyntax can be modelled with the natural numbers, which are included in logic. Logic is also syntactically incomplete, i.e., adding membership to the picture doesn't help.

Indeed, a notion of theorem capable of exhausting those logical formulæ which are true and excluding those which are false will be definable only in a medium so rich and complex as not to admit of a model anywhere in the reaches of the theory of logic which is under investigation. An exhaustive formulation of logical truth which carries general recognizability with it, even of the most tenuous sort, is not to be aspired to.
And on this sober note, we end.

It would be impertinent of me to congratulate Quine on this book, but it was impertinent of me to review it in the first place. It is first-rate work, genuinely readable and perfectly rigorous, of great value to all those with any serious interest in logic, philosophy, the foundations of mathematics, computing or natural science; also to those us preparing to read Principia.

xii + 346 pp., bibliography of ``such works as happen to have been alluded to, by title or otherwise, in the course of the book,'' indices of definitions, theorems and meta-theorems, proper names, and subjects
Logic / Mathematics / Philosophy
First Edition, Harvard University Press, 1940 (but the axioms of class theory in this edition are inconsistent, prompting the second edition). Revised edition, Harvard University Press, 1951. Harper Torchbooks trade paperback of the revised edition, New York, 1962; officially in print as a Harvard University Press paperback, date of issue 1981 (but I've not seen this). ISBN 0674554515 for this last, US$16. LoC BC135 Q48.
10 February 1996