Mathematical logic

From Wikipedia, the free encyclopedia

Mathematical logic is a subfield of mathematics exploring the applications of formal logic to mathematics. It bears close connections to metamathematics, the foundations of mathematics, and theoretical computer science. The unifying themes in mathematical logic include the study of the expressive power of formal systems and the deductive power of formal proof systems.

Mathematical logic is often divided into the fields of set theory, model theory, recursion theory, and proof theory. These areas share basic results on logic, particularly first-order logic, and definability. In computer science (particularly in the ACM Classification) mathematical logic encompasses additional topics not detailed in this article; see Logic in computer science for those.

Since its inception, mathematical logic has both contributed to, and has been motivated by, the study of foundations of mathematics. This study began in the late 19th century with the development of axiomatic frameworks for geometry, arithmetic, and analysis. In the early 20th century it was shaped by David Hilbert's program to prove the consistency of foundational theories. Results of Kurt Gödel, Gerhard Gentzen, and others provided partial resolution to the program, and clarified the issues involved in proving consistency. Work in set theory showed that almost all ordinary mathematics can be formalized in terms of sets, although there are some theorems that cannot be proven in common axiom systems for set theory. Contemporary work in the foundations of mathematics often focuses on establishing which parts of mathematics can be formalized in particular formal systems (as in reverse mathematics) rather than trying to find theories in which all of mathematics can be developed.

Subfields and scope

The Handbook of Mathematical Logic (Barwise 1989) makes a rough division of contemporary mathematical logic into four areas:

1. set theory
2. model theory
3. recursion theory, and
4. proof theory and constructive mathematics (considered as parts of a single area).

Each area has a distinct focus, although many techniques and results are shared among multiple areas. The borderlines amongst these fields, and the lines separating mathematical logic and other fields of mathematics, are not always sharp. Gödel's incompleteness theorem marks not only a milestone in recursion theory and proof theory, but has also led to Löb's theorem in modal logic. The method of forcing is employed in set theory, model theory, and recursion theory, as well as in the study of intuitionistic mathematics.

The mathematical field of category theory uses many formal axiomatic methods, and includes the study of categorical logic, but category theory is not ordinarily considered a subfield of mathematical logic. Because of its applicability in diverse fields of mathematics, mathematicians including Saunders Mac Lane have proposed category theory as a foundational system for mathematics, independent of set theory. These foundations use toposes, which resemble generalized models of set theory that may employ classical or nonclassical logic.

History

Mathematical logic emerged in the mid-19th century as a subfield of mathematics, reflecting the confluence of two traditions: formal philosophical logic and mathematics (Ferreirós 2001, p. 443). "Mathematical logic, also called 'logistic', 'symbolic logic', the 'algebra of logic', and, more recently, simply 'formal logic', is the set of logical theories elaborated in the course of the last [nineteenth] century with the aid of an artificial notation and a rigorously deductive method."^[2] Before this emergence, logic was studied with rhetoric, with calculationes,^[3] through the syllogism, and with philosophy. The first half of the 20th century saw an explosion of fundamental results, accompanied by vigorous debate over the foundations of mathematics.

Early history

Theories of logic were developed in many cultures in history, including China, India, Greece and the Islamic world. In 18th-century Europe, attempts to treat the operations of formal logic in a symbolic or algebraic way had been made by philosophical mathematicians including Leibniz and Lambert, but their labors remained isolated and little known.

19th century

In the middle of the nineteenth century, George Boole and then Augustus De Morgan presented systematic mathematical treatments of logic. Their work, building on work by algebraists such as George Peacock, extended the traditional Aristotelian doctrine of logic into a sufficient framework for the study of foundations of mathematics (Katz 1998, p. 686).

Charles Sanders Peirce built upon the work of Boole to develop a logical system for relations and quantifiers, which he published in several papers from 1870 to 1885. Gottlob Frege presented an independent development of logic with quantifiers in his Begriffsschrift, published in 1879, a work generally considered as marking a turning point in the history of logic. Frege's work remained obscure, however, until Bertrand Russell began to promote it near the turn of the century. The two-dimensional notation Frege developed was never widely adopted and is unused in contemporary texts.

From 1890 to 1905, Ernst Schröder published Vorlesungen über die Algebra der Logik in three volumes. This work summarized and extended the work of Boole, De Morgan, and Peirce, and was a comprehensive reference to symbolic logic as it was understood at the end of the 19th century.

Foundational theories

Concerns that mathematics had not been built on a proper foundation led to the development of axiomatic systems for fundamental areas of mathematics such as arithmetic, analysis, and geometry.

In logic, the term arithmetic refers to the theory of the natural numbers. Giuseppe Peano (1889) published a set of axioms for arithmetic that came to bear his name (Peano axioms), using a variation of the logical system of Boole and Schröder but adding quantifiers. Peano was unaware of Frege's work at the time. Around the same time Richard Dedekind showed that the natural numbers are uniquely characterized by their induction properties. Dedekind (1888) proposed a different characterization, which lacked the formal logical character of Peano's axioms. Dedekind's work, however, proved theorems inaccessible in Peano's system, including the uniqueness of the set of natural numbers (up to isomorphism) and the recursive definitions of addition and multiplication from the successor function and mathematical induction.

In the mid-19th century, flaws in Euclid's axioms for geometry became known (Katz 1998, p. 774). In addition to the independence of the parallel postulate, established by Nikolai Lobachevsky in 1826 (Lobachevsky 1840), mathematicians discovered that certain theorems taken for granted by Euclid were not in fact provable from his axioms. Among these is the theorem that a line contains at least two points, or that circles of the same radius whose centers are separated by that radius must intersect. Hilbert (1899) developed a complete set of axioms for geometry, building on previous work by Pasch (1882). The success in axiomatizing geometry motivated Hilbert to seek complete axiomatizations of other areas of mathematics, such as the natural numbers and the real line. This would prove to be a major area of research in the first half of the 20th century.

The 19th century saw great advances in the theory of real analysis, including theories of convergence of functions and Fourier series. Mathematicians such as Karl Weierstrass began to construct functions that stretched intuition, such as nowhere-differentiable continuous functions. Previous conceptions of a function as a rule for computation, or a smooth graph, were no longer adequate. Weierstrass began to advocate the arithmetization of analysis, which sought to axiomatize analysis using properties of the natural numbers. The modern (ε, δ)-definition of limit and continuous functions was already developed by Bolzano in 1817 (Felscher 2000), but remained relatively unknown. Cauchy in 1821 defined continuity in terms of infinitesimals (see Cours d'Analyse, page 34). In 1858, Dedekind proposed a definition of the real numbers in terms of Dedekind cuts of rational numbers (Dedekind 1872), a definition still employed in contemporary texts.

Georg Cantor developed the fundamental concepts of infinite set theory. His early results developed the theory of cardinality and proved that the reals and the natural numbers have different cardinalities (Cantor 1874). Over the next twenty years, Cantor developed a theory of transfinite numbers in a series of publications. In 1891, he published a new proof of the uncountability of the real numbers that introduced the diagonal argument, and used this method to prove Cantor's theorem that no set can have the same cardinality as its powerset. Cantor believed that every set could be well-ordered, but was unable to produce a proof for this result, leaving it as an open problem in 1895 (Katz 1998, p. 807).

20th century

In the early decades of the 20th century, the main areas of study were set theory and formal logic. The discovery of paradoxes in informal set theory caused some to wonder whether mathematics itself is inconsistent, and to look for proofs of consistency.

In 1900, Hilbert posed a famous list of 23 problems for the next century. The first two of these were to resolve the continuum hypothesis and prove the consistency of elementary arithmetic, respectively; the tenth was to produce a method that could decide whether a multivariate polynomial equation over the integers has a solution. Subsequent work to resolve these problems shaped the direction of mathematical logic, as did the effort to resolve Hilbert's Entscheidungsproblem, posed in 1928. This problem asked for a procedure that would decide, given a formalized mathematical statement, whether the statement is true or false.

Set theory and paradoxes

Ernst Zermelo (1904) gave a proof that every set could be well-ordered, a result Georg Cantor had been unable to obtain. To achieve the proof, Zermelo introduced the axiom of choice, which drew heated debate and research among mathematicians and the pioneers of set theory. The immediate criticism of the method led Zermelo to publish a second exposition of his result, directly addressing criticisms of his proof (Zermelo 1908a). This paper led to the general acceptance of the axiom of choice in the mathematics community.

Skepticism about the axiom of choice was reinforced by recently discovered paradoxes in naive set theory. Cesare Burali-Forti (1897) was the first to state a paradox: the Burali-Forti paradox shows that the collection of all ordinal numbers cannot form a set. Very soon thereafter, Bertrand Russell discovered Russell's paradox in 1901, and Jules Richard (1905) discovered Richard's paradox.

Zermelo (1908b) provided the first set of axioms for set theory. These axioms, together with the additional axiom of replacement proposed by Abraham Fraenkel, are now called Zermelo–Fraenkel set theory (ZF). Zermelo's axioms incorporated the principle of limitation of size to avoid Russell's paradox.

In 1910, the first volume of Principia Mathematica by Russell and Alfred North Whitehead was published. This seminal work developed the theory of functions and cardinality in a completely formal framework of type theory, which Russell and Whitehead developed in an effort to avoid the paradoxes. Principia Mathematica is considered one of the most influential works of the 20th century, although the framework of type theory did not prove popular as a foundational theory for mathematics (Ferreirós 2001, p. 445).

Fraenkel (1922) proved that the axiom of choice cannot be proved from the axioms of Zermelo's set theory with urelements. Later work by Paul Cohen (1966) showed that the addition of urelements is not needed, and the axiom of choice is unprovable in ZF. Cohen's proof developed the method of forcing, which is now an important tool for establishing independence results in set theory.^[4]

Symbolic logic

Leopold Löwenheim (1915) and Thoralf Skolem (1920) obtained the Löwenheim–Skolem theorem, which says that first-order logic cannot control the cardinalities of infinite structures. Skolem realized that this theorem would apply to first-order formalizations of set theory, and that it implies any such formalization has a countable model. This counterintuitive fact became known as Skolem's paradox.

In his doctoral thesis, Kurt Gödel (1929) proved the completeness theorem, which establishes a correspondence between syntax and semantics in first-order logic. Gödel used the completeness theorem to prove the compactness theorem, demonstrating the finitary nature of first-order logical consequence. These results helped establish first-order logic as the dominant logic used by mathematicians.

In 1931, Gödel published On Formally Undecidable Propositions of Principia Mathematica and Related Systems, which proved the incompleteness (in a different meaning of the word) of all sufficiently strong, effective first-order theories. This result, known as Gödel's incompleteness theorem, establishes severe limitations on axiomatic foundations for mathematics, striking a strong blow to Hilbert's program. It showed the impossibility of providing a consistency proof of arithmetic within any formal theory of arithmetic. Hilbert, however, did not acknowledge the importance of the incompleteness theorem for some time.^[5]

Gödel's theorem shows that a consistency proof of any sufficiently strong, effective axiom system cannot be obtained in the system itself, if the system is consistent, nor in any weaker system. This leaves open the possibility of consistency proofs that cannot be formalized within the system they consider. Gentzen (1936) proved the consistency of arithmetic using a finitistic system together with a principle of transfinite induction. Gentzen's result introduced the ideas of cut elimination and proof-theoretic ordinals, which became key tools in proof theory. Gödel (1958) gave a different consistency proof, which reduces the consistency of classical arithmetic to that of intuitionistic arithmetic in higher types.

Beginnings of the other branches

Alfred Tarski developed the basics of model theory.

Beginning in 1935, a group of prominent mathematicians collaborated under the pseudonym Nicolas Bourbaki to publish a series of encyclopedic mathematics texts. These texts, written in an austere and axiomatic style, emphasized rigorous presentation and set-theoretic foundations. Terminology coined by these texts, such as the words bijection, injection, and surjection, and the set-theoretic foundations the texts employed, were widely adopted throughout mathematics.

The study of computability came to be known as recursion theory, because early formalizations by Gödel and Kleene relied on recursive definitions of functions.^[6] When these definitions were shown equivalent to Turing's formalization involving Turing machines, it became clear that a new concept – the computable function – had been discovered, and that this definition was robust enough to admit numerous independent characterizations. In his work on the incompleteness theorems in 1931, Gödel lacked a rigorous concept of an effective formal system; he immediately realized that the new definitions of computability could be used for this purpose, allowing him to state the incompleteness theorems in generality that could only be implied in the original paper.

Numerous results in recursion theory were obtained in the 1940s by Stephen Cole Kleene and Emil Leon Post. Kleene (1943) introduced the concepts of relative computability, foreshadowed by Turing (1939), and the arithmetical hierarchy. Kleene later generalized recursion theory to higher-order functionals. Kleene and Kreisel studied formal versions of intuitionistic mathematics, particularly in the context of proof theory.

Formal logical systems

At its core, mathematical logic deals with mathematical concepts expressed using formal logical systems. These systems, though they differ in many details, share the common property of considering only expressions in a fixed formal language. The systems of propositional logic and first-order logic are the most widely studied today, because of their applicability to foundations of mathematics and because of their desirable proof-theoretic properties.^[7] Stronger classical logics such as second-order logic or infinitary logic are also studied, along with nonclassical logics such as intuitionistic logic.

First-order logic

First-order logic is a particular formal system of logic. Its syntax involves only finite expressions as well-formed formulas, while its semantics are characterized by the limitation of all quantifiers to a fixed domain of discourse.

Early results from formal logic established limitations of first-order logic. The Löwenheim–Skolem theorem (1919) showed that if a set of sentences in a countable first-order language has an infinite model then it has at least one model of each infinite cardinality. This shows that it is impossible for a set of first-order axioms to characterize the natural numbers, the real numbers, or any other infinite structure up to isomorphism. As the goal of early foundational studies was to produce axiomatic theories for all parts of mathematics, this limitation was particularly stark.

Gödel's completeness theorem (Gödel 1929) established the equivalence between semantic and syntactic definitions of logical consequence in first-order logic. It shows that if a particular sentence is true in every model that satisfies a particular set of axioms, then there must be a finite deduction of the sentence from the axioms. The compactness theorem first appeared as a lemma in Gödel's proof of the completeness theorem, and it took many years before logicians grasped its significance and began to apply it routinely. It says that a set of sentences has a model if and only if every finite subset has a model, or in other words that an inconsistent set of formulas must have a finite inconsistent subset. The completeness and compactness theorems allow for sophisticated analysis of logical consequence in first-order logic and the development of model theory, and they are a key reason for the prominence of first-order logic in mathematics.

Gödel's incompleteness theorems (Gödel 1931) establish additional limits on first-order axiomatizations. The first incompleteness theorem states that for any consistent, effectively given (defined below) logical system that is capable of interpreting arithmetic, there exists a statement that is true (in the sense that it holds for the natural numbers) but not provable within that logical system (and which indeed may fail in some non-standard models of arithmetic which may be consistent with the logical system). For example, in every logical system capable of expressing the Peano axioms, the Gödel sentence holds for the natural numbers but cannot be proved.

Here a logical system is said to be effectively given if it is possible to decide, given any formula in the language of the system, whether the formula is an axiom, and one which can express the Peano axioms is called "sufficiently strong." When applied to first-order logic, the first incompleteness theorem implies that any sufficiently strong, consistent, effective first-order theory has models that are not elementarily equivalent, a stronger limitation than the one established by the Löwenheim–Skolem theorem. The second incompleteness theorem states that no sufficiently strong, consistent, effective axiom system for arithmetic can prove its own consistency, which has been interpreted to show that Hilbert's program cannot be completed.

Other classical logics

Many logics besides first-order logic are studied. These include infinitary logics, which allow for formulas to provide an infinite amount of information, and higher-order logics, which include a portion of set theory directly in their semantics.

The most well studied infinitary logic is ${\displaystyle L_{\omega _{1},\omega }}$. In this logic, quantifiers may only be nested to finite depths, as in first-order logic, but formulas may have finite or countably infinite conjunctions and disjunctions within them. Thus, for example, it is possible to say that an object is a whole number using a formula of ${\displaystyle L_{\omega _{1},\omega }}$ such as

${\displaystyle (x=0)\lor (x=1)\lor (x=2)\lor \cdots .}$

Higher-order logics allow for quantification not only of elements of the domain of discourse, but subsets of the domain of discourse, sets of such subsets, and other objects of higher type. The semantics are defined so that, rather than having a separate domain for each higher-type quantifier to range over, the quantifiers instead range over all objects of the appropriate type. The logics studied before the development of first-order logic, for example Frege's logic, had similar set-theoretic aspects. Although higher-order logics are more expressive, allowing complete axiomatizations of structures such as the natural numbers, they do not satisfy analogues of the completeness and compactness theorems from first-order logic, and are thus less amenable to proof-theoretic analysis.

Another type of logics are fixed-point logics that allow inductive definitions, like one writes for primitive recursive functions.

One can formally define an extension of first-order logic — a notion which encompasses all logics in this section because they behave like first-order logic in certain fundamental ways, but does not encompass all logics in general, e.g. it does not encompass intuitionistic, modal or fuzzy logic. Lindström's theorem implies that the only extension of first-order logic satisfying both the compactness theorem and the Downward Löwenheim–Skolem theorem is first-order logic.

Nonclassical and modal logic

Modal logics include additional modal operators, such as an operator which states that a particular formula is not only true, but necessarily true. Although modal logic is not often used to axiomatize mathematics, it has been used to study the properties of first-order provability (Solovay 1976) and set-theoretic forcing (Hamkins and Löwe 2007).

Intuitionistic logic was developed by Heyting to study Brouwer's program of intuitionism, in which Brouwer himself avoided formalization. Intuitionistic logic specifically does not include the law of the excluded middle, which states that each sentence is either true or its negation is true. Kleene's work with the proof theory of intuitionistic logic showed that constructive information can be recovered from intuitionistic proofs. For example, any provably total function in intuitionistic arithmetic is computable; this is not true in classical theories of arithmetic such as Peano arithmetic.

Algebraic logic

Algebraic logic uses the methods of abstract algebra to study the semantics of formal logics. A fundamental example is the use of Boolean algebras to represent truth values in classical propositional logic, and the use of Heyting algebras to represent truth values in intuitionistic propositional logic. Stronger logics, such as first-order logic and higher-order logic, are studied using more complicated algebraic structures such as cylindric algebras.

Set theory

Set theory is the study of sets, which are abstract collections of objects. Many of the basic notions, such as ordinal and cardinal numbers, were developed informally by Cantor before formal axiomatizations of set theory were developed. The first such axiomatization, due to Zermelo (1908b), was extended slightly to become Zermelo–Fraenkel set theory (ZF), which is now the most widely used foundational theory for mathematics.

Other formalizations of set theory have been proposed, including von Neumann–Bernays–Gödel set theory (NBG), Morse–Kelley set theory (MK), and New Foundations (NF). Of these, ZF, NBG, and MK are similar in describing a cumulative hierarchy of sets. New Foundations takes a different approach; it allows objects such as the set of all sets at the cost of restrictions on its set-existence axioms. The system of Kripke–Platek set theory is closely related to generalized recursion theory.

Two famous statements in set theory are the axiom of choice and the continuum hypothesis. The axiom of choice, first stated by Zermelo (1904), was proved independent of ZF by Fraenkel (1922), but has come to be widely accepted by mathematicians. It states that given a collection of nonempty sets there is a single set C that contains exactly one element from each set in the collection. The set C is said to "choose" one element from each set in the collection. While the ability to make such a choice is considered obvious by some, since each set in the collection is nonempty, the lack of a general, concrete rule by which the choice can be made renders the axiom nonconstructive. Stefan Banach and Alfred Tarski (1924) showed that the axiom of choice can be used to decompose a solid ball into a finite number of pieces which can then be rearranged, with no scaling, to make two solid balls of the original size. This theorem, known as the Banach–Tarski paradox, is one of many counterintuitive results of the axiom of choice.

The continuum hypothesis, first proposed as a conjecture by Cantor, was listed by David Hilbert as one of his 23 problems in 1900. Gödel showed that the continuum hypothesis cannot be disproven from the axioms of Zermelo–Fraenkel set theory (with or without the axiom of choice), by developing the constructible universe of set theory in which the continuum hypothesis must hold. In 1963, Paul Cohen showed that the continuum hypothesis cannot be proven from the axioms of Zermelo–Fraenkel set theory (Cohen 1966). This independence result did not completely settle Hilbert's question, however, as it is possible that new axioms for set theory could resolve the hypothesis. Recent work along these lines has been conducted by W. Hugh Woodin, although its importance is not yet clear (Woodin 2001).

Contemporary research in set theory includes the study of large cardinals and determinacy. Large cardinals are cardinal numbers with particular properties so strong that the existence of such cardinals cannot be proved in ZFC. The existence of the smallest large cardinal typically studied, an inaccessible cardinal, already implies the consistency of ZFC. Despite the fact that large cardinals have extremely high cardinality, their existence has many ramifications for the structure of the real line. Determinacy refers to the possible existence of winning strategies for certain two-player games (the games are said to be determined). The existence of these strategies implies structural properties of the real line and other Polish spaces.

Model theory

Model theory studies the models of various formal theories. Here a theory is a set of formulas in a particular formal logic and signature, while a model is a structure that gives a concrete interpretation of the theory. Model theory is closely related to universal algebra and algebraic geometry, although the methods of model theory focus more on logical considerations than those fields.

The set of all models of a particular theory is called an elementary class; classical model theory seeks to determine the properties of models in a particular elementary class, or determine whether certain classes of structures form elementary classes.

The method of quantifier elimination can be used to show that definable sets in particular theories cannot be too complicated. Tarski (1948) established quantifier elimination for real-closed fields, a result which also shows the theory of the field of real numbers is decidable. (He also noted that his methods were equally applicable to algebraically closed fields of arbitrary characteristic.) A modern subfield developing from this is concerned with o-minimal structures.

Morley's categoricity theorem, proved by Michael D. Morley (1965), states that if a first-order theory in a countable language is categorical in some uncountable cardinality, i.e. all models of this cardinality are isomorphic, then it is categorical in all uncountable cardinalities.

A trivial consequence of the continuum hypothesis is that a complete theory with less than continuum many nonisomorphic countable models can have only countably many. Vaught's conjecture, named after Robert Lawson Vaught, says that this is true even independently of the continuum hypothesis. Many special cases of this conjecture have been established.

Recursion theory

Recursion theory, also called computability theory, studies the properties of computable functions and the Turing degrees, which divide the uncomputable functions into sets that have the same level of uncomputability. Recursion theory also includes the study of generalized computability and definability. Recursion theory grew from the work of Rózsa Péter, Alonzo Church and Alan Turing in the 1930s, which was greatly extended by Kleene and Post in the 1940s.^[8]

Classical recursion theory focuses on the computability of functions from the natural numbers to the natural numbers. The fundamental results establish a robust, canonical class of computable functions with numerous independent, equivalent characterizations using Turing machines, λ calculus, and other systems. More advanced results concern the structure of the Turing degrees and the lattice of recursively enumerable sets.

Generalized recursion theory extends the ideas of recursion theory to computations that are no longer necessarily finite. It includes the study of computability in higher types as well as areas such as hyperarithmetical theory and α-recursion theory.

Contemporary research in recursion theory includes the study of applications such as algorithmic randomness, computable model theory, and reverse mathematics, as well as new results in pure recursion theory.

Algorithmically unsolvable problems

An important subfield of recursion theory studies algorithmic unsolvability; a decision problem or function problem is algorithmically unsolvable if there is no possible computable algorithm that returns the correct answer for all legal inputs to the problem. The first results about unsolvability, obtained independently by Church and Turing in 1936, showed that the Entscheidungsproblem is algorithmically unsolvable. Turing proved this by establishing the unsolvability of the halting problem, a result with far-ranging implications in both recursion theory and computer science.

There are many known examples of undecidable problems from ordinary mathematics. The word problem for groups was proved algorithmically unsolvable by Pyotr Novikov in 1955 and independently by W. Boone in 1959. The busy beaver problem, developed by Tibor Radó in 1962, is another well-known example.

Hilbert's tenth problem asked for an algorithm to determine whether a multivariate polynomial equation with integer coefficients has a solution in the integers. Partial progress was made by Julia Robinson, Martin Davis and Hilary Putnam. The algorithmic unsolvability of the problem was proved by Yuri Matiyasevich in 1970 (Davis 1973).

Proof theory and constructive mathematics

Proof theory is the study of formal proofs in various logical deduction systems. These proofs are represented as formal mathematical objects, facilitating their analysis by mathematical techniques. Several deduction systems are commonly considered, including Hilbert-style deduction systems, systems of natural deduction, and the sequent calculus developed by Gentzen.

The study of constructive mathematics, in the context of mathematical logic, includes the study of systems in non-classical logic such as intuitionistic logic, as well as the study of predicative systems. An early proponent of predicativism was Hermann Weyl, who showed it is possible to develop a large part of real analysis using only predicative methods (Weyl 1918).

Because proofs are entirely finitary, whereas truth in a structure is not, it is common for work in constructive mathematics to emphasize provability. The relationship between provability in classical (or nonconstructive) systems and provability in intuitionistic (or constructive, respectively) systems is of particular interest. Results such as the Gödel–Gentzen negative translation show that it is possible to embed (or translate) classical logic into intuitionistic logic, allowing some properties about intuitionistic proofs to be transferred back to classical proofs.

Recent developments in proof theory include the study of proof mining by Ulrich Kohlenbach and the study of proof-theoretic ordinals by Michael Rathjen.

Applications

"Mathematical logic has been successfully applied not only to mathematics and its foundations (G. Frege, B. Russell, D. Hilbert, P. Bernays, H. Scholz, R. Carnap, S. Lesniewski, T. Skolem), but also to physics (R. Carnap, A. Dittrich, B. Russell, C. E. Shannon, A. N. Whitehead, H. Reichenbach, P. Fevrier), to biology (J. H. Woodger, A. Tarski), to psychology (F. B. Fitch, C. G. Hempel), to law and morals (K. Menger, U. Klug, P. Oppenheim), to economics (J. Neumann, O. Morgenstern), to practical questions (E. C. Berkeley, E. Stamm), and even to metaphysics (J. [Jan] Salamucha,^[9] H. Scholz, J. M. Bochenski). Its applications to the history of logic have proven extremely fruitful (J. Lukasiewicz, H. Scholz, B. Mates, A. Becker, E. Moody, J. Salamucha, K. Duerr, Z. Jordan, P. Boehner, J. M. Bochenski, S. [Stanislaw] T. Schayer,^[10] D. Ingalls)."^[11] "Applications have also been made to theology (F. Drewnowski, J. Salamucha, I. Thomas)."^[12]

Connections with computer science

The study of computability theory in computer science is closely related to the study of computability in mathematical logic. There is a difference of emphasis, however. Computer scientists often focus on concrete programming languages and feasible computability, while researchers in mathematical logic often focus on computability as a theoretical concept and on noncomputability.

The theory of semantics of programming languages is related to model theory, as is program verification (in particular, model checking). The Curry–Howard isomorphism between proofs and programs relates to proof theory, especially intuitionistic logic. Formal calculi such as the lambda calculus and combinatory logic are now studied as idealized programming languages.

Computer science also contributes to mathematics by developing techniques for the automatic checking or even finding of proofs, such as automated theorem proving and logic programming.

Descriptive complexity theory relates logics to computational complexity. The first significant result in this area, Fagin's theorem (1974) established that NP is precisely the set of languages expressible by sentences of existential second-order logic.

Foundations of mathematics

In the 19th century, mathematicians became aware of logical gaps and inconsistencies in their field. It was shown that Euclid's axioms for geometry, which had been taught for centuries as an example of the axiomatic method, were incomplete. The use of infinitesimals, and the very definition of function, came into question in analysis, as pathological examples such as Weierstrass' nowhere-differentiable continuous function were discovered.

Cantor's study of arbitrary infinite sets also drew criticism. Leopold Kronecker famously stated "God made the integers; all else is the work of man," endorsing a return to the study of finite, concrete objects in mathematics. Although Kronecker's argument was carried forward by constructivists in the 20th century, the mathematical community as a whole rejected them. David Hilbert argued in favor of the study of the infinite, saying "No one shall expel us from the Paradise that Cantor has created."

Mathematicians began to search for axiom systems that could be used to formalize large parts of mathematics. In addition to removing ambiguity from previously naive terms such as function, it was hoped that this axiomatization would allow for consistency proofs. In the 19th century, the main method of proving the consistency of a set of axioms was to provide a model for it. Thus, for example, non-Euclidean geometry can be proved consistent by defining point to mean a point on a fixed sphere and line to mean a great circle on the sphere. The resulting structure, a model of elliptic geometry, satisfies the axioms of plane geometry except the parallel postulate.

With the development of formal logic, Hilbert asked whether it would be possible to prove that an axiom system is consistent by analyzing the structure of possible proofs in the system, and showing through this analysis that it is impossible to prove a contradiction. This idea led to the study of proof theory. Moreover, Hilbert proposed that the analysis should be entirely concrete, using the term finitary to refer to the methods he would allow but not precisely defining them. This project, known as Hilbert's program, was seriously affected by Gödel's incompleteness theorems, which show that the consistency of formal theories of arithmetic cannot be established using methods formalizable in those theories. Gentzen showed that it is possible to produce a proof of the consistency of arithmetic in a finitary system augmented with axioms of transfinite induction, and the techniques he developed to do so were seminal in proof theory.

A second thread in the history of foundations of mathematics involves nonclassical logics and constructive mathematics. The study of constructive mathematics includes many different programs with various definitions of constructive. At the most accommodating end, proofs in ZF set theory that do not use the axiom of choice are called constructive by many mathematicians. More limited versions of constructivism limit themselves to natural numbers, number-theoretic functions, and sets of natural numbers (which can be used to represent real numbers, facilitating the study of mathematical analysis). A common idea is that a concrete means of computing the values of the function must be known before the function itself can be said to exist.

In the early 20th century, Luitzen Egbertus Jan Brouwer founded intuitionism as a philosophy of mathematics. This philosophy, poorly understood at first, stated that in order for a mathematical statement to be true to a mathematician, that person must be able to intuit the statement, to not only believe its truth but understand the reason for its truth. A consequence of this definition of truth was the rejection of the law of the excluded middle, for there are statements that, according to Brouwer, could not be claimed to be true while their negations also could not be claimed true. Brouwer's philosophy was influential, and the cause of bitter disputes among prominent mathematicians. Later, Kleene and Kreisel would study formalized versions of intuitionistic logic (Brouwer rejected formalization, and presented his work in unformalized natural language). With the advent of the BHK interpretation and Kripke models, intuitionism became easier to reconcile with classical mathematics.

Foundations of mathematics

From Wikipedia, the free encyclopedia

Foundations of mathematics is the study of the philosophical and logical and/or algorithmic basis of mathematics, or, in a broader sense, the mathematical investigation of what underlies the philosophical theories concerning the nature of mathematics. In this latter sense, the distinction between foundations of mathematics and philosophy of mathematics turns out to be quite vague. Foundations of mathematics can be conceived as the study of the basic mathematical concepts (number, geometrical figure, set, function, etc.) and how they form hierarchies of more complex structures and concepts, especially the fundamentally important structures that form the language of mathematics (formulas, theories and their models giving a meaning to formulas, definitions, proofs, algorithms, etc.) also called metamathematical concepts, with an eye to the philosophical aspects and the unity of mathematics. The search for foundations of mathematics is a central question of the philosophy of mathematics; the abstract nature of mathematical objects presents special philosophical challenges.

The foundations of mathematics as a whole does not aim to contain the foundations of every mathematical topic. Generally, the foundations of a field of study refers to a more-or-less systematic analysis of its most basic or fundamental concepts, its conceptual unity and its natural ordering or hierarchy of concepts, which may help to connect it with the rest of human knowledge. The development, emergence and clarification of the foundations can come late in the history of a field, and may not be viewed by everyone as its most interesting part.

Mathematics always played a special role in scientific thought, serving since ancient times as a model of truth and rigor for rational inquiry, and giving tools or even a foundation for other sciences (especially physics). Mathematics' many developments towards higher abstractions in the 19th century brought new challenges and paradoxes, urging for a deeper and more systematic examination of the nature and criteria of mathematical truth, as well as a unification of the diverse branches of mathematics into a coherent whole.

The systematic search for the foundations of mathematics started at the end of the 19th century and formed a new mathematical discipline called mathematical logic, with strong links to theoretical computer science. It went through a series of crises with paradoxical results, until the discoveries stabilized during the 20th century as a large and coherent body of mathematical knowledge with several aspects or components (set theory, model theory, proof theory, etc.), whose detailed properties and possible variants are still an active research field. Its high level of technical sophistication inspired many philosophers to conjecture that it can serve as a model or pattern for the foundations of other sciences.

Historical context

Ancient Greek mathematics

While the practice of mathematics had previously developed in other civilizations, special interest in its theoretical and foundational aspects was clearly evident in the work of the Ancient Greeks.

Early Greek philosophers disputed as to which is more basic, arithmetic or geometry. Zeno of Elea (490 – c. 430 BC) produced four paradoxes that seem to show the impossibility of change. The Pythagorean school of mathematics originally insisted that only natural and rational numbers exist. The discovery of the irrationality of √2, the ratio of the diagonal of a square to its side (around 5th century BC), was a shock to them which they only reluctantly accepted. The discrepancy between rationals and reals was finally resolved by Eudoxus of Cnidus (408–355 BC), a student of Plato, who reduced the comparison of irrational ratios to comparisons of multiples (rational ratios), thus anticipating the definition of real numbers by Richard Dedekind (1831–1916).

In the Posterior Analytics, Aristotle (384–322 BC) laid down the axiomatic method for organizing a field of knowledge logically by means of primitive concepts, axioms, postulates, definitions, and theorems. Aristotle took a majority of his examples for this from arithmetic and from geometry. This method reached its high point with Euclid's Elements (300 BC), a treatise on mathematics structured with very high standards of rigor: Euclid justifies each proposition by a demonstration in the form of chains of syllogisms (though they do not always conform strictly to Aristotelian templates). Aristotle's syllogistic logic, together with the axiomatic method exemplified by Euclid's Elements, are recognized as scientific achievements of ancient Greece.

Platonism as a traditional philosophy of mathematics

Starting from the end of the 19th century, a Platonist view of mathematics became common among practicing mathematicians.

The concepts or, as Platonists would have it, the objects of mathematics are abstract and remote from everyday perceptual experience: geometrical figures are conceived as idealities to be distinguished from effective drawings and shapes of objects, and numbers are not confused with the counting of concrete objects. Their existence and nature present special philosophical challenges: How do mathematical objects differ from their concrete representation? Are they located in their representation, or in our minds, or somewhere else? How can we know them?

The ancient Greek philosophers took such questions very seriously. Indeed, many of their general philosophical discussions were carried on with extensive reference to geometry and arithmetic. Plato (424/423 BC – 348/347 BC) insisted that mathematical objects, like other platonic Ideas (forms or essences), must be perfectly abstract and have a separate, non-material kind of existence, in a world of mathematical objects independent of humans. He believed that the truths about these objects also exist independently of the human mind, but is discovered by humans. In the Meno Plato's teacher Socrates asserts that it is possible to come to know this truth by a process akin to memory retrieval.

Above the gateway to Plato's academy appeared a famous inscription: "Let no one who is ignorant of geometry enter here". In this way Plato indicated his high opinion of geometry. He regarded geometry as "the first essential in the training of philosophers", because of its abstract character.

This philosophy of Platonist mathematical realism is shared by many mathematicians. It can be argued that Platonism somehow comes as a necessary assumption underlying any mathematical work.^[3]

In this view, the laws of nature and the laws of mathematics have a similar status, and the effectiveness ceases to be unreasonable. Not our axioms, but the very real world of mathematical objects forms the foundation.

Aristotle dissected and rejected this view in his Metaphysics. These questions provide much fuel for philosophical analysis and debate.

Middle Ages and Renaissance

For over 2,000 years, Euclid's Elements stood as a perfectly solid foundation for mathematics, as its methodology of rational exploration guided mathematicians, philosophers, and scientists well into the 19th century.

The Middle Ages saw a dispute over the ontological status of the universals (platonic Ideas): Realism asserted their existence independently of perception; conceptualism asserted their existence within the mind only; nominalism denied either, only seeing universals as names of collections of individual objects (following older speculations that they are words, "logoi").

René Descartes published La Géométrie (1637), aimed at reducing geometry to algebra by means of coordinate systems, giving algebra a more foundational role (while the Greeks embedded arithmetic into geometry by identifying whole numbers with evenly spaced points on a line). Descartes' book became famous after 1649 and paved the way to infinitesimal calculus.

Isaac Newton (1642–1727) in England and Leibniz (1646–1716) in Germany independently developed the infinitesimal calculus based on heuristic methods greatly efficient, but direly lacking rigorous justifications. Leibniz even went on to explicitly describe infinitesimals as actual infinitely small numbers (close to zero). Leibniz also worked on formal logic but most of his writings on it remained unpublished until 1903.

The Protestant philosopher George Berkeley (1685–1753), in his campaign against the religious implications of Newtonian mechanics, wrote a pamphlet on the lack of rational justifications of infinitesimal calculus:^[4] "They are neither finite quantities, nor quantities infinitely small, nor yet nothing. May we not call them the ghosts of departed quantities?"

Then mathematics developed very rapidly and successfully in physical applications, but with little attention to logical foundations.

19th century

In the 19th century, mathematics became increasingly abstract. Concerns about logical gaps and inconsistencies in different fields led to the development of axiomatic systems.

Real analysis

Cauchy (1789–1857) started the project of formulating and proving the theorems of infinitesimal calculus in a rigorous manner, rejecting the heuristic principle of the generality of algebra exploited by earlier authors. In his 1821 work Cours d'Analyse he defines infinitely small quantities in terms of decreasing sequences that converge to 0, which he then used to define continuity. But he did not formalize his notion of convergence.

The modern (ε, δ)-definition of limit and continuous functions was first developed by Bolzano in 1817, but remained relatively unknown. It gives a rigorous foundation of infinitesimal calculus based on the set of real numbers, arguably resolving the Zeno paradoxes and Berkeley's arguments.

Mathematicians such as Karl Weierstrass (1815–1897) discovered pathological functions such as continuous, nowhere-differentiable functions. Previous conceptions of a function as a rule for computation, or a smooth graph, were no longer adequate. Weierstrass began to advocate the arithmetization of analysis, to axiomatize analysis using properties of the natural numbers.

In 1858, Dedekind proposed a definition of the real numbers as cuts of rational numbers. This reduction of real numbers and continuous functions in terms of rational numbers, and thus of natural numbers, was later integrated by Cantor in his set theory, and axiomatized in terms of second order arithmetic by Hilbert and Bernays.

Group theory

For the first time, the limits of mathematics were explored. Niels Henrik Abel (1802–1829), a Norwegian, and Évariste Galois, (1811–1832) a Frenchman, investigated the solutions of various polynomial equations, and proved that there is no general algebraic solution to equations of degree greater than four (Abel–Ruffini theorem). With these concepts, Pierre Wantzel (1837) proved that straightedge and compass alone cannot trisect an arbitrary angle nor double a cube. In 1882, Lindemann building on the work of Hermite showed that a straightedge and compass quadrature of the circle (construction of a square equal in area to a given circle) was also impossible by proving that π is a transcendental number. Mathematicians had vainly attempted to solve all of these problems since the time of the ancient Greeks.

Abel and Galois's works opened the way for the developments of group theory (which would later be used to study symmetry in physics and other fields), and abstract algebra. Concepts of vector spaces emerged from the conception of barycentric coordinates by Möbius in 1827, to the modern definition of vector spaces and linear maps by Peano in 1888. Geometry was no more limited to three dimensions. These concepts did not generalize numbers but combined notions of functions and sets which were not yet formalized, breaking away from familiar mathematical objects.

Non-Euclidean geometries

After many failed attempts to derive the parallel postulate from other axioms, the study of the still hypothetical hyperbolic geometry by Johann Heinrich Lambert (1728–1777) led him to introduce the hyperbolic functions and compute the area of a hyperbolic triangle (where the sum of angles is less than 180°). Then the Russian mathematician Nikolai Lobachevsky (1792–1856) established in 1826 (and published in 1829) the coherence of this geometry (thus the independence of the parallel postulate), in parallel with the Hungarian mathematician János Bolyai (1802–1860) in 1832, and with Gauss. Later in the 19th century, the German mathematician Bernhard Riemann developed Elliptic geometry, another non-Euclidean geometry where no parallel can be found and the sum of angles in a triangle is more than 180°. It was proved consistent by defining point to mean a pair of antipodal points on a fixed sphere and line to mean a great circle on the sphere. At that time, the main method for proving the consistency of a set of axioms was to provide a model for it.

Projective geometry

One of the traps in a deductive system is circular reasoning, a problem that seemed to befall projective geometry until it was resolved by Karl von Staudt. As explained by Russian historians:^[5]

In the mid-nineteenth century there was an acrimonious controversy between the proponents of synthetic and analytic methods in projective geometry, the two sides accusing each other of mixing projective and metric concepts. Indeed the basic concept that is applied in the synthetic presentation of projective geometry, the cross-ratio of four points of a line, was introduced through consideration of the lengths of intervals.

The purely geometric approach of von Staudt was based on the complete quadrilateral to express the relation of projective harmonic conjugates. Then he created a means of expressing the familiar numeric properties with his Algebra of Throws. English language versions of this process of deducing the properties of a field can be found in either the book by Oswald Veblen and John Young, Projective Geometry (1938), or more recently in John Stillwell's Four Pillars of Geometry (2005). Stillwell writes on page 120

... projective geometry is simpler than algebra in a certain sense, because we use only five geometric axioms to derive the nine field axioms.

The algebra of throws is commonly seen as a feature of cross-ratios since students ordinarily rely upon numbers without worry about their basis. However, cross-ratio calculations use metric features of geometry, features not admitted by purists. For instance, in 1961 Coxeter wrote Introduction to Geometry without mention of cross-ratio.

Boolean algebra and logic

Attempts of formal treatment of mathematics had started with Leibniz and Lambert (1728–1777), and continued with works by algebraists such as George Peacock (1791–1858). Systematic mathematical treatments of logic came with the British mathematician George Boole (1847) who devised an algebra that soon evolved into what is now called Boolean algebra, in which the only numbers were 0 and 1 and logical combinations (conjunction, disjunction, implication and negation) are operations similar to the addition and multiplication of integers. Additionally, De Morgan published his laws in 1847. Logic thus became a branch of mathematics. Boolean algebra is the starting point of mathematical logic and has important applications in computer science.

Charles Sanders Peirce built upon the work of Boole to develop a logical system for relations and quantifiers, which he published in several papers from 1870 to 1885.

The German mathematician Gottlob Frege (1848–1925) presented an independent development of logic with quantifiers in his Begriffsschrift (formula language) published in 1879, a work generally considered as marking a turning point in the history of logic. He exposed deficiencies in Aristotle's Logic, and pointed out the three expected properties of a mathematical theory:

1. Consistency: impossibility of proving contradictory statements.
2. Completeness: any statement is either provable or refutable (i.e. its negation is provable).
3. Decidability: there is a decision procedure to test any statement in the theory.

He then showed in Grundgesetze der Arithmetik (Basic Laws of Arithmetic) how arithmetic could be formalised in his new logic.

Frege's work was popularized by Bertrand Russell near the turn of the century. But Frege's two-dimensional notation had no success. Popular notations were (x) for universal and (∃x) for existential quantifiers, coming from Giuseppe Peano and William Ernest Johnson until the ∀ symbol was introduced by Gerhard Gentzen in 1935 and became canonical in the 1960s.

From 1890 to 1905, Ernst Schröder published Vorlesungen über die Algebra der Logik in three volumes. This work summarized and extended the work of Boole, De Morgan, and Peirce, and was a comprehensive reference to symbolic logic as it was understood at the end of the 19th century.

Peano arithmetic

The formalization of arithmetic (the theory of natural numbers) as an axiomatic theory started with Peirce in 1881 and continued with Richard Dedekind and Giuseppe Peano in 1888. This was still a second-order axiomatization (expressing induction in terms of arbitrary subsets, thus with an implicit use of set theory) as concerns for expressing theories in first-order logic were not yet understood. In Dedekind's work, this approach appears as completely characterizing natural numbers and providing recursive definitions of addition and multiplication from the successor function and mathematical induction.

Foundational crisis

The foundational crisis of mathematics (in German Grundlagenkrise der Mathematik) was the early 20th century's term for the search for proper foundations of mathematics.

Several schools of the philosophy of mathematics ran into difficulties one after the other in the 20th century, as the assumption that mathematics had any foundation that could be consistently stated within mathematics itself was heavily challenged by the discovery of various paradoxes (such as Russell's paradox).

The name "paradox" should not be confused with contradiction. A contradiction in a formal theory is a formal proof of an absurdity inside the theory (such as 2 + 2 = 5), showing that this theory is inconsistent and must be rejected. But a paradox may be either a surprising but true result in a given formal theory, or an informal argument leading to a contradiction, so that a candidate theory, if it is to be formalized, must disallow at least one of its steps; in this case the problem is to find a satisfying theory without contradiction. Both meanings may apply if the formalized version of the argument forms the proof of a surprising truth. For instance, Russell's paradox may be expressed as "there is no set of all sets" (except in some marginal axiomatic set theories).

Various schools of thought opposed each other. The leading school was that of the formalist approach, of which David Hilbert was the foremost proponent, culminating in what is known as Hilbert's program, which thought to ground mathematics on a small basis of a logical system proved sound by metamathematical finitistic means. The main opponent was the intuitionist school, led by L. E. J. Brouwer, which resolutely discarded formalism as a meaningless game with symbols (van Dalen, 2008). The fight was acrimonious. In 1920 Hilbert succeeded in having Brouwer, whom he considered a threat to mathematics, removed from the editorial board of Mathematische Annalen, the leading mathematical journal of the time.

Philosophical views

At the beginning of the 20th century, three schools of philosophy of mathematics opposed each other: Formalism, Intuitionism and Logicism.

Formalism

It has been claimed that formalists, such as David Hilbert (1862–1943), hold that mathematics is only a language and a series of games. Indeed, he used the words "formula game" in his 1927 response to L. E. J. Brouwer's criticisms:

And to what extent has the formula game thus made possible been successful? This formula game enables us to express the entire thought-content of the science of mathematics in a uniform manner and develop it in such a way that, at the same time, the interconnections between the individual propositions and facts become clear ... The formula game that Brouwer so deprecates has, besides its mathematical value, an important general philosophical significance. For this formula game is carried out according to certain definite rules, in which the technique of our thinking is expressed. These rules form a closed system that can be discovered and definitively stated.^[6]

Thus Hilbert is insisting that mathematics is not an arbitrary game with arbitrary rules; rather it must agree with how our thinking, and then our speaking and writing, proceeds.^[6]

We are not speaking here of arbitrariness in any sense. Mathematics is not like a game whose tasks are determined by arbitrarily stipulated rules. Rather, it is a conceptual system possessing internal necessity that can only be so and by no means otherwise.^[7]

The foundational philosophy of formalism, as exemplified by David Hilbert, is a response to the paradoxes of set theory, and is based on formal logic. Virtually all mathematical theorems today can be formulated as theorems of set theory. The truth of a mathematical statement, in this view, is represented by the fact that the statement can be derived from the axioms of set theory using the rules of formal logic.

Merely the use of formalism alone does not explain several issues: why we should use the axioms we do and not some others, why we should employ the logical rules we do and not some others, why do "true" mathematical statements (e.g., the laws of arithmetic) appear to be true, and so on. Hermann Weyl would ask these very questions of Hilbert:

What "truth" or objectivity can be ascribed to this theoretic construction of the world, which presses far beyond the given, is a profound philosophical problem. It is closely connected with the further question: what impels us to take as a basis precisely the particular axiom system developed by Hilbert? Consistency is indeed a necessary but not a sufficient condition. For the time being we probably cannot answer this question ...^[8]

In some cases these questions may be sufficiently answered through the study of formal theories, in disciplines such as reverse mathematics and computational complexity theory. As noted by Weyl, formal logical systems also run the risk of inconsistency; in Peano arithmetic, this arguably has already been settled with several proofs of consistency, but there is debate over whether or not they are sufficiently finitary to be meaningful. Gödel's second incompleteness theorem establishes that logical systems of arithmetic can never contain a valid proof of their own consistency. What Hilbert wanted to do was prove a logical system S was consistent, based on principles P that only made up a small part of S. But Gödel proved that the principles P could not even prove P to be consistent, let alone S.

Intuitionism

Intuitionists, such as L. E. J. Brouwer (1882–1966), hold that mathematics is a creation of the human mind. Numbers, like fairy tale characters, are merely mental entities, which would not exist if there were never any human minds to think about them.

The foundational philosophy of intuitionism or constructivism, as exemplified in the extreme by Brouwer and more coherently by Stephen Kleene, requires proofs to be "constructive" in nature – the existence of an object must be demonstrated rather than inferred from a demonstration of the impossibility of its non-existence. For example, as a consequence of this the form of proof known as reductio ad absurdum is suspect.

Some modern theories in the philosophy of mathematics deny the existence of foundations in the original sense. Some theories tend to focus on mathematical practice, and aim to describe and analyze the actual working of mathematicians as a social group. Others try to create a cognitive science of mathematics, focusing on human cognition as the origin of the reliability of mathematics when applied to the real world. These theories would propose to find foundations only in human thought, not in any objective outside construct. The matter remains controversial.

Logicism

Logicism is one of the schools of thought in the philosophy of mathematics, putting forth the theory that mathematics is an extension of logic and therefore some or all mathematics is reducible to logic. Bertrand Russell and Alfred North Whitehead championed this theory fathered by Gottlob Frege.

Set-theoretic Platonism

Many researchers in axiomatic set theory have subscribed to what is known as set-theoretic Platonism, exemplified by Kurt Gödel.

Several set theorists followed this approach and actively searched for axioms that may be considered as true for heuristic reasons and that would decide the continuum hypothesis. Many large cardinal axioms were studied, but the hypothesis always remained independent from them. Other types of axioms were considered, but none of them has reached consensus on the continuum hypothesis yet. Recent work by Hamkins proposes a more flexible alternative: a set-theoretic multiverse allowing free passage between set-theoretic universes that satisfy the continuum hypothesis and other universes that do not.

Indispensability argument for realism

This argument by Willard Quine and Hilary Putnam says (in Putnam's shorter words),

... quantification over mathematical entities is indispensable for science ...; therefore we should accept such quantification; but this commits us to accepting the existence of the mathematical entities in question.

However Putnam was not a Platonist.

Rough-and-ready realism

Few mathematicians are typically concerned on a daily, working basis over logicism, formalism or any other philosophical position. Instead, their primary concern is that the mathematical enterprise as a whole always remains productive. Typically, they see this as insured by remaining open-minded, practical and busy; as potentially threatened by becoming overly-ideological, fanatically reductionistic or lazy. Such a view was expressed by the Physics Nobel Prize laureate Richard Feynman:

People say to me, "Are you looking for the ultimate laws of physics?" No, I'm not ... If it turns out there is a simple ultimate law which explains everything, so be it – that would be very nice to discover. If it turns out it's like an onion with millions of layers ... then that's the way it is. But either way there's Nature and she's going to come out the way She is. So therefore when we go to investigate we shouldn't predecide what it is we're looking for only to find out more about it.^[9]

and also Steven Weinberg:^[10]

The insights of philosophers have occasionally benefited physicists, but generally in a negative fashion – by protecting them from the preconceptions of other philosophers. ... without some guidance from our preconceptions one could do nothing at all. It is just that philosophical principles have not generally provided us with the right preconceptions.

He believed that any undecidability in mathematics, such as the continuum hypothesis, could be potentially resolved despite the incompleteness theorem, by finding suitable further axioms to add to set theory.

Philosophical consequences of the Gödel's completeness theorem

Gödel's completeness theorem establishes an equivalence in first-order logic between the formal provability of a formula and its truth in all possible models. Precisely, for any consistent first-order theory it gives an "explicit construction" of a model described by the theory; this model will be countable if the language of the theory is countable. However this "explicit construction" is not algorithmic. It is based on an iterative process of completion of the theory, where each step of the iteration consists in adding a formula to the axioms if it keeps the theory consistent; but this consistency question is only semi-decidable (an algorithm is available to find any contradiction but if there is none this consistency fact can remain unprovable).

This can be seen as a giving a sort of justification to the Platonist view that the objects of our mathematical theories are real. More precisely, it shows that the mere assumption of the existence of the set of natural numbers as a totality (an actual infinity) suffices to imply the existence of a model (a world of objects) of any consistent theory. However several difficulties remain:

• For any consistent theory this usually does not give just one world of objects, but an infinity of possible worlds that the theory might equally describe, with a possible diversity of truths between them.
• In the case of set theory, none of the models obtained by this construction resemble the intended model, as they are countable while set theory intends to describe uncountable infinities. Similar remarks can be made in many other cases. For example, with theories that include arithmetic, such constructions generally give models that include non-standard numbers, unless the construction method was specifically designed to avoid them.
• As it gives models to all consistent theories without distinction, it gives no reason to accept or reject any axiom as long as the theory remains consistent, but regards all consistent axiomatic theories as referring to equally existing worlds. It gives no indication on which axiomatic system should be preferred as a foundation of mathematics.
• As claims of consistency are usually unprovable, they remain a matter of belief or non-rigorous kinds of justifications. Hence the existence of models as given by the completeness theorem needs in fact two philosophical assumptions: the actual infinity of natural numbers and the consistency of the theory.

Another consequence of the completeness theorem is that it justifies the conception of infinitesimals as actual infinitely small nonzero quantities, based on the existence of non-standard models as equally legitimate to standard ones. This idea was formalized by Abraham Robinson into the theory of nonstandard analysis.

More paradoxes

• 1920: Thoralf Skolem corrected Leopold Löwenheim's proof of what is now called the downward Löwenheim–Skolem theorem, leading to Skolem's paradox discussed in 1922, namely the existence of countable models of ZF, making infinite cardinalities a relative property.
• 1922: Proof by Abraham Fraenkel that the axiom of choice cannot be proved from the axioms of Zermelo set theory with urelements.
• 1931: Publication of Gödel's incompleteness theorems, showing that essential aspects of Hilbert's program could not be attained. It showed how to construct, for any sufficiently powerful and consistent recursively axiomatizable system – such as necessary to axiomatize the elementary theory of arithmetic on the (infinite) set of natural numbers – a statement that formally expresses its own unprovability, which he then proved equivalent to the claim of consistency of the theory; so that (assuming the consistency as true), the system is not powerful enough for proving its own consistency, let alone that a simpler system could do the job. It thus became clear that the notion of mathematical truth can not be completely determined and reduced to a purely formal system as envisaged in Hilbert's program. This dealt a final blow to the heart of Hilbert's program, the hope that consistency could be established by finitistic means (it was never made clear exactly what axioms were the "finitistic" ones, but whatever axiomatic system was being referred to, it was a 'weaker' system than the system whose consistency it was supposed to prove).
• 1936: Alfred Tarski proved his truth undefinability theorem.
• 1936: Alan Turing proved that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.
• 1938: Gödel proved the consistency of the axiom of choice and of the generalized continuum hypothesis.
• 1936–1937: Alonzo Church and Alan Turing, respectively, published independent papers showing that a general solution to the Entscheidungsproblem is impossible: the universal validity of statements in first-order logic is not decidable (it is only semi-decidable as given by the completeness theorem).
• 1955: Pyotr Novikov showed that there exists a finitely presented group G such that the word problem for G is undecidable.
• 1963: Paul Cohen showed that the Continuum Hypothesis is unprovable from ZFC. Cohen's proof developed the method of forcing, which is now an important tool for establishing independence results in set theory.
• 1964: Inspired by the fundamental randomness in physics, Gregory Chaitin starts publishing results on algorithmic information theory (measuring incompleteness and randomness in mathematics).^[11]
• 1966: Paul Cohen showed that the axiom of choice is unprovable in ZF even without urelements.
• 1970: Hilbert's tenth problem is proven unsolvable: there is no recursive solution to decide whether a Diophantine equation (multivariable polynomial equation) has a solution in integers.
• 1971: Suslin's problem is proven to be independent from ZFC.

Partial resolution of the crisis

Starting in 1935, the Bourbaki group of French mathematicians started publishing a series of books to formalize many areas of mathematics on the new foundation of set theory.

The intuitionistic school did not attract many adherents, and it was not until Bishop's work in 1967 that constructive mathematics was placed on a sounder footing.^[12]

One may consider that Hilbert's program has been partially completed, so that the crisis is essentially resolved, satisfying ourselves with lower requirements than Hilbert's original ambitions. His ambitions were expressed in a time when nothing was clear: it was not clear whether mathematics could have a rigorous foundation at all.

There are many possible variants of set theory, which differ in consistency strength, where stronger versions (postulating higher types of infinities) contain formal proofs of the consistency of weaker versions, but none contains a formal proof of its own consistency. Thus the only thing we don't have is a formal proof of consistency of whatever version of set theory we may prefer, such as ZF.

In practice, most mathematicians either do not work from axiomatic systems, or if they do, do not doubt the consistency of ZFC, generally their preferred axiomatic system. In most of mathematics as it is practiced, the incompleteness and paradoxes of the underlying formal theories never played a role anyway, and in those branches in which they do or whose formalization attempts would run the risk of forming inconsistent theories (such as logic and category theory), they may be treated carefully.

The development of category theory in the middle of the 20th century showed the usefulness of set theories larger than ZFC, such as Von Neumann–Bernays–Gödel set theory or Tarski–Grothendieck set theory, albeit that in very many cases the use of large cardinal axioms or Grothendieck Universes is formally eliminable.

One goal of the Reverse Mathematics program is to identify whether there are areas of 'core mathematics' in which foundational issues may again provoke a 'crisis.'