foundations of mathematics The quest for rigour

While laying rigorous foundations for mathematics, 19th-century mathematicians discovered that the language of mathematics could be reduced to that of set theory (developed by Cantor), dealing with membership (∊) and equality (=), together with some rudimentary arithmetic, containing at least symbols for zero (0) and successor (S). Underlying all this were the basic logical concepts: conjunction (∧), disjunction (∨), implication (⊃), negation (¬), and the universal (∀) and existential (∃) quantifiers (formalized by the German mathematician Gottlob Frege [1848–1925]). (The modern notation owes more to the influence of the English logician Bertrand Russell [1872–1970] and the Italian mathematician Giuseppe Peano [1858–1932] than to that of Frege.) For an extensive discussion of logic symbols and operations, see logic: Logic systems: Formal logic.

For some time, logicians were obsessed with a principle of parsimony, called Ockham’s razor, which justified them in reducing the number of these fundamental concepts, for example, by defining p ⊃ q (read p implies q) as ¬p ∨ q or even as ¬(p ∧ ¬q). While this definition, even if unnecessarily cumbersome, is legitimate classically, it is not permitted in intuitionistic logic (see below Intuitionistic logic). In the same spirit, many mathematicians adopted the Wiener-Kuratowski definition of the ordered pair < a, b> as {{a}, {a, b}}, where {a} is the set whose sole element is a, which disguises its true significance.

Logic had been studied by the ancients, in particular by Aristotle and the Stoic philosophers. Philo of Megara (fl. c. 250 bc) had observed (or postulated) that p ⊃ q is false if and only if p is true and q is false. Yet the intimate connection between logic and mathematics had to await the insight of 19th-century thinkers, in particular Frege.

Frege was able to explain most mathematical notions with the help of his comprehension scheme, which asserts that, for every ϕ (formula or statement), there should exist a set X such that, for all x, x ∊ X if and only if ϕ(x) is true. Moreover, by the axiom of extensionality, this set X is uniquely determined by ϕ(x). A flaw in Frege’s system was uncovered by Russell, who pointed out some obvious contradictions involving sets that contain themselves as elements—e.g., by taking ϕ(x) to be ¬(x ∊ x). Russell illustrated this by what has come to be known as the barber paradox: A barber states that he shaves all who do not shave themselves. Who shaves the barber? Any answer contradicts the barber’s statement. To avoid these contradictions Russell introduced the concept of types, a hierarchy (not necessarily linear) of elements and sets such that definitions always proceed from more basic elements (sets) to more inclusive sets, hoping that self-referencing and circular definitions would then be excluded. With this type distinction, x ∊ X only if X is of an appropriate higher type than x.

The type theory proposed by Russell, later developed in collaboration with the English mathematician Alfred North Whitehead (1861–1947) in their monumental Principia Mathematica (1910–13), turned out to be too cumbersome to appeal to mathematicians and logicians, who managed to avoid Russell’s paradox in other ways. Mathematicians made use of the Neumann-Gödel-Bernays set theory, which distinguishes between small sets and large classes, while logicians preferred an essentially equivalent first-order language, the Zermelo-Fraenkel axioms, which allow one to construct new sets only as subsets of given old sets. Mention should also be made of the system of the American philosopher Willard Van Orman Quine (b. 1908), which admits a universal set. (Cantor had not allowed such a “biggest” set, as the set of all its subsets would have to be still bigger.) Although type theory was greatly simplified by Alonzo Church and the American mathematician Leon Henkin (b. 1921), it came into its own only with the advent of category theory (see below Category theory).