by Mario Livio
Figure 47
In 1842, Boole started to correspond regularly with De Morgan, to whom he was sending his mathematical papers for comments. Because of his growing reputation as an original mathematician, and backed by a strong recommendation from De Morgan, Boole was offered the position of professor of mathematics at Queen’s College, in Cork, Ireland, in 1849. He continued to teach there for the rest of his life. In 1855 Boole married Mary Everest (after whose uncle, the surveyor George Everest, the mountain was named), who was seventeen years his junior, and the couple had five daughters. Boole died prematurely at age forty-nine. On a cold winter day in 1864, he got drenched on his way to the college, but he insisted on giving his lectures even though his clothes were soaking wet. At home, his wife may have worsened his condition by pouring buckets of water onto the bed, following a superstition that the cure should somehow replicate the cause of the illness. Boole developed pneumonia and died on December 8, 1864. Bertrand Russell did not hide his admiration for this self-taught individual: “Pure mathematics was discovered by Boole, in a work which he called The Laws of Thought (1854)…His book was in fact concerned with formal logic, and this is the same thing as mathematics.” Remarkably for that time, both Mary Boole (1832–1916) and each of the five Boole daughters achieved considerable fame in fields ranging from education to chemistry.
Boole published The Mathematical Analysis of Logic in 1847 and The Laws of Thought in 1854 (the full title of the latter read: An Investigation of the Laws of Thought, on Which Are Founded the Mathematical Theories of Logic and Probabilities). These were genuine masterworks—the first to take the parallelism between logical and arithmetic operations a giant step forward. Boole literally transformed logic into a type of algebra (which came to be called Boolean algebra) and extended the analysis of logic even to probabilistic reasoning. In Boole’s words:
The design of the following treatise [The Laws of Thought] is to investigate the fundamental laws of those operations of the mind by which reasoning is performed; to give expression to them in the symbolical language of a Calculus, and upon this foundation to establish the science of Logic and construct its method; to make that method itself the basis of a general method for the application of the mathematical doctrine of Probabilities; and finally to collect from the various elements of truth brought to view in the course of these inquiries some probable intimations concerning the nature and constitution of the human mind.
Boole’s calculus could be interpreted either as applying to relations among classes (collections of objects or members) or within the logic of propositions. For instance, if x and y were classes, then a relation such as x y meant that the two classes had precisely the same members, even if the classes were defined differently. As an example, if all the children in a certain school are shorter than seven feet, then the two classes defined as x “all the children in the school” and y “all the children in the school that are shorter than seven feet” are equal. If x and y represented propositions, then x y meant that the two propositions were equivalent (that one was true if and only if the other was also true). For example, the propositions x “John Barrymore was Ethel Barrymore’s brother” and y “Ethel Barrymore was John Barrymore’s sister” are equal. The symbol “x · y” represented the common part of the two classes x and y (those members belonging to both x and y), or the conjunction of the propositions x and y (i.e., “x and y”). For instance, if x was the class of all village idiots and y was the class of all things with black hair, then x · y was the class of all black-haired village idiots. For propositions x and y, the conjunction x · y (or the word “and”) meant that both propositions had to hold. For example, when the Motor Vehicle Administration says that “you must pass a peripheral vision test and a driving test,” this means that both requirements must be met. For Boole, for two classes having no members in common, the symbol “x y” represented the class consisting of both the members of x and the members of y. In the case of propositions, “x y” corresponded to “either x or y but not both.” For instance, if x is the proposition “pegs are square” and y is “pegs are round,” then x y is “pegs are either square or round.” Similarly, “x y” represented the class of those members of x that were not members of y, or the proposition “x but not y.” Boole denoted the universal class (containing all possible members under discussion) by 1 and the empty or null class (having no members whatsoever) by 0. Note that the null class (or set) is definitely not the same as the number 0—the latter is simply the number of members in the null class. Note also that the null class is not the same as nothing, because a class with nothing in it is still a class. For instance, if all the newspapers in Albania are written in Albanian, then the class of all Albanian-language newspapers in Albania would be denoted by 1 in Boole’s notation, while the class of all Spanish-language newspapers in Albania would be denoted by 0. For propositions, 1 represented the standard true (e.g., humans are mortal) and 0 the standard false (e.g., humans are immortal) propositions, respectively.
With these conventions, Boole was able to formulate a set of axioms defining an algebra of logic. For instance, you can check that using the above definitions, the obviously true proposition “everything is either x or not x” could be written in Boole’s algebra as x (1 x) 1, which also holds in ordinary algebra. Similarly, the statement that the common part between any class and the empty class is an empty class was represented by 0 · x 0, which also meant that the conjunction of any proposition with a false proposition is false. For instance, the conjunction “sugar is sweet and humans are immortal” produces a false proposition in spite of the fact that the first part is true. Note that again, this “equality” in Boolean algebra holds true also with normal algebraic numbers.
To show the power of his methods, Boole attempted to use his logical symbols for everything he deemed important. For instance, he even analyzed the arguments of the philosophers Samuel Clarke and Baruch Spinoza for the existence and attributes of God. His conclusion, however, was rather pessimistic: “It is not possible, I think, to rise from the perusal of the arguments of Clarke and Spinoza without a deep conviction of the futility of all endeavors to establish, entirely a priori, the existence of an Infinite Being, His attributes, and His relation to the universe.” In spite of the soundness of Boole’s conclusion, apparently not everybody was convinced of the futility of such endeavors, since updated versions of ontological arguments for God’s existence continue to emerge even today.
Overall, Boole managed to mathematically tame the logical connectives and, or, if…then, and not, which are currently at the very core of computer operations and various switching circuits. Consequently, he is regarded by many as one of the “prophets” who brought about the digital age. Still, due to its pioneering nature, Boole’s algebra was not perfect. First, Boole made his writings somewhat ambiguous and difficult to comprehend by using a notation that was too close to that of ordinary algebra. Second, Boole confused the distinction between propositions (e.g., “Aristotle is mortal”), propositional functions or predicates (e.g., “x is mortal”), and quantified statements (e.g., “for all x, x is mortal”). Finally, Frege and Russell were later to claim that algebra stems from logic. One could argue, therefore, that it made more sense to construct algebra on the basis of logic rather than the other way around.
There was another aspect of Boole’s work, however, that was about to become very fruitful. This was the realization of how closely related logic and the concept of classes or sets were. Recall that Boole’s algebra applied equally well to classes and to logical propositions. Indeed, when all the members of one set X are also members of set Y (X is a subset of Y), this fact can be expressed as a logical implication of the form “if X then Y.” For instance, the fact that the set of all horses is a subset of the set of all four-legged animals can be rewritten as the logical statement “If X is a horse then it is a four-legged animal.”
Boole’s algebra of logic was subsequently expanded and improved upon by a n
umber of researchers, but the person who fully exploited the similarity between sets and logic, and who took the entire concept to a whole new level, was Gottlob Frege (figure 48).
Friedrich Ludwig Gottlob Frege was born at Wismar, Germany, where both his father and his mother were, at different times, the principals at a girls’ high school. He studied mathematics, physics, chemistry, and philosophy, first at the University of Jena and then for an additional two years at the University of Göttingen. After completing his education, he started lecturing at Jena in 1874, and he continued to teach mathematics there throughout his entire professional career. In spite of a heavy teaching load, Frege managed to publish his first revolutionary work in logic in 1879. The publication was entitled Concept-Script, A Formal Language for Pure Thought Modeled on that of Arithmetic (it is commonly known as the Begriffsschrift). In this work, Frege developed an original, logical language, which he later amplified in his two-volume Grundgesetze der Arithmetic (Basic Laws of Arithmetic). Frege’s plan in logic was on one hand very focused, but on the other extraordinarily ambitious. While he primarily concentrated on arithmetic, he wanted to show that even such familiar concepts as the natural numbers, 1, 2, 3,…, could be reduced to logical constructs. Consequently, Frege believed that one could prove all the truths of arithmetic from a few axioms in logic. In other words, according to Frege, even statements such as 1 + 1 = 2 were not empirical truths, based on observation, but rather they could be derived from a set of logical axioms. Frege’s Begriffsschrift has been so influential that the contemporary logician Willard Van Orman Quine (1908–2000) once wrote: “Logic is an old subject, and since 1879 it has been a great one.”
Figure 48
Central to Frege’s philosophy was the assertion that truth is independent of human judgment. In his Basic Laws of Arithmetic he writes: “Being true is different from being taken to be true, whether by one or many or everybody, and in no case is it to be reduced to it. There is no contradiction in something’s being true which everybody takes to be false. I understand by ‘laws of logic’ not psychological laws of takings-to-be-true, but laws of truth…they [the laws of truth] are boundary stones set in an eternal foundation, which our thought can overflow, but never displace.”
Frege’s logical axioms generally take the form “for all…if…then…” For instance, one of the axioms reads: “for all p, if not-(not-p) then p.” This axiom basically states that if a proposition that is contradictory to the one under discussion is false, then the proposition is true. For instance, if it is not true that you do not have to stop your car at a stop sign, then you definitely do have to stop at a stop sign. To actually develop a logical “language,” Frege supplemented the set of axioms with an important new feature. He replaced the traditional subject/predicate style of classical logic by concepts borrowed from the mathematical theory of functions. Let me briefly explain. When one writes in mathematics expressions such as: f(x) 3x 1, this means that f is a function of the variable x and that the value of the function can be obtained by multiplying the value of the variable by three and then adding one. Frege defined what he called concepts as functions. For example, suppose you want to discuss the concept “eats meat.” This concept would be denoted symbolically by a function “F(x),” and the value of this function would be “true” if x lion, and “false” if x deer. Similarly, with respect to numbers, the concept (function) “being smaller than 7” would map every number equal to or larger than 7 to “false” and all numbers smaller than 7 to “true.” Frege referred to objects for which a certain concept gave the value of “true” as “falling under” that concept.
As I noted above, Frege firmly believed that every proposition concerning the natural numbers was knowable and derivable solely from logical definitions and laws. Accordingly, he started his exposition of the subject of natural numbers without requiring any prior understanding of the notion of “number.” For instance, in Frege’s logical language, two concepts are equinumerous (that is, they have the same number associated with them) if there is a one-to-one correspondence between the objects “falling under” one concept and the objects “falling under” the other. That is, garbage can lids are equinumerous with the garbage cans themselves (if every can has a lid), and this definition does not require any mention of numbers. Frege then introduced an ingenious logical definition of the number 0. Imagine a concept F defined by “not identical to itself.” Since every object has to be identical to itself, no objects fall under F. In other words, for any object x, F(x) false. Frege defined the common number zero as being the “number of the concept F.” He then went on to define all the natural numbers in terms of entities he called extensions. The extension of a concept was the class of all the objects that fall under that concept. While this definition may not be the easiest to digest for the nonlogician, it is really quite simple. The extension of the concept “woman,” for instance, was the class of all women. Note that the extension of “woman” is not in itself a woman.
You may wonder how this abstract logical definition helped to define, say, the number 4. According to Frege, the number 4 was the extension (or class) of all the concepts that have four objects falling under them. So, the concept “being a leg of a particular dog named Snoopy” belongs to that class (and therefore to the number 4), as does the concept “being a grandparent of Gottlob Frege.”
Frege’s program was extraordinarily impressive, but it also suffered from some serious drawbacks. On one hand, the idea of using concepts—the bread and butter of thinking—to construct arithmetic, was pure genius. On the other, Frege did not detect some crucial inconsistencies in his formalism. In particular, one of his axioms—known as Basic Law V—proved to lead to a contradiction and was therefore fatally flawed.
The law itself stated innocently enough that the extension of a concept F is identical to the extension of concept G if and only if F and G have the same objects under them. But the bomb was dropped on June 16, 1902, when Bertrand Russell (figure 49) wrote a letter to Frege, pointing out to him a certain paradox that showed Basic Law V to be inconsistent. As fate would have it, Russell’s letter arrived just as the second volume of Frege’s Basic Laws of Arithmetic was going to press. The shocked Frege hastened to add to the manuscript the frank admission: “A scientist can hardly meet with anything more undesirable than to have the foundations give way just as the work is finished. I was put in this position by a letter from Mr. Bertrand Russell when the work was nearly through the press.” To Russell himself, Frege graciously wrote: “Your discovery of the contradiction caused me the greatest surprise and, I would almost say, consternation, since it has shaken the basis on which I intended to build arithmetic.”
Figure 49
The fact that one paradox could have such a devastating effect on an entire program aimed at creating the bedrock of mathematics may sound surprising at first, but as Harvard University logician W. V. O. Quine once noted: “More than once in history the discovery of paradox has been the occasion for major reconstruction at the foundation of thought.” Russell’s paradox provided for precisely such an occasion.
Russell’s Paradox
The person who essentially single-handedly founded the theory of sets was the German mathematician Georg Cantor. Sets, or classes, quickly proved to be so fundamental and so intertwined with logic that any attempt to build mathematics on the foundation of logic necessarily implied that one was building it on the axiomatic foundation of set theory.
A class or a set is simply a collection of objects. The objects don’t have to be related in any way. You can speak of one class containing all of the following items: the soap operas that aired in 2003, Napoleon’s white horse, and the concept of true love. The elements that belong to a certain class are called members of that class.
Most classes of objects you are likely to come up with are not members of themselves. For instance, the class of all snowflakes is not in itself a snowflake; the class of all antique watches is not an antique watch, and so on
. But some classes actually are members of themselves. For example, the class of “everything that is not an antique watch” is a member of itself, since this class is definitely not an antique watch. Similarly, the class of all classes is a member of itself since obviously it is a class. How about, however, the class of “all of those classes that are not members of themselves”? Let’s call that class R. Is R a member of itself (of R) or not? Clearly R cannot belong to R, because if it did, it would violate the definition of the R membership. But if R does not belong to itself, then according to the definition it must be a member of R. Similar to the situation with the village barber, we therefore find that the class R both belongs and does not belong to R, which is a logical contradiction. This was the paradox that Russell sent to Frege. Since this antinomy undermined the entire process by which classes or sets could be determined, the blow to Frege’s program was deadly. While Frege did make some desperate attempts to remedy his axiom system, he was unsuccessful. The conclusion appeared to be disastrous—rather than being more solid than mathematics, formal logic appeared to be more vulnerable to paralyzing inconsistencies.