The Foundations of Mathematics: Hilbert's Formalism vs. Brouwer's Intuitionism

views updated

The Foundations of Mathematics: Hilbert's Formalism vs. Brouwer's Intuitionism

Overview

Different philosophical views of the nature of mathematics and its foundations came to a head in the early twentieth century. Among the different schools of thought were the logicism of Gottlob Frege (1848-1925), the formalism of David Hilbert (1862-1943), and the intuitionism of Luitzen Egbertus Jan Brouwer (1881-1966).

Background

Frege, who founded modern mathematical logic in the 1870s, claimed that mathematics is reducible to logic. That is, if all logic were understood perfectly, then all mathematics could be derived from it, or considered part of logic. This view, logicism, was always controversial, but it started important lines of inquiry in philosophy, logic, and mathematics. Bertrand Russell (1872-1970) and Alfred North Whitehead (1861-1947) adopted a weaker version of logicism than Frege's. Ludwig Wittgenstein (1889-1951) defended logicism in Tractatus Logico-Philosophicus (1921).

In 1889 Giuseppe Peano (1858-1932) introduced five axioms for the arithmetic of the natural numbers. These "Peano postulates" had extensive influence on investigation into the foundations of mathematics. The formal system of Russell and Whitehead in Principia Mathematica (1910-1913) offered rigorous, detailed derivations of Peano's arithmetic and other mathematical theories in terms of propositional logic, artificial language, and "well-formed formulas" (known as wffs).

Peano was a formalist. Formalism attempts to reduce mathematical problems to formal statements and then prove that the resulting formal systems are complete and consistent. A mathematical system is complete when every valid or true statement in that system is provable in that system. A theory is consistent if it contains no contradictions, that is, if some statement p does not imply both q and not-q.

Platonism in mathematics is the belief that mathematical objects exist as ideals, independent of worldly experience, and can be discovered by thinking. Constructivism opposes Platonism, claiming that mathematical objects exist only if they can be constructed, that is, only if proofs or axioms can be invented for them. For constructivism, a mathematical proof is acceptable only if it arises from the data of experience.

At the Second International Congress of Mathematics in Paris in 1900, Hilbert challenged his colleagues with 23 problems. This "Hilbert program," with modifications through the 1920s, became the agenda of formalism.

Georg Cantor (1845-1918) developed set theory in the 1870s. Hilbert was bothered by the many paradoxes and unanswered questions that attended Cantor's concept of infinite sets. Hilbert's essay, "On the Infinite" (1925), attempted to resolve some of these issues, and the Hilbert program encouraged other mathematicians to think about them, too.

Among Cantor's results was the theorem that the power set of any set S (the set of all subsets of S) has a greater cardinality (more members) than S. This theorem led to difficulties with the notion of infinity. The set of natural numbers is infinite. Call its cardinality ℵ₀. Obviously some sets, such as the set of real numbers, the set of points on a line, the power set of the natural numbers, etc., have greater cardinalities than ℵ₀, that is, greater than infinity. This is the "continuum problem."

Hilbert's version of formalism accepted Platonism, but some formalisms are closer to constructivism, holding that mathematical statements are just sequences of "chicken scratches" and do not represent any actual objects.

Finitism recognizes the existence of only those mathematical objects that can be demonstrated in a finite number of steps or proved in a finite number of wffs. Hilbert and many of his followers were finitists.

Intuitionism claims, against logicism, that logic is part of mathematics; against Platonism, that the only real mathematical objects are those that can be experienced; against formalism, that mathematical proofs are assertions of the reality of mathematical objects, not just series of wffs; and against finitism, that proofs are necessary, not just sufficient, to assert the reality of mathematical objects. Intuitionism frequently makes common cause with constructivism.

Reacting against Platonism and formalism, the intuitionism and constructivism of Brouwer rejected the law of the excluded middle as established by Augustus De Morgan (1806-1871) and questioned Cantor's concept of infinity because of its unintelligibility. As Brouwer devised it in the first two decades of the twentieth century, intuitionism demanded the actual mental conception of mathematical objects, rather than just the possibility that they could be proved.

Hilbert and Brouwer were each influenced by the philosophy of mathematics of Immanuel Kant (1724-1804), who held that there are two, and only two, forms of intuition: space and time. For Brouwer, since the infinite continuum cannot be understood in space and time, it must be just an idea of pure reason, or what Kant would call a "regulative ideal." Brouwer emphasized Kant's intuition of time, while Hilbert used a Kantian epistemology, or theory of knowledge, to support his finitism.

Impact

Many important results in mathematical and symbolic logic stemmed from the formalism vs. intuitionism debate.

Emil Leon Post (1897-1954) proved the consistency of the Russell/Whitehead propositional logic in 1920. Wilhelm Ackermann (1896-1962) and Hilbert did the same for first-order predicate logic in 1928. Consistency proofs for other logics were offered by Jacques Herbrand (1908-1931) in 1930 and Gerhard Gentzen (1909-1945) in 1936. In the 1930s John von Neumann (1903-1957) solved the "compact group problem," the fifth of the 23 challenges that Hilbert had given to the worldwide mathematical community. Jan Lukasiewicz (1878-1956) and Post proved decidability for propositional logic in 1921. A system or theory is decidable if there is a way (algorithm) to determine whether a given sentence is a theorem of that system or theory. In various degrees, these results all tended to favor formalism.

Results favoring Brouwer and intuitionism also appeared. In 1930 Arend Heyting (1898-1980) formulated a propositional logic in accordance with intuitionistic/constructivistic principles. In 1939 John Charles Chenoweth McKinsey (1908-1953) demonstrated that Heyting's axioms for intuitionistic propositional logic are self-sufficient.

The two incompleteness proofs of Kurt Gödel, a Platonist, dealt formalism a telling blow in 1931.

Beyond the negative result of Gödel's incompleteness proofs, Alonzo Church (1903-1995) and Alan Turing (1912-1954) each proved independently in 1936 that first-order logic is undecidable. This result, called Church's theorem, is not to be confused with what is known as Church's thesis or the Church-Turing thesis, propounded the same year, which has to do with possible algorithms for the computability of functions.

Before World War II, most of the investigators of the relation between logic and the foundations of mathematics were mathematicians, and the German-speaking world field dominated the field. After Hilbert's death, and especially since the 1960s, mathematicians generally lost interest in these foundational issues. Mathematical logic and the logic of mathematics became mostly the province of logicians and philosophers, with the English-speaking world dominating.

ERIC V.D. LUFT