Mathematical logic emerged in the mid-19th century as a subfield of mathematics, reflecting the confluence of two traditions: formal
philosophical logic and mathematics. 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 nineteenth century with the aid of an artificial notation and a rigorously deductive method. Before this emergence, logic was studied with
rhetoric, with
calculationes, 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 in ancient
China,
India,
Greece,
Roman empire and the
Islamic world. Greek methods, particularly
Aristotelian logic (or term logic) as found in the
Organon, found wide application and acceptance in Western science and mathematics for millennia. The
Stoics, especially
Chrysippus, began the development of
propositional logic. 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. In 1847,
Vatroslav Bertić made substantial work on algebraization of logic, independently from Boole.
Charles Sanders Peirce later 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 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 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. In addition to the independence of the
parallel postulate, established by
Nikolai Lobachevsky in 1826, 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 developed a complete set of
axioms for geometry, building on
previous work by Pasch. 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, 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, 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. 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.
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 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. 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 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 discovered
Richard's paradox. Zermelo 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. Fraenkel proved that the axiom of choice cannot be proved from the axioms of Zermelo's set theory with
urelements. Later work by
Paul Cohen 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.
Symbolic logic Leopold Löwenheim and
Thoralf Skolem 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. as a student in
Vienna,1925 In his doctoral thesis,
Kurt Gödel 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. 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 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 gave a different consistency proof, which reduces the consistency of classical arithmetic to that of intuitionistic arithmetic in higher types. The first textbook on symbolic logic for the layman was written by
Lewis Carroll, author of ''
Alice's Adventures in Wonderland'', in 1896.
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
Éléments de mathématique, 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 or
computability theory, because early formalizations by Gödel and Kleene relied on recursive definitions of functions. 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 introduced the concepts of relative computability, foreshadowed by Turing, and the
arithmetical hierarchy. Kleene later generalized recursion theory to higher-order functionals. Kleene and
Georg Kreisel studied formal versions of intuitionistic mathematics, particularly in the context of proof theory. == Formal logical systems ==