by Scott Soames
CHAPTER 5
MODERN LOGIC AND THE FOUNDATIONS OF MATHEMATICS
The philosophical origins of modern symbolic logic and its use in the philosophy of mathematics; the Frege-Russell attempt to explain what numbers are and what mathematical knowledge is; what was achieved, what was not, and how the program might still be advanced.
The invention of modern logic initiated by the German philosopher-mathematician Gottlob Frege, and continued by Bertrand Russell and other mathematically minded philosophers in the early twentieth century, is one of philosophy’s greatest achievements.1 Born in 1848, Frege earned a Ph.D. in mathematics from the University of Göttingen in 1873, followed by his Habilitation from the University of Jena in 1874, where he taught for his entire career. Now recognized as one of the greatest philosophical logicians and philosophers of mathematics of all time, his contributions initially went virtually unnoticed by his fellow mathematicians. He did, however, profoundly influence four young men who were to become philosophical giants of the early twentieth century—Bertrand Russell, Edmund Husserl, Rudolf Carnap, and Ludwig Wittgenstein.
Frege’s goal was to ground the certainty and objectivity of mathematics in the fundamental laws of logic, thereby distinguishing logic and mathematics from empirical science in general, and from the psychology of human reasoning in particular. In 1879, his Begriffsschrift (Concept Script) presented the new system of symbolic logic now called “the predicate calculus,” the expressive power of which vastly surpassed that of any previous system. The greatest advance in the history of the subject, its rigorous formulation rendered it capable of fully formalizing the notion of proof in mathematics.2
Frege’s logic combined the simple truth-functional logic (governing reasoning involving ‘and’, ‘or’, ‘not’, and ‘if, then’), known from the Stoics onward, with a powerful new account of reasoning involving ‘all’ and ‘some’, supplanting the far more limited syllogistic logic dating back to Aristotle. Whereas Aristotle’s theory of logical syllogisms covered only a small number of simple inferences of the sort
(i) All human beings are mortal, Cleopatra is a human being, therefore Cleopatra is mortal.
and
(ii) Some philosophers are logicians, all logicians are mathematicians, therefore some philosophers are mathematicians.
Frege’s logic vastly expanded the number of valid inference patterns, dwarfing those identified by earlier logicians.
A logic in his modern sense consists of precisely defined sets of sentences and formulas plus a proof procedure, typically consisting of axioms and rules of inference. Axioms are statements the truth of which is transparently obvious. Rules of inference—e.g., from A and If A, then B one may infer B—tell you what lines you may add to a proof-in-progress by inspecting earlier lines of the proof. A proof is, by definition, a finite sequence of lines, each of which is either an axiom or a formula obtainable from earlier lines by one of the rules of inference. A proof of Q from P is such a sequence of lines, starting with P and ending with Q. Whether or not something is a proof (in the sense of establishing that Q can’t be false if P is true) is always decidable merely by inspecting the formula on each line, without worrying about which objects and properties its expressions stand for. Thus, the status of something as a proof can always be settled conclusively. As we shall see in chapter 6, this strict notion of proof was an early step leading to the mathematical theory of computation that made the digital age possible.
In addition to formalizing proof, Frege explained how to understand the sentences of his logical language. This is done by (i) identifying a domain of objects one is using the sentences to talk about, (ii) indicating which object in the domain each name refers to, and (iii) stating, for each predicate—e.g., ‘is not identical with zero’ or ‘is an odd number’—the condition any object must satisfy in order for the predicate to correctly apply to it. A simple sentence in which a predicate is combined with names is true just in case the predicate correctly applies to (and hence is true of) the objects designated by the names. The negation of a sentence S is true just in case S isn’t true. A conjunction of sentences is true just in case each conjunct is true; a disjunction is true just in case at least one is; while what is called “a material conditional,” If P, then Q, is true if and only if it is not the case that the conjunction of P and the negation of Q is true. Finally, if S(n) is a sentence containing a name n, and the formula S(x) arises from S(n) by replacing one or more occurrences of n with a variable x, then For all x S(x) is true just in case S(x) is true no matter which object one chooses as (temporary) referent of x. For some x S(x) is true just in case there is at least one object in the domain that makes S(x) true when one assigns it as (temporary) referent of x. In this way, truth conditions of every sentence of the logical language are specified. Since there is no longest sentence, these rules are sufficient to interpret the infinitely many sentences of the Fregean language.
A sentence S is a logical truth if and only if it comes out true, when interpreted in this way, no matter what domain of objects one uses S to talk about, no matter what referents one assigns to its names, and no matter what conditions are used to define correct application of the predicates occurring in S. For example, (If P&Q, then P) is a logical truth. A sentence Q is a logical consequence of a sentence (or set of sentences) P if and only if no matter what domain of objects one uses both Q and the sentences in P to talk about, no matter what referents are assigned to their names (the same assignment when n occurs in both P and Q), and no matter what conditions are used to define correct application of their predicates (the same conditions when a predicate appears in both P and Q), Q will always be true when all the sentences in P are true. For example, For some x (Fx & Gx) is a logical consequence of Fn and Gn.
Today, these definitions are usually expressed using the notion of abstract models consisting of a domain D of objects, an assignment of objects in D as referents of names, plus an assignment, for each predicate, of conditions of correct application. A sentence is logically true just in case it is true in all models. The statement made by a use of such a truth couldn’t possibly be false. When the truth of a sentence or set of sentences in an arbitrary model always guarantees the truth of another sentence (in that model), the latter is a logical consequence of the former; hence it is impossible for the latter to be false when the former sentence (or sentences) is (or are) true. When two sentences are always either true together in any model or false together (in that model), they are logically equivalent. To Frege’s credit, all and only the sentences provable in his basic system from a set of sentences are logical consequences of those sentences.3
Dismayed by the lack of attention initially paid to this momentous advance, Frege followed five years later with a clear statement of his philosophy of mathematics in Die Grundlagen der Arithmetik (The Foundations of Arithmetic).4 In this now-classic work, he defends his vision of the objectivity of mathematics and the source of our certain knowledge of mathematical truths. He does so by (i) defining the natural numbers, (ii) outlining a strategy for proving the axioms of arithmetic from the axioms of logic plus logical definitions of arithmetical concepts, and (iii) offering the prospect of extending the strategy to higher mathematics through the definition and analysis of real and complex numbers.
In addition, starting in 1891, he laid the foundations of the scientific study of linguistic meaning by explaining, in a series of articles, the principles by which sentences—of natural languages like German and the invented languages of logic and mathematics—systematically encode information about the world. In 1893 and 1903, his grand project was brought to fruition in his two-volume work, Grundgesetze der Arithmetik (Basic Laws of Arithmetic), in which he gave detailed derivations of all arithmetical axioms from what he took to be the most fundamental laws of logic.5
Through it all, his aim was to answer two philosophical questions: What are numbers? and What is the basis of mathematical knowledge? Though, in concepti
on, his answer was simple, his key notion of a concept requires some explanation. For Frege, simple predicates like ‘is round’ and ‘is a ball’ stand for concepts, which they contribute to the truth or falsity of sentences containing them. For our purposes, we can think of concepts as conditions objects must satisfy in order for predicates to be true of them. Thus the Fregean concepts designated by ‘is round’ and ‘is a ball’ assign respectively (i) truth to anything round and falsity to all else, and (ii) truth to anything that is a ball and falsity to all else. When we combine predicates—e.g., x is round & x is a ball—we form a complex predicate that stands for the concept that is true of all and only round balls.6
With this in mind, we return to Frege’s answer to the questions What are numbers? and What is the basis of mathematical knowledge? In brief, he answered, logic is the source of mathematical knowledge; zero is the set of concepts true of nothing; one is the set of concepts each of which is true of something, and only that thing; two is the set of concepts each of which is true of some distinct x and y, and nothing else; etc. Since numbers are sets of concepts, the successor n of a number m is the set of concepts F each of which is such that for some object x of which F is true, the concept being an F other than x is a member of m. The natural numbers are members of every set that contains zero while also containing the successor of anything it contains. Multiplication is repeated addition, addition is defined in terms of counting, and counting is repeated moving from a number to its successor.
To understand Frege, one must understand his methodology. Prior to philosophical analysis we know many arithmetical truths, but we have no idea what numbers are and little understanding of how we know about them. His basic idea is that numbers are whatever they have to be in order to explain our knowledge of them. To discover what they are, we must give definitions of numbers that allow us to deduce what we pre-theoretically know. How, for example, should 2, 3, 5, and the operation of addition be defined so that Facts 2 and 3 can be logically deduced from the definitions plus our perceptual knowledge of Fact 1?
FACT 1
a. X is a black book on my desk and Y is a black book on my desk; X isn’t the same object as Y; moreover, for any object whatsoever, if it is a black book on my desk, either it is X or it is Y.
b. U is a blue book on my desk and V is a blue book on my desk and W is a blue book on my desk; U isn’t the same object as V and U isn’t the same object as W and V isn’t the same object as W; moreover, for any object whatsoever, if it is a blue book on my desk, then either it is U or it is V or it is W.
c. Nothing is both a black book on my desk and a blue book on my desk.
FACT 2
There are exactly two black books on my desk and exactly three blue books on my desk.
FACT 3
There are exactly five books on my desk.
Frege’s chief objection to earlier philosophers of mathematics was that they didn’t answer, or even really try to answer, questions like these.
He did. For him, the statement there are four moons of Jupiter is the statement that the number of things falling under the concept moon of Jupiter = 4, or, more informally, the number of moons of Jupiter = 4. For any concept F, the number of F’s is the set of concepts C such that the things that are F and the things that are C can be exhaustively paired off one with another, without repeating any F or any C, until there are no more F’s or C’s to pair off. Thus, the number of fingers on my right hand is the set of concepts C such that my thumb can be paired with a C, my index finger can be paired with a different C, and so on until each finger is paired with its own instance of C, and there are no more C’s and no more fingers to pair off.
Having conceptualized statements about numbers in this way, Frege needed the following definitions to embark on his project of deriving arithmetic from logic.
Def: Zero is the number of the concept not identical with itself.
Def: n immediately succeeds m if and only if for some concept F, and some object x falling under F (i.e., some object of which the concept F is true), n is the number of F’s, and m is the number of the concept falling under F but not identical with x.
Def: x is a natural number if and only if x is a member of every set that contains zero and always contains the successor of anything it contains.
Since everything is identical with itself, it follows that zero is the set of concepts true of nothing, that 1 is the set of concepts true of some x and only x, that 2 is the set of concepts true of some distinct x and y, and only them, and so on. The principle of mathematical induction also follows: For any concept F, if F is true of zero, and if F is always true of the successor of any natural number it is true of, then F is true of every natural number. Definitions of multiplication as repeated addition, and addition as repeated ascent from a natural number to its successor, completed the set of needed definitions.
Convinced that the highest certainty belongs to self-evident principles of logic—without which thought itself might be impossible—Frege believed that by deriving arithmetic from logic he would show the certainty of arithmetic and higher mathematics to be based on logic itself. The most basic arithmetical truths—the axioms—were to be derived as logical consequences of his definitions plus self-evident logical axioms. All other arithmetical truths were to be derived from the arithmetical axioms. When, in similar fashion, results of higher mathematics were derived from arithmetic—a process already underway—Frege imagined that all classical mathematics could be so generated. Thus, he believed, all mathematical knowledge could be explained as logical knowledge.
This was the grand structure of his program in the philosophy of mathematics. The key step was to give proofs of all axioms of the arithmetical theory now known as Peano Arithmetic.7 Relying on further reductions of higher mathematics to arithmetic, he concluded that mathematics (save geometry, for which he made an exception) is just an elaboration of logic. But there was a puzzle lurking in his plan that didn’t become recognizable until later, when the nature of logic itself had been more fully investigated. If numbers are sets of concepts, and statements about numbers are logical consequences of logical axioms, then logic itself must make claims about what sets of concepts do, and don’t, exist. But, how can it? How can a discipline devoted to specifying which inferences in any domain of inquiry are guaranteed to be truth-preserving, and which aren’t, tell us which things of a special sort (sets) exist and which don’t? Initially, this didn’t concern Frege. He assumed that for each meaningful predicate expressing a condition applying to objects, there is a set—perhaps empty, perhaps not—of all and only the objects satisfying the condition. To build this principle into logic was, in effect, to assume that talk about x’s being so-and-so is interchangeable with talk about x being in the set of things that are so-and-so.
In 1903 Bertrand Russell, who was then working on his own derivation of arithmetic from logic, showed this assumption to be false. Russell’s system, while similar to Frege’s, identified natural numbers with sets of sets, rather than sets of concepts. Like Frege, he had assumed that for every meaningful formula (predicate) in his logical language there is a set—possibly empty, possibly not—of precisely those things of which the formula is true. But he discovered that this assumption led to a contradiction.
Consider the formula x isn’t a member of x, which says of any set that it isn’t a member of itself. Since the formula is meaningful, Russell initially thought that there is a set, possibly empty, that contains all and only those sets of which the formula is true. Call that set Y. Now ask, Is Y a member of itself? If it is, then, by definition, it isn’t a member of Y; equally, if it isn’t a member of Y, then it is. Because of this, the assumptions built into Russell’s and Frege’s attempted derivations of arithmetic from logic turned out to be inconsistent.8 Although Frege never succeeded in adequately revising the assumptions, Russell spent much of the next seven years doing so, resulting in a contradiction-free derivation of arithmetic prese
nted in his and Alfred North Whitehead’s Principia Mathematica.9
Unfortunately, Russell’s way of avoiding contradiction raised questions about whether the underlying system really was logic. Whereas Frege dreamed of deriving mathematics from self-evident logical truths, some of the complications of Russell’s system were neither obvious nor truths of logic. One, the axiom of infinity, simply assumed the existence of infinitely many non-sets.10 Another, the axiom of reducibility, generated controversy from the start, while a related complication, the theory of types, imposed constraints that were difficult to justify.11 Later reductions eliminated the worst complications, but the systems to which they reduced mathematics weren’t logical systems governing reasoning on all subjects. Rather, they were mathematical systems.
The dominant theory of sets growing out of the early work of Frege and Russell is now known as Zermelo-Fraenkel set theory.12 Rather than combining set theory with logic, ZF is an independent mathematical theory with its own axioms governing thought and talk about its own special objects. The reduction of arithmetic to ZF can be achieved in several ways. But there is no question of justifying arithmetic by reducing it to set theory, since our knowledge of the latter is no more secure, or philosophically explicable, than our knowledge of the former. The great utility of set theory lies in its role as a common base to which a great many mathematical theories can be reduced and thereby productively compared.
