Mathematical logic
Encyclopedia
Mathematical logic is a subfield of mathematics
with close connections to foundations of mathematics
, theoretical computer science
and philosophical logic
. The field includes both the mathematical study of logic
and the applications of formal logic to other areas of mathematics. The unifying themes in mathematical logic include the study of the expressive power of formal system
s 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 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 axiom
atic 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, rather than trying to find theories in which all of mathematics can be developed.
, 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.
, India, Greece and the Islamic world
. In the 18th century, 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.
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.
In logic, the term arithmetic refers to the theory of the natural number
s. Giuseppe Peano
(1888) 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 function
s was already developed by Bolzano
in 1817 (Felscher 2000), but remained relatively unknown.
Cauchy in 1821 defined continuity in terms of infinitesimal
s (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 number
s 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).
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 integer
s 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.
(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 number
s 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 remaining 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.
(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.
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 intutitionistic arithmetic in higher types.
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. 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.
Each area has a distinct focus, although many techniques and results are shared between multiple areas. The border lines between these fields, and the lines between 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 topos
es, which resemble generalized models of set theory that may employ classical or nonclassical logic.
are the most widely studied today, because of their applicability to foundations of mathematics
and because of their desirable proof-theoretic properties. Stronger classical logics such as second-order logic
or infinitary logic
are also studied, along with nonclassical logics such as intuitionistic logic
.
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 about 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 sufficiently strong, effectively given logical system there exists a statement which is true but not provable within that system. Here a logical system is effectively given if it is possible to decide, given any formula in the language of the system, whether the formula is an axiom. A logical system is sufficiently strong if it can express the Peano axioms
. 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.
s, which include a portion of set theory directly in their semantics.
The most well studied infinitary logic is
. 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 
such as
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 function
s.
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.
s 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.
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 algebra
s 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 algebra
s.
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 space
s.
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 structure
s.
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.
, also called computability theory, studies the properties of computable function
s and the Turing degree
s, which divide the uncomputable functions into sets which have the same level of uncomputability. Recursion theory also includes the study of generalized computability and definability. Recursion theory grew from of the work of Alonzo Church
and Alan Turing
in the 1930s, which was greatly extended by Kleene
and Post
in the 1940s.
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 machine
s, λ calculus
, and other systems. More advanced results concern the structure of the Turing degrees and the lattice
of recursively enumerable set
s.
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.
or function problem
is algorithmically unsolvable if there is no possible computable algorithm which 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).
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 system
s, 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.
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
.
's axioms for geometry, which had been taught for centuries as an example of the axiomatic method, were incomplete. The use of infinitesimal
s, 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 so do 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.
, reprinted in English translation in Gentzen's Collected works, M. E. Szabo, ed., North-Holland, Amsterdam, 1969.. English translation of title: "Completeness of the logical calculus".. English translation of title: "The completeness of the axioms of the calculus of logical functions"., see On Formally Undecidable Propositions of Principia Mathematica and Related Systems
for details on English translations., reprinted in English translation in Gödel's Collected Works, vol II, Soloman Feferman et al., eds. Oxford University Press, 1990., English 1902 edition (The Foundations of Geometry) republished 1980, Open Court, Chicago.. Lecture given at the International Congress of Mathematicians, 3 September 1928. Published in English translation as "The Grounding of Elementary Number Theory", in Mancosu 1998, pp. 266–273.. (German). Reprinted in English translation as "Geometric Investigations on the Theory of Parallel Lines" in Non-Euclidean Geometry, Robert Bonola (ed.), Dover, 1955. ISBN 0486600270 (German). Translated as "On possibilities in the calculus of relatives" in Jean van Heijenoort
, 1967. A Source Book in Mathematical Logic, 1879–1931. Harvard Univ. Press: 228–251... (Italian), excerpt reprinted in English stranslation as "The principles of arithmetic, presented by a new method", van Heijenoort 1976, pp. 83 97. (French), reprinted in English translation as "The principles of mathematics and the problems of sets", van Heijenoort 1976, pp. 142–144.. (German), reprinted in English translation as "Proof that every set can be well-ordered", van Heijenoort 1976, pp. 139–141. (German), reprinted in English translation as "A new proof of the possibility of a well-ordering", van Heijenoort 1976, pp. 183–198..
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
with close connections to foundations of mathematics
Foundations of mathematics
Foundations of mathematics is a term sometimes used for certain fields of mathematics, such as mathematical logic, axiomatic set theory, proof theory, model theory, type theory and recursion theory...
, theoretical computer science
Theoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....
and philosophical logic
Philosophical logic
Philosophical logic is a term introduced by Bertrand Russell to represent his idea that the workings of natural language and thought can only be adequately represented by an artificial language; essentially it was his formalization program for the natural language...
. The field includes both the mathematical study of logic
Logic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...
and the applications of formal logic to other areas of mathematics. The unifying themes in mathematical logic include the study of the expressive power of formal system
Formal system
In formal logic, a formal system consists of a formal language and a set of inference rules, used to derive an expression from one or more other premises that are antecedently supposed or derived . The axioms and rules may be called a deductive apparatus...
s and the deductive power of formal proof
Mathematical proof
In mathematics, a proof is a convincing demonstration that some mathematical statement is necessarily true. Proofs are obtained from deductive reasoning, rather than from inductive or empirical arguments. That is, a proof must demonstrate that a statement is true in all cases, without a single...
systems.
Mathematical logic is often divided into the fields of set theory
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
, model theory
Model theory
In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....
, recursion theory
Recursion theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
, and proof theory
Proof theory
Proof theory is a branch of mathematical logic that represents proofs as formal mathematical objects, facilitating their analysis by mathematical techniques. Proofs are typically presented as inductively-defined data structures such as plain lists, boxed lists, or trees, which are constructed...
. These areas share basic results on logic, particularly first-order logic
First-order logic
First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...
, and definability
Definable set
In mathematical logic, a definable set is an n-ary relation on the domain of a structure whose elements are precisely those elements satisfying some formula in the language of that structure...
. In computer science (particularly in the ACM Classification
ACM Computing Classification System
The ACM Computing Classification System is a subject classification system for computer science devised by the Association for Computing Machinery...
) mathematical logic encompasses additional topics not detailed in this article; see logic in computer science for those.
Since its inception, mathematical logic has contributed to, and has been motivated by, the study of foundations of mathematics
Foundations of mathematics
Foundations of mathematics is a term sometimes used for certain fields of mathematics, such as mathematical logic, axiomatic set theory, proof theory, model theory, type theory and recursion theory...
. This study began in the late 19th century with the development of axiom
Axiom
In traditional logic, an axiom or postulate is a proposition that is not proven or demonstrated but considered either to be self-evident or to define and delimit the realm of analysis. In other words, an axiom is a logical statement that is assumed to be true...
atic frameworks for geometry
Geometry
Geometry arose as the field of knowledge dealing with spatial relationships. Geometry was one of the two fields of pre-modern mathematics, the other being the study of numbers ....
, arithmetic
Arithmetic
Arithmetic or arithmetics is the oldest and most elementary branch of mathematics, used by almost everyone, for tasks ranging from simple day-to-day counting to advanced science and business calculations. It involves the study of quantity, especially as the result of combining numbers...
, and analysis
Analysis
Analysis is the process of breaking a complex topic or substance into smaller parts to gain a better understanding of it. The technique has been applied in the study of mathematics and logic since before Aristotle , though analysis as a formal concept is a relatively recent development.The word is...
. In the early 20th century it was shaped by David Hilbert
David Hilbert
David Hilbert was a German mathematician. He is recognized as one of the most influential and universal mathematicians of the 19th and early 20th centuries. Hilbert discovered and developed a broad range of fundamental ideas in many areas, including invariant theory and the axiomatization of...
's program
Hilbert's program
In mathematics, Hilbert's program, formulated by German mathematician David Hilbert, was a proposed solution to the foundational crisis of mathematics, when early attempts to clarify the foundations of mathematics were found to suffer from paradoxes and inconsistencies...
to prove the consistency of foundational theories. Results of Kurt Gödel
Kurt Gödel
Kurt Friedrich Gödel was an Austrian logician, mathematician and philosopher. Later in his life he emigrated to the United States to escape the effects of World War II. One of the most significant logicians of all time, Gödel made an immense impact upon scientific and philosophical thinking in the...
, Gerhard Gentzen
Gerhard Gentzen
Gerhard Karl Erich Gentzen was a German mathematician and logician. He had his major contributions in the foundations of mathematics, proof theory, especially on natural deduction and sequent calculus...
, 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, rather than trying to find theories in which all of mathematics can be developed.
History
Mathematical logic emerged in the mid-19th century as a subfield of mathematics independent of the traditional study of logic (Ferreirós 2001, p. 443). Before this emergence, logic was studied with rhetoricRhetoric
Rhetoric is the art of discourse, an art that aims to improve the facility of speakers or writers who attempt to inform, persuade, or motivate particular audiences in specific situations. As a subject of formal study and a productive civic practice, rhetoric has played a central role in the Western...
, through the syllogism
Syllogism
A syllogism is a kind of logical argument in which one proposition is inferred from two or more others of a certain form...
, and with philosophy
Philosophy
Philosophy is the study of general and fundamental problems, such as those connected with existence, knowledge, values, reason, mind, and language. Philosophy is distinguished from other ways of addressing such problems by its critical, generally systematic approach and its reliance on rational...
. The first half of the 20th century saw an explosion of fundamental results, accompanied by vigorous debate over the foundations of mathematics.
Early history
Sophisticated theories of logic were developed in many cultures, including ChinaLogic in China
In the history of logic, logic in China plays a particularly interesting role due to its length and relative isolation from the strong current of development of the study of logic in Europe and the Islamic world, though it may have some influence from Indian logic due to the spread of...
, India, Greece and the Islamic world
Logic in Islamic philosophy
Logic played an important role in Islamic philosophy .Islamic Logic or mantiq is similar science to what is called Traditional Logic in Western Sciences.- External links :*Routledge Encyclopedia of Philosophy: , Routledge, 1998...
. In the 18th century, attempts to treat the operations of formal logic in a symbolic or algebraic way had been made by philosophical mathematicians including Leibniz and Lambert
Johann Heinrich Lambert
Johann Heinrich Lambert was a Swiss mathematician, physicist, philosopher and astronomer.Asteroid 187 Lamberta was named in his honour.-Biography:...
, but their labors remained isolated and little known.
19th century
In the middle of the nineteenth century, George BooleGeorge Boole
George Boole was an English mathematician and philosopher.As the inventor of Boolean logic—the basis of modern digital computer logic—Boole is regarded in hindsight as a founder of the field of computer science. Boole said,...
and then Augustus De Morgan
Augustus De Morgan
Augustus De Morgan was a British mathematician and logician. He formulated De Morgan's laws and introduced the term mathematical induction, making its idea rigorous. The crater De Morgan on the Moon is named after him....
presented systematic mathematical treatments of logic. Their work, building on work by algebraists such as George Peacock
George Peacock
George Peacock was an English mathematician.-Life:Peacock was born on 9 April 1791 at Thornton Hall, Denton, near Darlington, County Durham. His father, the Rev. Thomas Peacock, was a clergyman of the Church of England, incumbent and for 50 years curate of the parish of Denton, where he also kept...
, extended the traditional Aristotelian doctrine of logic into a sufficient framework for the study of foundations of mathematics
Foundations of mathematics
Foundations of mathematics is a term sometimes used for certain fields of mathematics, such as mathematical logic, axiomatic set theory, proof theory, model theory, type theory and recursion theory...
(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
Gottlob Frege
Friedrich Ludwig Gottlob Frege was a German mathematician, logician and philosopher. He is considered to be one of the founders of modern logic, and made major contributions to the foundations of mathematics. He is generally considered to be the father of analytic philosophy, for his writings on...
presented an independent development of logic with quantifiers in his Begriffsschrift
Begriffsschrift
Begriffsschrift is a book on logic by Gottlob Frege, published in 1879, and the formal system set out in that book...
, 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
Bertrand Russell
Bertrand Arthur William Russell, 3rd Earl Russell, OM, FRS was a British philosopher, logician, mathematician, historian, and social critic. At various points in his life he considered himself a liberal, a socialist, and a pacifist, but he also admitted that he had never been any of these things...
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
Ernst Schröder
Ernst Schröder was a German mathematician mainly known for his work on algebraic logic. He is a major figure in the history of mathematical logic , by virtue of summarizing and extending the work of George Boole, Augustus De Morgan, Hugh MacColl, and especially Charles Peirce...
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
Some 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 number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s. Giuseppe Peano
Giuseppe Peano
Giuseppe Peano was an Italian mathematician, whose work was of philosophical value. The author of over 200 books and papers, he was a founder of mathematical logic and set theory, to which he contributed much notation. The standard axiomatization of the natural numbers is named the Peano axioms in...
(1888) published a set of axioms for arithmetic that came to bear his name (Peano axioms
Peano axioms
In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are a set of axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano...
), 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
Richard Dedekind
Julius Wilhelm Richard Dedekind was a German mathematician who did important work in abstract algebra , algebraic number theory and the foundations of the real numbers.-Life:...
showed that the natural numbers are uniquely characterized by their induction
Mathematical induction
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...
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
Parallel postulate
In geometry, the parallel postulate, also called Euclid's fifth postulate because it is the fifth postulate in Euclid's Elements, is a distinctive axiom in Euclidean geometry...
, 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
Hilbert's axioms
Hilbert's axioms are a set of 20 assumptions proposed by David Hilbert in 1899 in his book Grundlagen der Geometrie , as the foundation for a modern treatment of Euclidean geometry...
, building on previous work
Pasch's axiom
In geometry, Pasch's axiom is a result of plane geometry used by Euclid, but yet which cannot be derived from Euclid's postulates. Its axiomatic role was discovered by Moritz Pasch.The axiom states that, in the plane,...
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
Real line
In mathematics, the real line, or real number line is the line whose points are the real numbers. That is, the real line is the set of all real numbers, viewed as a geometric space, namely the Euclidean space of dimension one...
. 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
Real analysis
Real analysis, is a branch of mathematical analysis dealing with the set of real numbers and functions of a real variable. In particular, it deals with the analytic properties of real functions and sequences, including convergence and limits of sequences of real numbers, the calculus of the real...
, including theories of convergence of functions and Fourier series
Fourier series
In mathematics, a Fourier series decomposes periodic functions or periodic signals into the sum of a set of simple oscillating functions, namely sines and cosines...
. Mathematicians such as Karl Weierstrass
Karl Weierstrass
Karl Theodor Wilhelm Weierstrass was a German mathematician who is often cited as the "father of modern analysis".- Biography :Weierstrass was born in Ostenfelde, part of Ennigerloh, Province of Westphalia....
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
Arithmetization of analysis
The arithmetization of analysis was a research program in the foundations of mathematics carried out in the second half of the 19th century. Kronecker originally introduced the term arithmetization of analysis, by which he meant its constructivization in the context of the natural numbers...
, which sought to axiomatize analysis using properties of the natural numbers. The modern (ε, δ)-definition of limit and continuous function
Continuous function
In mathematics, a continuous function is a function for which, intuitively, "small" changes in the input result in "small" changes in the output. Otherwise, a function is said to be "discontinuous". A continuous function with a continuous inverse function is called "bicontinuous".Continuity of...
s was already developed by Bolzano
Bernard Bolzano
Bernhard Placidus Johann Nepomuk Bolzano , Bernard Bolzano in English, was a Bohemian mathematician, logician, philosopher, theologian, Catholic priest and antimilitarist of German mother tongue.-Family:Bolzano was the son of two pious Catholics...
in 1817 (Felscher 2000), but remained relatively unknown.
Cauchy in 1821 defined continuity in terms of infinitesimal
Infinitesimal
Infinitesimals have been used to express the idea of objects so small that there is no way to see them or to measure them. The word infinitesimal comes from a 17th century Modern Latin coinage infinitesimus, which originally referred to the "infinite-th" item in a series.In common speech, an...
s (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
Georg Cantor
Georg Ferdinand Ludwig Philipp Cantor was a German mathematician, best known as the inventor of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of one-to-one correspondence between the members of two sets, defined infinite and well-ordered sets,...
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 number
Transfinite number
Transfinite numbers are numbers that are "infinite" in the sense that they are larger than all finite numbers, yet not necessarily absolutely infinite. The term transfinite was coined by Georg Cantor, who wished to avoid some of the implications of the word infinite in connection with these...
s in a series of publications. In 1891, he published a new proof of the uncountability of the real numbers that introduced the diagonal argument
Cantor's diagonal argument
Cantor's diagonal argument, also called the diagonalisation argument, the diagonal slash argument or the diagonal method, was published in 1891 by Georg Cantor as a mathematical proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural...
, and used this method to prove Cantor's theorem
Cantor's theorem
In elementary set theory, Cantor's theorem states that, for any set A, the set of all subsets of A has a strictly greater cardinality than A itself...
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
David Hilbert
David Hilbert was a German mathematician. He is recognized as one of the most influential and universal mathematicians of the 19th and early 20th centuries. Hilbert discovered and developed a broad range of fundamental ideas in many areas, including invariant theory and the axiomatization of...
posed a famous list of 23 problems
Hilbert's problems
Hilbert's problems form a list of twenty-three problems in mathematics published by German mathematician David Hilbert in 1900. The problems were all unsolved at the time, and several of them were very influential for 20th century mathematics...
for the next century. The first two of these were to resolve the continuum hypothesis
Continuum hypothesis
In mathematics, the continuum hypothesis is a hypothesis, advanced by Georg Cantor in 1874, about the possible sizes of infinite sets. It states:Establishing the truth or falsehood of the continuum hypothesis is the first of Hilbert's 23 problems presented in the year 1900...
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 integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s has a solution. Subsequent work to resolve these problems shaped the direction of mathematical logic, as did the effort to resolve Hilbert's Entscheidungsproblem
Entscheidungsproblem
In mathematics, the is a challenge posed by David Hilbert in 1928. The asks for an algorithm that will take as input a description of a formal language and a mathematical statement in the language and produce as output either "True" or "False" according to whether the statement is true or false...
, 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 ZermeloErnst Zermelo
Ernst Friedrich Ferdinand Zermelo was a German mathematician, whose work has major implications for the foundations of mathematics and hence on philosophy. He is known for his role in developing Zermelo–Fraenkel axiomatic set theory and his proof of the well-ordering theorem.-Life:He graduated...
(1904) gave a proof that every set could be well-ordered, a result Georg Cantor
Georg Cantor
Georg Ferdinand Ludwig Philipp Cantor was a German mathematician, best known as the inventor of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of one-to-one correspondence between the members of two sets, defined infinite and well-ordered sets,...
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
Cesare Burali-Forti
Cesare Burali-Forti was an Italian mathematician.He was born in Arezzo, and was an assistant of Giuseppe Peano in Turin from 1894 to 1896, during which time he discovered what came to be called the Burali-Forti paradox of Cantorian set theory. He died in Turin.-Books by C. Burali-Forti:* with R....
(1897) was the first to state a paradox: the Burali-Forti paradox
Burali-Forti paradox
In set theory, a field of mathematics, the Burali-Forti paradox demonstrates that naively constructing "the set of all ordinal numbers" leads to a contradiction and therefore shows an antinomy in a system that allows its construction...
shows that the collection of all ordinal number
Ordinal number
In set theory, an ordinal number, or just ordinal, is the order type of a well-ordered set. They are usually identified with hereditarily transitive sets. Ordinals are an extension of the natural numbers different from integers and from cardinals...
s cannot form a set. Very soon thereafter, Bertrand Russell
Bertrand Russell
Bertrand Arthur William Russell, 3rd Earl Russell, OM, FRS was a British philosopher, logician, mathematician, historian, and social critic. At various points in his life he considered himself a liberal, a socialist, and a pacifist, but he also admitted that he had never been any of these things...
discovered Russell's paradox
Russell's paradox
In the foundations of mathematics, Russell's paradox , discovered by Bertrand Russell in 1901, showed that the naive set theory created by Georg Cantor leads to a contradiction...
in 1901, and Jules Richard
Jules Richard
Jules Richard was a French mathematician.- Life and Works:...
(1905) discovered Richard's paradox
Richard's paradox
In logic, Richard's paradox is a semantical antinomy in set theory and natural language first described by the French mathematician Jules Richard in 1905. Today, the paradox is ordinarily used in order to motivate the importance of carefully distinguishing between mathematics and metamathematics...
.
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
Zermelo–Fraenkel set theory
In mathematics, Zermelo–Fraenkel set theory with the axiom of choice, named after mathematicians Ernst Zermelo and Abraham Fraenkel and commonly abbreviated ZFC, is one of several axiomatic systems that were proposed in the early twentieth century to formulate a theory of sets without the paradoxes...
(ZF). Zermelo's axioms incorporated the principle of limitation of size
Limitation of size
In the philosophy of mathematics, specifically the philosophical foundations of set theory, limitation of size is a concept developed by Philip Jourdain and/or Georg Cantor to avoid Cantor's paradox. It identifies certain "inconsistent multiplicities", in Cantor's terminology, that cannot be sets...
to avoid Russell's paradox.
In 1910, the first volume of Principia Mathematica
Principia Mathematica
The Principia Mathematica is a three-volume work on the foundations of mathematics, written by Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1913...
by Russell and Alfred North Whitehead
Alfred North Whitehead
Alfred North Whitehead, OM FRS was an English mathematician who became a philosopher. He wrote on algebra, logic, foundations of mathematics, philosophy of science, physics, metaphysics, and education...
was published. This seminal work developed the theory of functions and cardinality in a completely formal framework of type theory
Type theory
In mathematics, logic and computer science, type theory is any of several formal systems that can serve as alternatives to naive set theory, or the study of such formalisms in general...
, 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 remaining axioms of Zermelo's set theory with urelements. Later work by Paul Cohen
Paul Cohen (mathematician)
Paul Joseph Cohen was an American mathematician best known for his proof of the independence of the continuum hypothesis and the axiom of choice from Zermelo–Fraenkel set theory, the most widely accepted axiomatization of set theory.-Early years:Cohen was born in Long Branch, New Jersey, into a...
(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
Forcing (mathematics)
In the mathematical discipline of set theory, forcing is a technique invented by Paul Cohen for proving consistency and independence results. It was first used, in 1963, to prove the independence of the axiom of choice and the continuum hypothesis from Zermelo–Fraenkel set theory...
, which is now an important tool for establishing independence results in set theory.
Symbolic logic
Leopold LöwenheimLeopold Löwenheim
Leopold Löwenheim was a German mathematician, known for his work in mathematical logic. The Nazi regime forced him to retire because under the Nuremberg Laws he was considered only three quarters Aryan. In 1943 much of his work was destroyed during a bombing raid on Berlin...
(1915) and Thoralf Skolem
Thoralf Skolem
Thoralf Albert Skolem was a Norwegian mathematician known mainly for his work on mathematical logic and set theory.-Life:...
(1920) obtained the Löwenheim–Skolem theorem
Löwenheim–Skolem theorem
In mathematical logic, the Löwenheim–Skolem theorem, named for Leopold Löwenheim and Thoralf Skolem, states that if a countable first-order theory has an infinite model, then for every infinite cardinal number κ it has a model of size κ...
, 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
Structure (mathematical logic)
In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations which are defined on it....
. This counterintuitive fact became known as Skolem's paradox
Skolem's paradox
In mathematical logic and philosophy, Skolem's paradox is a seeming contradiction that arises from the downward Löwenheim–Skolem theorem. Thoralf Skolem was the first to discuss the seemingly contradictory aspects of the theorem, and to discover the relativity of set-theoretic notions now known as...
.
In his doctoral thesis, Kurt Gödel
Kurt Gödel
Kurt Friedrich Gödel was an Austrian logician, mathematician and philosopher. Later in his life he emigrated to the United States to escape the effects of World War II. One of the most significant logicians of all time, Gödel made an immense impact upon scientific and philosophical thinking in the...
(1929) proved the completeness theorem, which establishes a correspondence between syntax and semantics in first-order logic
First-order logic
First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...
. Gödel used the completeness theorem to prove the compactness theorem
Compactness theorem
In mathematical logic, the compactness theorem states that a set of first-order sentences has a model if and only if every finite subset of it has a model...
, 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
On Formally Undecidable Propositions of Principia Mathematica and Related Systems
Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I is a paper in mathematical logic by Kurt Gödel...
, 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 (1936) proved the consistency of arithmetic using a finitistic system together with a principle of transfinite induction
Transfinite induction
Transfinite induction is an extension of mathematical induction to well-ordered sets, for instance to sets of ordinal numbers or cardinal numbers.- Transfinite induction :Let P be a property defined for all ordinals α...
. 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 intutitionistic arithmetic in higher types.
Beginnings of the other branches
Alfred TarskiAlfred Tarski
Alfred Tarski was a Polish logician and mathematician. Educated at the University of Warsaw and a member of the Lwow-Warsaw School of Logic and the Warsaw School of Mathematics and philosophy, he emigrated to the USA in 1939, and taught and carried out research in mathematics at the University of...
developed the basics of model theory
Model theory
In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....
.
Beginning in 1935, a group of prominent mathematicians collaborated under the pseudonym Nicolas Bourbaki
Nicolas Bourbaki
Nicolas Bourbaki is the collective pseudonym under which a group of 20th-century mathematicians wrote a series of books presenting an exposition of modern advanced mathematics, beginning in 1935. With the goal of founding all of mathematics on set theory, the group strove for rigour and generality...
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. When these definitions were shown equivalent to Turing's formalization involving Turing machines, it became clear that a new concept – the computable function
Computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register...
– 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
Stephen Cole Kleene
Stephen Cole Kleene was an American mathematician who helped lay the foundations for theoretical computer science...
and Emil Leon Post
Emil Leon Post
Emil Leon Post was a mathematician and logician. He is best known for his work in the field that eventually became known as computability theory.-Early work:...
. Kleene (1943) introduced the concepts of relative computability, foreshadowed by Turing (1939), and the arithmetical hierarchy
Arithmetical hierarchy
In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene-Mostowski hierarchy classifies certain sets based on the complexity of formulas that define them...
. 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.
Subfields and scope
The Handbook of Mathematical Logic makes a rough division of contemporary mathematical logic into four areas:- set theorySet theorySet theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
- model theoryModel theoryIn mathematics, model theory is the study of mathematical structures using tools from mathematical logic....
- recursion theoryRecursion theoryComputability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
, and - proof theoryProof theoryProof theory is a branch of mathematical logic that represents proofs as formal mathematical objects, facilitating their analysis by mathematical techniques. Proofs are typically presented as inductively-defined data structures such as plain lists, boxed lists, or trees, which are constructed...
and constructive mathematics (considered as parts of a single area).
Each area has a distinct focus, although many techniques and results are shared between multiple areas. The border lines between these fields, and the lines between 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
Löb's theorem
In mathematical logic, Löb's theorem states that in a theory with Peano arithmetic, for any formula P, if it is provable that "if P is provable then P", then P is provable...
in modal logic. The method of forcing
Forcing (mathematics)
In the mathematical discipline of set theory, forcing is a technique invented by Paul Cohen for proving consistency and independence results. It was first used, in 1963, to prove the independence of the axiom of choice and the continuum hypothesis from Zermelo–Fraenkel set theory...
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
Category theory
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...
uses many formal axiomatic methods, and includes the study of categorical logic
Categorical logic
Categorical logic is a branch of category theory within mathematics, adjacent to mathematical logic but more notable for its connections to theoretical computer science. In broad terms, categorical logic represents both syntax and semantics by a category, and an interpretation by a functor...
, 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
Saunders Mac Lane
Saunders Mac Lane was an American mathematician who cofounded category theory with Samuel Eilenberg.-Career:...
have proposed category theory as a foundational system for mathematics, independent of set theory. These foundations use topos
Topos
In mathematics, a topos is a type of category that behaves like the category of sheaves of sets on a topological space...
es, which resemble generalized models of set theory that may employ classical or nonclassical logic.
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, or signature. The systems of propositional logic and first-order logicFirst-order logic
First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...
are the most widely studied today, because of their applicability to foundations of mathematics
Foundations of mathematics
Foundations of mathematics is a term sometimes used for certain fields of mathematics, such as mathematical logic, axiomatic set theory, proof theory, model theory, type theory and recursion theory...
and because of their desirable proof-theoretic properties. Stronger classical logics such as second-order logic
Second-order logic
In logic and mathematics second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory....
or infinitary logic
Infinitary logic
An infinitary logic is a logic that allows infinitely long statements and/or infinitely long proofs. Some infinitary logics may have different properties from those of standard first-order logic. In particular, infinitary logics may fail to be compact or complete. Notions of compactness and...
are also studied, along with nonclassical logics such as intuitionistic logic
Intuitionistic logic
Intuitionistic logic, or constructive logic, is a symbolic logic system differing from classical logic in its definition of the meaning of a statement being true. In classical logic, all well-formed statements are assumed to be either true or false, even if we do not have a proof of either...
.
First-order logic
First-order logic is a particular formal system of logic. Its syntaxSyntax
In linguistics, syntax is the study of the principles and rules for constructing phrases and sentences in natural languages....
involves only finite expressions as well-formed formulas, while its semantics
Semantics
Semantics is the study of meaning. It focuses on the relation between signifiers, such as words, phrases, signs and symbols, and what they stand for, their denotata....
are characterized by the limitation of all quantifiers to a fixed domain of discourse
Domain of discourse
In the formal sciences, the domain of discourse, also called the universe of discourse , is the set of entities over which certain variables of interest in some formal treatment may range...
.
Early results about formal logic established limitations of first-order logic. The Löwenheim–Skolem theorem
Löwenheim–Skolem theorem
In mathematical logic, the Löwenheim–Skolem theorem, named for Leopold Löwenheim and Thoralf Skolem, states that if a countable first-order theory has an infinite model, then for every infinite cardinal number κ it has a model of size κ...
(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
Isomorphism
In abstract algebra, an isomorphism is a mapping between objects that shows a relationship between two properties or operations. If there exists an isomorphism between two structures, the two structures are said to be isomorphic. In a certain sense, isomorphic structures are...
. 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's completeness theorem
Gödel's completeness theorem is a fundamental theorem in mathematical logic that establishes a correspondence between semantic truth and syntactic provability in first-order logic. It was first proved by Kurt Gödel in 1929....
(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
Compactness theorem
In mathematical logic, the compactness theorem states that a set of first-order sentences has a model if and only if every finite subset of it has a model...
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
If and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
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
Model theory
In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....
, and they are a key reason for the prominence of first-order logic in mathematics.
Gödel's incompleteness theorems
Gödel's incompleteness theorems
Gödel's incompleteness theorems are two theorems of mathematical logic that establish inherent limitations of all but the most trivial axiomatic systems capable of doing arithmetic. The theorems, proven by Kurt Gödel in 1931, are important both in mathematical logic and in the philosophy of...
(Gödel 1931) establish additional limits on first-order axiomatizations. The first incompleteness theorem states that for any sufficiently strong, effectively given logical system there exists a statement which is true but not provable within that system. Here a logical system is effectively given if it is possible to decide, given any formula in the language of the system, whether the formula is an axiom. A logical system is sufficiently strong if it can express the Peano axioms
Peano axioms
In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are a set of axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano...
. 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
Elementary substructure
In model theory, a field within mathematical logic, two structures M and N of the same signature σ are called elementarily equivalent if they satisfy the same first-order σ-sentences....
, 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 logicHigher-order logic
In mathematics and logic, a higher-order logic is a form of predicate logic that is distinguished from first-order logic by additional quantifiers and a stronger semantics...
s, which include a portion of set theory directly in their semantics.
The most well studied infinitary logic is
. 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 such asHigher-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 function
Primitive recursive function
The primitive recursive functions are defined using primitive recursion and composition as central operations and are a strict subset of the total µ-recursive functions...
s.
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
Fuzzy logic
Fuzzy logic is a form of many-valued logic; it deals with reasoning that is approximate rather than fixed and exact. In contrast with traditional logic theory, where binary sets have two-valued logic: true or false, fuzzy logic variables may have a truth value that ranges in degree between 0 and 1...
. Lindström's theorem
Lindström's theorem
In mathematical logic, Lindström's theorem states that first-order logic is the strongest logic In mathematical logic, Lindström's theorem (named after Swedish logician Per Lindström) states that first-order logic is the strongest logic In mathematical logic, Lindström's theorem (named after...
implies that the only extension of first-order logic satisfying both the compactness theorem
Compactness theorem
In mathematical logic, the compactness theorem states that a set of first-order sentences has a model if and only if every finite subset of it has a model...
and the Downward Löwenheim–Skolem theorem
Löwenheim–Skolem theorem
In mathematical logic, the Löwenheim–Skolem theorem, named for Leopold Löwenheim and Thoralf Skolem, states that if a countable first-order theory has an infinite model, then for every infinite cardinal number κ it has a model of size κ...
is first-order logic.
Nonclassical and modal logic
Modal logicModal logic
Modal logic is a type of formal logic that extends classical propositional and predicate logic to include operators expressing modality. Modals — words that express modalities — qualify a statement. For example, the statement "John is happy" might be qualified by saying that John is...
s 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
Intuitionistic logic
Intuitionistic logic, or constructive logic, is a symbolic logic system differing from classical logic in its definition of the meaning of a statement being true. In classical logic, all well-formed statements are assumed to be either true or false, even if we do not have a proof of either...
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 logicAlgebraic logic
In mathematical logic, algebraic logic is the study of logic presented in an algebraic style.What is now usually called classical algebraic logic focuses on the identification and algebraic description of models appropriate for the study of various logics and connected problems...
uses the methods of abstract algebra
Abstract algebra
Abstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras...
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 algebra
Heyting algebra
In mathematics, a Heyting algebra, named after Arend Heyting, is a bounded lattice equipped with a binary operation a→b of implication such that ∧a ≤ b, and moreover a→b is the greatest such in the sense that if c∧a ≤ b then c ≤ a→b...
s 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 algebra
Cylindric algebra
The notion of cylindric algebra, invented by Alfred Tarski, arises naturally in the algebraization of first-order logic with equality. This is comparable to the role Boolean algebras play for propositional logic. Indeed, cylindric algebras are Boolean algebras equipped with additional...
s.
Set theory
Set theorySet theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
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
Zermelo–Fraenkel set theory
In mathematics, Zermelo–Fraenkel set theory with the axiom of choice, named after mathematicians Ernst Zermelo and Abraham Fraenkel and commonly abbreviated ZFC, is one of several axiomatic systems that were proposed in the early twentieth century to formulate a theory of sets without the paradoxes...
(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
Von Neumann–Bernays–Gödel set theory
In the foundations of mathematics, von Neumann–Bernays–Gödel set theory is an axiomatic set theory that is a conservative extension of the canonical axiomatic set theory ZFC. A statement in the language of ZFC is provable in NBG if and only if it is provable in ZFC. The ontology of NBG includes...
(NBG), Morse–Kelley set theory
Morse–Kelley set theory
In the foundation of mathematics, Morse–Kelley set theory or Kelley–Morse set theory is a first order axiomatic set theory that is closely related to von Neumann–Bernays–Gödel set theory...
(MK), and New Foundations
New Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
(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
Kripke–Platek set theory
The Kripke–Platek axioms of set theory are a system of axioms for axiomatic set theory developed by Saul Kripke and Richard Platek. The axiom system, written in first-order logic, has an infinite number of axioms because an infinite axiom schema is used.KP is weaker than Zermelo–Fraenkel set theory...
is closely related to generalized recursion theory.
Two famous statements in set theory are the axiom of choice and the continuum hypothesis
Continuum hypothesis
In mathematics, the continuum hypothesis is a hypothesis, advanced by Georg Cantor in 1874, about the possible sizes of infinite sets. It states:Establishing the truth or falsehood of the continuum hypothesis is the first of Hilbert's 23 problems presented in the year 1900...
. 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
Stefan Banach
Stefan Banach was a Polish mathematician who worked in interwar Poland and in Soviet Ukraine. He is generally considered to have been one of the 20th century's most important and influential mathematicians....
and Alfred Tarski
Alfred Tarski
Alfred Tarski was a Polish logician and mathematician. Educated at the University of Warsaw and a member of the Lwow-Warsaw School of Logic and the Warsaw School of Mathematics and philosophy, he emigrated to the USA in 1939, and taught and carried out research in mathematics at the University of...
(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
Banach–Tarski paradox
The Banach–Tarski paradox is a theorem in set theoretic geometry which states the following: Given a solid ball in 3-dimensional space, there exists a decomposition of the ball into a finite number of non-overlapping pieces , which can then be put back together in a different way to yield two...
, 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
Constructible universe
In mathematics, the constructible universe , denoted L, is a particular class of sets which can be described entirely in terms of simpler sets. It was introduced by Kurt Gödel in his 1938 paper "The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis"...
of set theory in which the continuum hypothesis must hold. In 1963, Paul Cohen
Paul Cohen (mathematician)
Paul Joseph Cohen was an American mathematician best known for his proof of the independence of the continuum hypothesis and the axiom of choice from Zermelo–Fraenkel set theory, the most widely accepted axiomatization of set theory.-Early years:Cohen was born in Long Branch, New Jersey, into a...
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
W. Hugh Woodin
William Hugh Woodin is an American mathematician and set theorist at University of California, Berkeley. He has made many notable contributions to the theory of inner models and determinacy. A type of large cardinal, the Woodin cardinal, bears his name.-Biography:Born in Tucson, Arizona, Woodin...
, although its importance is not yet clear (Woodin 2001).
Contemporary research in set theory includes the study of large cardinals and determinacy
Determinacy
In set theory, a branch of mathematics, determinacy is the study of under what circumstances one or the other player of a game must have a winning strategy, and the consequences of the existence of such strategies.-Games:...
. 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
Inaccessible cardinal
In set theory, an uncountable regular cardinal number is called weakly inaccessible if it is a weak limit cardinal, and strongly inaccessible, or just inaccessible, if it is a strong limit cardinal. Some authors do not require weakly and strongly inaccessible cardinals to be uncountable...
, 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 space
Polish space
In the mathematical discipline of general topology, a Polish space is a separable completely metrizable topological space; that is, a space homeomorphic to a complete metric space that has a countable dense subset. Polish spaces are so named because they were first extensively studied by Polish...
s.
Model theory
Model theoryModel theory
In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....
studies the models of various formal theories. Here a theory
Theory (mathematical logic)
In mathematical logic, a theory is a set of sentences in a formal language. Usually a deductive system is understood from context. An element \phi\in T of a theory T is then called an axiom of the theory, and any sentence that follows from the axioms is called a theorem of the theory. Every axiom...
is a set of formulas in a particular formal logic and signature
Signature (logic)
In logic, especially mathematical logic, a signature lists and describes the non-logical symbols of a formal language. In universal algebra, a signature lists the operations that characterize an algebraic structure. In model theory, signatures are used for both purposes.Signatures play the same...
, while a model
Structure (mathematical logic)
In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations which are defined on it....
is a structure that gives a concrete interpretation of the theory. Model theory is closely related to universal algebra
Universal algebra
Universal algebra is the field of mathematics that studies algebraic structures themselves, not examples of algebraic structures....
and algebraic geometry
Algebraic geometry
Algebraic geometry is a branch of mathematics which combines techniques of abstract algebra, especially commutative algebra, with the language and the problems of geometry. It occupies a central place in modern mathematics and has multiple conceptual connections with such diverse fields as complex...
, 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
Elementary class
In the branch of mathematical logic called model theory, an elementary class is a class consisting of all structures satisfying a fixed first-order theory.- Definition :...
; 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
Quantifier elimination
Quantifier elimination is a concept of simplification used in mathematical logic, model theory, and theoretical computer science. One way of classifying formulas is by the amount of quantification...
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 structure
O-minimal theory
In mathematical logic, and more specifically in model theory, an infinite structure which is totally ordered by In mathematical logic, and more specifically in model theory, an infinite structure which is totally ordered by...
s.
Morley's categoricity theorem
Morley's categoricity theorem
In model theory, a branch of mathematical logic, a theory is κ-categorical if it has exactly one model of cardinality κ up to isomorphism....
, proved by Michael D. Morley
Michael D. Morley
Michael Darwin Morley is an American mathematician, currently professor emeritus at Cornell University.His research is in advanced mathematical logic and model theory, and he is best known for Morley's categoricity theorem, which he proved in his Ph.D. thesis "Categoricity in Power" in 1962.His...
(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
Continuum hypothesis
In mathematics, the continuum hypothesis is a hypothesis, advanced by Georg Cantor in 1874, about the possible sizes of infinite sets. It states:Establishing the truth or falsehood of the continuum hypothesis is the first of Hilbert's 23 problems presented in the year 1900...
is that a complete theory with less than continuum many nonisomorphic countable models can have only countably many. Vaught's conjecture
Vaught conjecture
The Vaught conjecture is a conjecture in the mathematical field of model theory originally proposed by Robert Lawson Vaught in 1961. It states that the number of countable models of a first-order complete theory in a countable language is finite or ℵ0 or 2ℵ0...
, named after Robert Lawson Vaught
Robert Lawson Vaught
Robert Lawson Vaught was a mathematical logician, and one of the founders of model theory.-Life:Vaught was a bit of a musical prodigy in his youth, in his case the piano. He began his university studies at Pomona College, at age 16. When World War II broke out, he enlisted US Navy which assigned...
, says that this is true even independently of the continuum hypothesis. Many special cases of this conjecture have been established.
Recursion theory
Recursion theoryRecursion theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
, also called computability theory, studies the properties of computable function
Computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register...
s and the Turing degree
Turing degree
In computer science and mathematical logic the Turing degree or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set...
s, which divide the uncomputable functions into sets which have the same level of uncomputability. Recursion theory also includes the study of generalized computability and definability. Recursion theory grew from of the work of Alonzo Church
Alonzo Church
Alonzo Church was an American mathematician and logician who made major contributions to mathematical logic and the foundations of theoretical computer science. He is best known for the lambda calculus, Church–Turing thesis, Frege–Church ontology, and the Church–Rosser theorem.-Life:Alonzo Church...
and Alan Turing
Alan Turing
Alan Mathison Turing, OBE, FRS , was an English mathematician, logician, cryptanalyst, and computer scientist. He was highly influential in the development of computer science, providing a formalisation of the concepts of "algorithm" and "computation" with the Turing machine, which played a...
in the 1930s, which was greatly extended by Kleene
Stephen Cole Kleene
Stephen Cole Kleene was an American mathematician who helped lay the foundations for theoretical computer science...
and Post
Emil Leon Post
Emil Leon Post was a mathematician and logician. He is best known for his work in the field that eventually became known as computability theory.-Early work:...
in the 1940s.
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 machine
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
s, λ calculus
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
, and other systems. More advanced results concern the structure of the Turing degrees and the lattice
Lattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
of recursively enumerable set
Recursively enumerable set
In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing-recognizable if:...
s.
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
Hyperarithmetical theory
In recursion theory, hyperarithmetic theory is a generalization of Turing computability. It has close connections with definability in second-order arithmetic and with weak systems of set theory such as Kripke–Platek set theory...
and α-recursion theory
Alpha recursion theory
In recursion theory, α recursion theory is a generalisation of recursion theory to subsets of admissible ordinals \alpha. An admissible ordinal is closed under \Sigma_1 functions. Admissible ordinals are models of Kripke–Platek set theory. In what follows \alpha is considered to be fixed.The...
.
Contemporary research in recursion theory includes the study of applications such as algorithmic randomness, computable model theory
Computable model theory
Computable model theory is a branch of model theory which deals with questions of computability as they apply to model-theoretical structures. It was developed almost simultaneously by mathematicians in the West, primarily located in the United States and Australia, and Soviet Russia during the...
, and reverse mathematics
Reverse mathematics
Reverse mathematics is a program in mathematical logic that seeks to determine which axioms are required to prove theorems of mathematics. Its defining method can briefly be described as "going backwards from the theorems to the axioms", in contrast to the ordinary mathematical practice of...
, as well as new results in pure recursion theory.
Algorithmically unsolvable problems
An important subfield of recursion theory studies algorithmic unsolvability; a decision problemDecision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
or function problem
Function problem
In computational complexity theory, a function problem is a computational problem where a single output is expected for every input, but the output is more complex than that of a decision problem, that is, it isn't just YES or NO...
is algorithmically unsolvable if there is no possible computable algorithm which 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
Entscheidungsproblem
In mathematics, the is a challenge posed by David Hilbert in 1928. The asks for an algorithm that will take as input a description of a formal language and a mathematical statement in the language and produce as output either "True" or "False" according to whether the statement is true or false...
is algorithmically unsolvable. Turing proved this by establishing the unsolvability of the halting problem
Halting problem
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...
, 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
Word problem for groups
In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group G is the algorithmic problem of deciding whether two words in the generators represent the same element...
was proved algorithmically unsolvable by Pyotr Novikov in 1955 and independently by W. Boone in 1959. The busy beaver
Busy beaver
In computability theory, a busy beaver is a Turing machine that attains the maximum "operational busyness" among all the Turing machines in a certain class...
problem, developed by Tibor Radó
Tibor Radó
Tibor Radó was a Hungarian mathematician who moved to the USA after World War I. He was born in Budapest and between 1913 and 1915 attended the Polytechnic Institute. In World War I, he became a First Lieutenant in the Hungarian Army and was captured on the Russian Front...
in 1962, is another well-known example.
Hilbert's tenth problem
Hilbert's tenth problem
Hilbert's tenth problem is the tenth on the list of Hilbert's problems of 1900. Its statement is as follows:Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined in a finite...
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
Julia Robinson
Julia Hall Bowman Robinson was an American mathematician best known for her work on decision problems and Hilbert's Tenth Problem.-Background and education:...
, Martin Davis
Martin Davis
Martin David Davis, is an American mathematician, known for his work on Hilbert's tenth problem . He received his Ph.D. from Princeton University in 1950, where his adviser was Alonzo Church . He is Professor Emeritus at New York University. He is the co-inventor of the Davis-Putnam and the DPLL...
and Hilary Putnam
Hilary Putnam
Hilary Whitehall Putnam is an American philosopher, mathematician and computer scientist, who has been a central figure in analytic philosophy since the 1960s, especially in philosophy of mind, philosophy of language, philosophy of mathematics, and philosophy of science...
. The algorithmic unsolvability of the problem was proved by Yuri Matiyasevich
Yuri Matiyasevich
Yuri Vladimirovich Matiyasevich, is a Russian mathematician and computer scientist. He is best known for his negative solution of Hilbert's tenth problem, presented in his doctoral thesis, at LOMI .- Biography :* In 1962-1963 studied at Saint Petersburg Lyceum 239...
in 1970 (Davis 1973).
Proof theory and constructive mathematics
Proof theoryProof theory
Proof theory is a branch of mathematical logic that represents proofs as formal mathematical objects, facilitating their analysis by mathematical techniques. Proofs are typically presented as inductively-defined data structures such as plain lists, boxed lists, or trees, which are constructed...
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 system
Hilbert-style deduction system
In logic, especially mathematical logic, a Hilbert system, sometimes called Hilbert calculus or Hilbert–Ackermann system, is a type of system of formal deduction attributed to Gottlob Frege and David Hilbert...
s, systems of natural deduction
Natural deduction
In logic and proof theory, natural deduction is a kind of proof calculus in which logical reasoning is expressed by inference rules closely related to the "natural" way of reasoning...
, and the sequent calculus
Sequent calculus
In proof theory and mathematical logic, sequent calculus is a family of formal systems sharing a certain style of inference and certain formal properties. The first sequent calculi, systems LK and LJ, were introduced by Gerhard Gentzen in 1934 as a tool for studying natural deduction in...
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
Hermann Weyl
Hermann Klaus Hugo Weyl was a German mathematician and theoretical physicist. Although much of his working life was spent in Zürich, Switzerland and then Princeton, he is associated with the University of Göttingen tradition of mathematics, represented by David Hilbert and Hermann Minkowski.His...
, 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
Gödel–Gentzen negative translation
In proof theory, the Gödel–Gentzen negative translation is a method for embedding classical first-order logic into intuitionistic first-order logic. It is one of a number of double-negation translations that are of importance to the metatheory of intuitionistic logic...
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
Proof mining
In proof theory, a branch of mathematical logic, proof mining is a research program that analyzes formalized proofs, especially in analysis, to obtain explicit bounds or rates of convergence from proofs that, when expressed in natural language, appear to be nonconstructive.This research has led to...
by Ulrich Kohlenbach
Ulrich Kohlenbach
Ulrich Wilhelm Kohlenbach is a German professor of mathematics and a researcher in logic. He graduated from Lessing-Gymnasium in 1980 and completed his studies of mathematics, philosophy, and linguistics with a master degree from the University of Frankfurt. In 1990, he received his Ph.D. under...
and the study of proof-theoretic ordinals by Michael Rathjen.
Connections with computer science
The study of computability theory in computer scienceComputability theory (computer science)
Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within 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
Model theory
In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....
, as is program verification (in particular, model checking
Model checking
In computer science, model checking refers to the following problem:Given a model of a system, test automatically whether this model meets a given specification....
). The Curry–Howard isomorphism between proofs and programs relates to proof theory
Proof theory
Proof theory is a branch of mathematical logic that represents proofs as formal mathematical objects, facilitating their analysis by mathematical techniques. Proofs are typically presented as inductively-defined data structures such as plain lists, boxed lists, or trees, which are constructed...
, especially intuitionistic logic
Intuitionistic logic
Intuitionistic logic, or constructive logic, is a symbolic logic system differing from classical logic in its definition of the meaning of a statement being true. In classical logic, all well-formed statements are assumed to be either true or false, even if we do not have a proof of either...
. Formal calculi such as the lambda calculus
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
and combinatory logic
Combinatory logic
Combinatory logic is a notation introduced by Moses Schönfinkel and Haskell Curry to eliminate the need for variables in mathematical logic. It has more recently been used in computer science as a theoretical model of computation and also as a basis for the design of functional programming...
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
Automated theorem proving
Automated theorem proving or automated deduction, currently the most well-developed subfield of automated reasoning , is the proving of mathematical theorems by a computer program.- Decidability of the problem :...
and logic programming
Logic programming
Logic programming is, in its broadest sense, the use of mathematical logic for computer programming. In this view of logic programming, which can be traced at least as far back as John McCarthy's [1958] advice-taker proposal, logic is used as a purely declarative representation language, and a...
.
Descriptive complexity theory relates logics to computational complexity
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...
. The first significant result in this area, Fagin's theorem
Fagin's theorem
Fagin's theorem is a result in descriptive complexity theory that states that the set of all properties expressible in existential second-order logic is precisely the complexity class NP...
(1974) established that NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
is precisely the set of languages expressible by sentences of existential second-order logic
Second-order logic
In logic and mathematics second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory....
.
Foundations of mathematics
In the 19th century, mathematicians became aware of logical gaps and inconsistencies in their field. It was shown that EuclidEuclid
Euclid , fl. 300 BC, also known as Euclid of Alexandria, was a Greek mathematician, often referred to as the "Father of Geometry". He was active in Alexandria during the reign of Ptolemy I...
's axioms for geometry, which had been taught for centuries as an example of the axiomatic method, were incomplete. The use of infinitesimal
Infinitesimal
Infinitesimals have been used to express the idea of objects so small that there is no way to see them or to measure them. The word infinitesimal comes from a 17th century Modern Latin coinage infinitesimus, which originally referred to the "infinite-th" item in a series.In common speech, an...
s, and the very definition of function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
, 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
Leopold Kronecker
Leopold Kronecker was a German mathematician who worked on number theory and algebra.He criticized Cantor's work on set theory, and was quoted by as having said, "God made integers; all else is the work of man"...
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
David Hilbert
David Hilbert was a German mathematician. He is recognized as one of the most influential and universal mathematicians of the 19th and early 20th centuries. Hilbert discovered and developed a broad range of fundamental ideas in many areas, including invariant theory and the axiomatization of...
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
Non-Euclidean geometry
Non-Euclidean geometry is the term used to refer to two specific geometries which are, loosely speaking, obtained by negating the Euclidean parallel postulate, namely hyperbolic and elliptic geometry. This is one term which, for historical reasons, has a meaning in mathematics which is much...
can be proved consistent by defining point to mean a point on a fixed sphere and line to mean a great circle
Great circle
A great circle, also known as a Riemannian circle, of a sphere is the intersection of the sphere and a plane which passes through the center point of the sphere, as opposed to a general circle of a sphere where the plane is not required to pass through the center...
on the sphere. The resulting structure, a model of elliptic geometry
Elliptic geometry
Elliptic geometry is a non-Euclidean geometry, in which, given a line L and a point p outside L, there exists no line parallel to L passing through p. Elliptic geometry, like hyperbolic geometry, violates Euclid's parallel postulate, which can be interpreted as asserting that there is exactly one...
, 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
Proof theory
Proof theory is a branch of mathematical logic that represents proofs as formal mathematical objects, facilitating their analysis by mathematical techniques. Proofs are typically presented as inductively-defined data structures such as plain lists, boxed lists, or trees, which are constructed...
. 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
Hilbert's program
In mathematics, Hilbert's program, formulated by German mathematician David Hilbert, was a proposed solution to the foundational crisis of mathematics, when early attempts to clarify the foundations of mathematics were found to suffer from paradoxes and inconsistencies...
, 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
Transfinite induction
Transfinite induction is an extension of mathematical induction to well-ordered sets, for instance to sets of ordinal numbers or cardinal numbers.- Transfinite induction :Let P be a property defined for all ordinals α...
, and the techniques he developed to so do 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
Mathematical analysis
Mathematical analysis, which mathematicians refer to simply as analysis, has its beginnings in the rigorous formulation of infinitesimal calculus. It is a branch of pure mathematics that includes the theories of differentiation, integration and measure, limits, infinite series, and analytic functions...
). 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
Luitzen Egbertus Jan Brouwer
Luitzen Egbertus Jan Brouwer FRS , usually cited as L. E. J. Brouwer but known to his friends as Bertus, was a Dutch mathematician and philosopher, a graduate of the University of Amsterdam, who worked in topology, set theory, measure theory and complex analysis.-Biography:Early in his career,...
founded intuitionism
Intuitionism
In the philosophy of mathematics, intuitionism, or neointuitionism , is an approach to mathematics as the constructive mental activity of humans. That is, mathematics does not consist of analytic activities wherein deep properties of existence are revealed and applied...
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
BHK interpretation
In mathematical logic, the Brouwer–Heyting–Kolmogorov interpretation, or BHK interpretation, of intuitionistic logic was proposed by L. E. J. Brouwer, Arend Heyting and independently by Andrey Kolmogorov...
and Kripke models, intuitionism became easier to reconcile with classical mathematics.
See also
- List of mathematical logic topics
- List of computability and complexity topics
- List of set theory topics
- List of first-order theories
- Knowledge representationKnowledge representationKnowledge representation is an area of artificial intelligence research aimed at representing knowledge in symbols to facilitate inferencing from those knowledge elements, creating new elements of knowledge...
- MetalogicMetalogicMetalogic is the study of the metatheory of logic. While logic is the study of the manner in which logical systems can be used to decide the correctness of arguments, metalogic studies the properties of the logical systems themselves...
- Logic symbols
Undergraduate texts
........- Shawn Hedman, A first course in logic: an introduction to model theory, proof theory, computability, and complexity, Oxford University Press, 2004, ISBN 0198529813. Covers logics in close reation with computability theoryComputability theoryComputability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
and complexity theoryComputational complexity theoryComputational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
Research papers, monographs, texts, and surveys
., reprinted as an appendix in Martin Davis, Computability and Unsolvability, Dover reprint 1982. JStor. JSTOR. JStor, to appear. Electronic posting by the journal..... PDFClassical papers, texts, and collections
, reprinted in van Heijenoort 1976, pp. 104–111.. English translation of title: "Consistency and irrational numbers". Two English translations:-
- 1963 (1901). Essays on the Theory of Numbers. Beman, W. W., ed. and trans. Dover.
- 1996. In From Kant to Hilbert: A Source Book in the Foundations of Mathematics, 2 vols, Ewald, William B., ed., Oxford University PressOxford University PressOxford University Press is the largest university press in the world. It is a department of the University of Oxford and is governed by a group of 15 academics appointed by the Vice-Chancellor known as the Delegates of the Press. They are headed by the Secretary to the Delegates, who serves as...
: 787–832. (German), reprinted in English translation as "The notion of 'definite' and the independence of the axiom of choice", van Heijenoort 1976, pp. 284–289.
- Frege Gottlob (1879), BegriffsschriftBegriffsschriftBegriffsschrift is a book on logic by Gottlob Frege, published in 1879, and the formal system set out in that book...
, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens. Halle a. S.: Louis Nebert. Translation: Concept Script, a formal language of pure thought modelled upon that of arithmetic, by S. Bauer-Mengelberg in Jean Van HeijenoortJean Van HeijenoortJean Louis Maxime van Heijenoort was a pioneer historian of mathematical logic. He was also a personal secretary to Leon Trotsky from 1932 to 1939, and from then until 1947, an American Trotskyist activist.-Life:Van Heijenoort was born in Creil, France...
, ed., 1967. From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931. Harvard University Press. - Frege Gottlob (1884), Die Grundlagen der Arithmetik: eine logisch-mathematische Untersuchung über den Begriff der Zahl. Breslau: W. Koebner. Translation: J. L. AustinJ. L. AustinJohn Langshaw Austin was a British philosopher of language, born in Lancaster and educated at Shrewsbury School and Balliol College, Oxford University. Austin is widely associated with the concept of the speech act and the idea that speech is itself a form of action...
, 1974. The Foundations of Arithmetic: A logico-mathematical enquiry into the concept of number, 2nd ed. Blackwell.
, reprinted in English translation in Gentzen's Collected works, M. E. Szabo, ed., North-Holland, Amsterdam, 1969.. English translation of title: "Completeness of the logical calculus".. English translation of title: "The completeness of the axioms of the calculus of logical functions"., see On Formally Undecidable Propositions of Principia Mathematica and Related Systems
On Formally Undecidable Propositions of Principia Mathematica and Related Systems
Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I is a paper in mathematical logic by Kurt Gödel...
for details on English translations., reprinted in English translation in Gödel's Collected Works, vol II, Soloman Feferman et al., eds. Oxford University Press, 1990., English 1902 edition (The Foundations of Geometry) republished 1980, Open Court, Chicago.. Lecture given at the International Congress of Mathematicians, 3 September 1928. Published in English translation as "The Grounding of Elementary Number Theory", in Mancosu 1998, pp. 266–273.. (German). Reprinted in English translation as "Geometric Investigations on the Theory of Parallel Lines" in Non-Euclidean Geometry, Robert Bonola (ed.), Dover, 1955. ISBN 0486600270 (German). Translated as "On possibilities in the calculus of relatives" in Jean van Heijenoort
Jean Van Heijenoort
Jean Louis Maxime van Heijenoort was a pioneer historian of mathematical logic. He was also a personal secretary to Leon Trotsky from 1932 to 1939, and from then until 1947, an American Trotskyist activist.-Life:Van Heijenoort was born in Creil, France...
, 1967. A Source Book in Mathematical Logic, 1879–1931. Harvard Univ. Press: 228–251... (Italian), excerpt reprinted in English stranslation as "The principles of arithmetic, presented by a new method", van Heijenoort 1976, pp. 83 97. (French), reprinted in English translation as "The principles of mathematics and the problems of sets", van Heijenoort 1976, pp. 142–144.. (German), reprinted in English translation as "Proof that every set can be well-ordered", van Heijenoort 1976, pp. 139–141. (German), reprinted in English translation as "A new proof of the possibility of a well-ordering", van Heijenoort 1976, pp. 183–198..
External links
- Mathematical Logic around the world
- Polyvalued logic
- forall x: an introduction to formal logic, by P.D. Magnus, is a free textbook.
- A Problem Course in Mathematical Logic, by Stefan Bilaniuk, is another free textbook.
- Detlovs, Vilnis, and Podnieks, Karlis (University of Latvia) Introduction to Mathematical Logic. A hyper-textbook.
- Stanford Encyclopedia of PhilosophyStanford Encyclopedia of PhilosophyThe Stanford Encyclopedia of Philosophy is a freely-accessible online encyclopedia of philosophy maintained by Stanford University. Each entry is written and maintained by an expert in the field, including professors from over 65 academic institutions worldwide...
: Classical Logic – by Stewart ShapiroStewart ShapiroStewart Shapiro is O'Donnell Professor of Philosophy at the Ohio State University and a regular visiting professor at the University of St Andrews in Scotland. He is an important contemporary figure in the philosophy of mathematics where he defends a version of structuralism. He studied...
. - Stanford Encyclopedia of Philosophy: First-order Model Theory – by Wilfrid HodgesWilfrid HodgesWilfrid Augustine Hodges is a British mathematician, known for his work in model theory. He was Professor of Mathematics at Queen Mary, University of London from 1987 to 2006, and is the author of numerous books on logic....
. - The London Philosophy Study Guide offers many suggestions on what to read, depending on the student's familiarity with the subject: