Mathematical logic is the study offormal logic withinmathematics. Major subareas includemodel theory,proof theory,set theory, andrecursion theory (also known as computability theory). Research in mathematical logic commonly addresses the mathematical properties of formal systems of logic such as their expressive or deductive power. However, it can also include uses of logic to characterize correct mathematical reasoning or to establishfoundations of mathematics.
Since its inception, mathematical logic has both contributed to and been motivated by the study of foundations of mathematics. This study began in the late 19th century with the development ofaxiomatic frameworks forgeometry,arithmetic, andanalysis. In the early 20th century it was shaped byDavid Hilbert'sprogram to prove the consistency of foundational theories. Results ofKurt Gödel,Gerhard Gentzen, and others provided partial resolution to the program, and clarified the issues involved in proving consistency. Work in set theory showed that almost all ordinary mathematics can be formalized in terms of sets, although there are some theorems that cannot be proven in common axiom systems for set theory. Contemporary work in the foundations of mathematics often focuses on establishing which parts of mathematics can be formalized in particular formal systems (as inreverse mathematics) rather than trying to find theories in which all of mathematics can be developed.
Additionally, sometimes the field ofcomputational complexity theory is also included together with mathematical logic.[2][3] Each area has a distinct focus, although many techniques and results are shared among multiple areas. The borderlines amongst these fields, and the lines separating mathematical logic and other fields of mathematics, are not always sharp.Gödel's incompleteness theorem marks not only a milestone in recursion theory and proof theory, but has also led toLöb's theorem in modal logic. The method offorcing is employed in set theory, model theory, and recursion theory, as well as in the study of intuitionistic mathematics.
The mathematical field ofcategory theory uses many formal axiomatic methods, and includes the study ofcategorical logic, but category theory is not ordinarily considered a subfield of mathematical logic. Because of its applicability in diverse fields of mathematics, mathematicians includingSaunders Mac Lane have proposed category theory as a foundational system for mathematics, independent of set theory. These foundations usetoposes, which resemble generalized models of set theory that may employ classical or nonclassical logic.
Mathematical logic emerged in the mid-19th century as a subfield of mathematics, reflecting the confluence of two traditions: formal philosophical logic and mathematics.[4] Mathematical logic, also called 'logistic', 'symbolic logic', the 'algebra of logic', and, more recently, simply 'formal logic', is the set of logical theories elaborated in the course of the nineteenth century with the aid of an artificial notation and a rigorously deductive method.[5] Before this emergence, logic was studied withrhetoric, withcalculationes,[6] through thesyllogism, and withphilosophy. The first half of the 20th century saw an explosion of fundamental results, accompanied by vigorous debate over the foundations of mathematics.
Theories of logic were developed in many cultures in history, including in ancientChina,India,Greece,Roman empire and theIslamic world. Greek methods, particularlyAristotelian logic (or term logic) as found in theOrganon, found wide application and acceptance in Western science and mathematics for millennia.[7] TheStoics, especiallyChrysippus, began the development ofpropositional logic. In 18th-century Europe, attempts to treat the operations of formal logic in a symbolic or algebraic way had been made by philosophical mathematicians includingLeibniz andLambert, but their labors remained isolated and little known.
In the middle of the nineteenth century,George Boole and thenAugustus De Morgan presented systematic mathematical treatments of logic. Their work, building on work by algebraists such asGeorge Peacock, extended the traditional Aristotelian doctrine of logic into a sufficient framework for the study offoundations of mathematics.[8] In 1847,Vatroslav Bertić made substantial work on algebraization of logic, independently from Boole.[9]Charles Sanders Peirce later built upon the work of Boole to develop a logical system for relations and quantifiers, which he published in several papers from 1870 to 1885.
Gottlob Frege presented an independent development of logic with quantifiers in hisBegriffsschrift, published in 1879, a work generally considered as marking a turning point in the history of logic. Frege's work remained obscure, however, untilBertrand 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 publishedVorlesungen ü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.
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 termarithmetic refers to the theory of thenatural numbers.Giuseppe Peano[10] 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 timeRichard Dedekind showed that the natural numbers are uniquely characterized by theirinduction properties. Dedekind proposed a different characterization, which lacked the formal logical character of Peano's axioms.[11] 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 thesuccessor function and mathematical induction.
In the mid-19th century, flaws in Euclid's axioms for geometry became known.[12] In addition to the independence of theparallel postulate, established byNikolai Lobachevsky in 1826,[13] 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[14] developed a complete set ofaxioms for geometry, building onprevious work by Pasch.[15] The success in axiomatizing geometry motivated Hilbert to seek complete axiomatizations of other areas of mathematics, such as the natural numbers and thereal 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 ofreal analysis, including theories of convergence of functions andFourier series. Mathematicians such asKarl Weierstrass began to construct functions that stretched intuition, such asnowhere-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 thearithmetization of analysis, which sought to axiomatize analysis using properties of the natural numbers. The modern(ε, δ)-definition of limit andcontinuous functions was already developed byBolzano in 1817,[16] but remained relatively unknown.Cauchy in 1821 defined continuity in terms ofinfinitesimals (see Cours d'Analyse, page 34). In 1858, Dedekind proposed a definition of the real numbers in terms ofDedekind cuts of rational numbers, a definition still employed in contemporary texts.[17]
Georg Cantor developed the fundamental concepts of infinite set theory. His early results developed the theory ofcardinality andproved that the reals and the natural numbers have different cardinalities.[18] Over the next twenty years, Cantor developed a theory oftransfinite numbers in a series of publications. In 1891, he published a new proof of the uncountability of the real numbers that introduced thediagonal argument, and used this method to proveCantor's theorem that no set can have the same cardinality as itspowerset. Cantor believed that every set could bewell-ordered, but was unable to produce a proof for this result, leaving it as an open problem in 1895.[19]
In the early decades of the 20th century, the main areas of study were set theory and formal logic. The discovery of paradoxes in informal set theory caused some to wonder whether mathematics itself is inconsistent, and to look for proofs of consistency.
In 1900,Hilbert posed a famous list of23 problems for the next century. The first two of these were to resolve thecontinuum 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 theintegers has a solution. Subsequent work to resolve these problems shaped the direction of mathematical logic, as did the effort to resolve Hilbert'sEntscheidungsproblem, posed in 1928. This problem asked for a procedure that would decide, given a formalized mathematical statement, whether the statement is true or false.
Ernst Zermelo gave a proof thatevery set could be well-ordered, a resultGeorg Cantor had been unable to obtain.[20] To achieve the proof, Zermelo introduced theaxiom 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.[21] This paper led to the general acceptance of the axiom of choice in the mathematics community.
In 1910, the first volume ofPrincipia Mathematica by Russell andAlfred North Whitehead was published. This seminal work developed the theory of functions and cardinality in a completely formal framework oftype 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.[25]
Fraenkel[26] proved that the axiom of choice cannot be proved from the axioms of Zermelo's set theory withurelements. Later work byPaul Cohen[27] showed that the addition of urelements is not needed, and the axiom of choice is unprovable in ZF. Cohen's proof developed the method offorcing, which is now an important tool for establishingindependence results in set theory.[28]
In his doctoral thesis,Kurt Gödel proved thecompleteness theorem, which establishes a correspondence between syntax and semantics in first-order logic.[31] Gödel used the completeness theorem to prove thecompactness theorem, demonstrating the finitary nature of first-orderlogical consequence. These results helped establish first-order logic as the dominant logic used by mathematicians.
In 1931, Gödel publishedOn 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 asGö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.[a]
Gödel's theorem shows that aconsistency proof of any sufficiently strong, effective axiom system cannot be obtained in the system itself, if the system is consistent, nor in any weaker system. This leaves open the possibility of consistency proofs that cannot be formalized within the system they consider. Gentzen proved the consistency of arithmetic using a finitistic system together with a principle oftransfinite induction.[32] Gentzen's result introduced the ideas ofcut elimination andproof-theoretic ordinals, which became key tools in proof theory. Gödel gave a different consistency proof, which reduces the consistency of classical arithmetic to that of intuitionistic arithmetic in higher types.[33]
Beginning in 1935, a group of prominent mathematicians collaborated under the pseudonymNicolas Bourbaki to publishÉléments de mathématique, a series of encyclopedic mathematics texts. These texts, written in an austere and axiomatic style, emphasized rigorous presentation and set-theoretic foundations. Terminology coined by these texts, such as the wordsbijection,injection, andsurjection, and the set-theoretic foundations the texts employed, were widely adopted throughout mathematics.
The study of computability came to be known as recursion theory orcomputability theory, because early formalizations by Gödel and Kleene relied on recursive definitions of functions.[b] When these definitions were shown equivalent to Turing's formalization involvingTuring machines, it became clear that a new concept – thecomputable 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 byStephen Cole Kleene andEmil Leon Post. Kleene[36] introduced the concepts of relative computability, foreshadowed by Turing,[37] and thearithmetical hierarchy. Kleene later generalized recursion theory to higher-order functionals. Kleene andGeorg Kreisel studied formal versions of intuitionistic mathematics, particularly in the context of proof theory.
Early results from formal logic established limitations of first-order logic. TheLö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 toisomorphism. 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 established the equivalence between semantic and syntactic definitions oflogical consequence in first-order logic.[31] 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. Thecompactness 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 ofmodel theory, and they are a key reason for the prominence of first-order logic in mathematics.
Gödel's incompleteness theorems establish additional limits on first-order axiomatizations.[38] Thefirst incompleteness theorem states that for any consistent, effectively given (defined below) logical system that is capable of interpreting arithmetic, there exists a statement that is true (in the sense that it holds for the natural numbers) but not provable within that logical system (and which indeed may fail in somenon-standard models of arithmetic which may be consistent with the logical system). For example, in every logical system capable of expressing thePeano axioms, the Gödel sentence holds for the natural numbers but cannot be proved.
Here a logical system is said to be effectively given if it is possible to decide, given any formula in the language of the system, whether the formula is an axiom, and one which can express the Peano axioms is called "sufficiently strong." When applied to first-order logic, the first incompleteness theorem implies that any sufficiently strong, consistent, effective first-order theory has models that are notelementarily equivalent, a stronger limitation than the one established by the Löwenheim–Skolem theorem. Thesecond incompleteness theorem states that no sufficiently strong, consistent, effective axiom system for arithmetic can prove its own consistency, which has been interpreted to show thatHilbert's program cannot be reached.
Many logics besides first-order logic are studied. These includeinfinitary logics, which allow for formulas to provide an infinite amount of information, andhigher-order logics, 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 thedomain 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.
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 orfuzzy logic.
Modal logics include additional modal operators, such as an operator which states that a particular formula is not only true, but necessarily true. Although modal logic is not often used to axiomatize mathematics, it has been used to study the properties of first-order provability[39] and set-theoretic forcing.[40]
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 thelaw 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 iscomputable; this is not true in classical theories of arithmetic such asPeano arithmetic.
Algebraic logic uses the methods ofabstract algebra to study the semantics of formal logics. A fundamental example is the use ofBoolean algebras to representtruth values in classical propositional logic, and the use ofHeyting algebras to represent truth values in intuitionistic propositional logic. Stronger logics, such as first-order logic and higher-order logic, are studied using more complicated algebraic structures such ascylindric algebras.
Set theory is the study ofsets, 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. Thefirst such axiomatization, due to Zermelo,[24] was extended slightly to becomeZermelo–Fraenkel set theory (ZF), which is now the most widely used foundational theory for mathematics.
Other formalizations of set theory have been proposed, includingvon Neumann–Bernays–Gödel set theory (NBG),Morse–Kelley set theory (MK), andNew Foundations (NF). Of these, ZF, NBG, and MK are similar in describing acumulative 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 ofKripke–Platek set theory is closely related to generalized recursion theory.
Two famous statements in set theory are theaxiom of choice and thecontinuum hypothesis. The axiom of choice, first stated by Zermelo,[20] was proved independent of ZF by Fraenkel,[26] but has come to be widely accepted by mathematicians. It states that given a collection of nonempty sets there is a single setC that contains exactly one element from each set in the collection. The setC 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 andAlfred Tarski 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.[41] This theorem, known as theBanach–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 byDavid 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 theconstructible 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.[27] 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 byW. Hugh Woodin, although its importance is not yet clear.[42]
Contemporary research in set theory includes the study oflarge cardinals anddeterminacy. Large cardinals arecardinal 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, aninaccessible cardinal, already implies the consistency of ZFC. Despite the fact that large cardinals have extremely highcardinality, 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 bedetermined). The existence of these strategies implies structural properties of the real line and otherPolish spaces.
Model theory studies the models of various formal theories. Here atheory is a set of formulas in a particular formal logic andsignature, while amodel is a structure that gives a concrete interpretation of the theory. Model theory is closely related touniversal algebra andalgebraic 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 anelementary 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 ofquantifier elimination can be used to show that definable sets in particular theories cannot be too complicated. Tarski established quantifier elimination forreal-closed fields, a result which also shows the theory of the field of real numbers isdecidable.[43] He also noted that his methods were equally applicable to algebraically closed fields of arbitrary characteristic. A modern subfield developing from this is concerned witho-minimal structures.
Morley's categoricity theorem, proved byMichael D. Morley,[44] 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 thecontinuum hypothesis is that a complete theory with less than continuum many nonisomorphic countable models can have only countably many.Vaught's conjecture, named afterRobert Lawson Vaught, says that this is true even independently of the continuum hypothesis. Many special cases of this conjecture have been established.
Recursion theory, also calledcomputability theory, studies the properties ofcomputable functions and theTuring degrees, which divide the uncomputable functions into sets that have the same level of uncomputability. Recursion theory also includes the study of generalized computability and definability. Recursion theory grew from the work ofRózsa Péter,Alonzo Church andAlan Turing in the 1930s, which was greatly extended byKleene andPost in the 1940s.[45]
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 usingTuring machines,λ calculus, and other systems. More advanced results concern the structure of the Turing degrees and thelattice ofrecursively enumerable sets.
Generalized recursion theory extends the ideas of recursion theory to computations that are no longer necessarily finite. It includes the study of computability in higher types as well as areas such ashyperarithmetical theory andα-recursion theory.
An important subfield of recursion theory studies algorithmic unsolvability; adecision problem orfunction problem isalgorithmically unsolvable if there is no possible computable algorithm that returns the correct answer for all legal inputs to the problem. The first results about unsolvability, obtained independently by Church and Turing in 1936, showed that theEntscheidungsproblem is algorithmically unsolvable. Turing proved this by establishing the unsolvability of thehalting 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. Theword problem for groups was proved algorithmically unsolvable byPyotr Novikov in 1955 and independently by W. Boone in 1959. Thebusy beaver problem, developed byTibor Radó in 1962, is another well-known example.
Proof theory is the study of formal proofs in various logical deduction systems. These proofs are represented as formal mathematical objects, facilitating their analysis by mathematical techniques. Several deduction systems are commonly considered, includingHilbert-style deduction systems, systems ofnatural deduction, and thesequent calculus developed by Gentzen.
The study ofconstructive 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 ofpredicative systems. An early proponent of predicativism wasHermann Weyl, who showed it is possible to develop a large part of real analysis using only predicative methods.[47]
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 theGödel–Gentzen negative translation show that it is possible to embed (ortranslate) classical logic into intuitionistic logic, allowing some properties about intuitionistic proofs to be transferred back to classical proofs.
The study ofcomputability theory in computer science is closely related to the study of computability in mathematical logic. There is a difference of emphasis, however.Computer scientists often focus on concrete programming languages andfeasible computability, while researchers in mathematical logic often focus on computability as a theoretical concept and on noncomputability.
Computer science also contributes to mathematics by developing techniques for the automatic checking or even finding of proofs, such asautomated theorem proving andlogic programming.
In the 19th century, mathematicians became aware of logical gaps and inconsistencies in their field. It was shown thatEuclid's axioms for geometry, which had been taught for centuries as an example of the axiomatic method, were incomplete. The use ofinfinitesimals, and the very definition offunction, 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 definingpoint to mean a point on a fixed sphere andline to mean agreat circle on the sphere. The resulting structure, a model ofelliptic 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 ofproof theory. Moreover, Hilbert proposed that the analysis should be entirely concrete, using the termfinitary to refer to the methods he would allow but not precisely defining them. This project, known asHilbert'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 oftransfinite induction, and the techniques he developed to do so were seminal in proof theory.
A second thread in the history of foundations of mathematics involvesnonclassical logics andconstructive mathematics. The study of constructive mathematics includes many different programs with various definitions ofconstructive. 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 tonatural numbers,number-theoretic functions, and sets of natural numbers (which can be used to represent real numbers, facilitating the study ofmathematical 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 foundedintuitionism as a part ofphilosophy 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 tointuit 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 thelaw 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. Kleene and Kreisel would later study formalized versions of intuitionistic logic (Brouwer rejected formalization, and presented his work in unformalized natural language). With the advent of theBHK interpretation andKripke models, intuitionism became easier to reconcile with classical mathematics.
^In the foreword to the 1934 first edition of "Grundlagen der Mathematik" (Hilbert & Bernays 1934), Bernays wrote the following, which is reminiscent of the famous note byFrege when informed of Russell's paradox.
"Die Ausführung dieses Vorhabens hat eine wesentliche Verzögerung dadurch erfahren, daß in einem Stadium, in dem die Darstellung schon ihrem Abschuß nahe war, durch das Erscheinen der Arbeiten von Herbrand und von Gödel eine veränderte Situation im Gebiet der Beweistheorie entstand, welche die Berücksichtigung neuer Einsichten zur Aufgabe machte. Dabei ist der Umfang des Buches angewachsen, so daß eine Teilung in zwei Bände angezeigt erschien."
Translation:
"Carrying out this plan [by Hilbert for an exposition on proof theory for mathematical logic] has experienced an essential delay because, at the stage at which the exposition was already near to its conclusion, there occurred an altered situation in the area of proof theory due to the appearance of works by Herbrand and Gödel, which necessitated the consideration of new insights. Thus the scope of this book has grown, so that a division into two volumes seemed advisable."
So certainly Hilbert was aware of the importance of Gödel's work by 1934. The second volume in 1939 included a form of Gentzen's consistency proof for arithmetic.
^A detailed study of this terminology is given bySoare 1996.
^Ferreirós 2001 surveys the rise of first-order logic over other formal logics in the early 20th century.
Fisher, Alec (1982).Formal Number Theory and Computability: A Workbook. (suitable as a first course for independent study) (1st ed.). Oxford University Press.ISBN978-0-19-853188-3.
Hamilton, A.G. (1988).Logic for Mathematicians (2nd ed.). Cambridge University Press.ISBN978-0-521-36865-0.
Hinman, Peter G. (2005).Fundamentals of mathematical logic. A K Peters, Ltd.ISBN1-56881-262-0.
Andrews, Peter B. (2002).An Introduction to Mathematical Logic and Type Theory: To Truth Through Proof (2nd ed.).Boston: Kluwer Academic Publishers.ISBN978-1-4020-0763-7.
Troelstra, Anne Sjerp; Schwichtenberg, Helmut (2000).Basic Proof Theory. Cambridge Tracts in Theoretical Computer Science (2nd ed.). Cambridge University Press.ISBN978-0-521-77911-1.
Dedekind, Richard (1872).Stetigkeit und irrationale Zahlen (in German). English translation as: "Consistency and irrational numbers".
Dedekind, Richard (1888).Was sind und was sollen die Zahlen?. Two English translations:
1963 (1901).Essays on the Theory of Numbers. Beman, W. W., ed. and trans. Dover.
1996. InFrom Kant to Hilbert: A Source Book in the Foundations of Mathematics, 2 vols, Ewald, William B., ed.,Oxford University Press: 787–832.
Fraenkel, Abraham A. (1922). "Der Begriff 'definit' und die Unabhängigkeit des Auswahlsaxioms".Sitzungsberichte der Preussischen Akademie der Wissenschaften, Physikalisch-mathematische Klasse (in German). pp. 253–257. Reprinted in English translation as "The notion of 'definite' and the independence of the axiom of choice" invan Heijenoort 1976, pp. 284–289.
Frege, Gottlob (1879),Begriffsschrift, 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 invan Heijenoort 1976.
Frege, Gottlob (1884),Die Grundlagen der Arithmetik: eine logisch-mathematische Untersuchung über den Begriff der Zahl. Breslau: W. Koebner. Translation:J. L. Austin, 1974.The Foundations of Arithmetic: A logico-mathematical enquiry into the concept of number, 2nd ed. Blackwell.
Gentzen, Gerhard (1936). "Die Widerspruchsfreiheit der reinen Zahlentheorie".Mathematische Annalen.112:132–213.doi:10.1007/BF01565428.S2CID122719892. Reprinted in English translation in Gentzen'sCollected works, M. E. Szabo, ed., North-Holland, Amsterdam, 1969.
Gödel, Kurt (1929).Über die Vollständigkeit des Logikkalküls [Completeness of the logical calculus]. doctoral dissertation. University Of Vienna.
Gödel, Kurt (1930). "Die Vollständigkeit der Axiome des logischen Funktionen-kalküls" [The completeness of the axioms of the calculus of logical functions].Monatshefte für Mathematik und Physik (in German).37:349–360.doi:10.1007/BF01696781.S2CID123343522.
Hilbert, David (1899).Grundlagen der Geometrie (in German).Leipzig: Teubner. English 1902 edition (The Foundations of Geometry) republished 1980, Open Court, Chicago.
Lobachevsky, Nikolai (1840).Geometrishe Untersuchungen zur Theorie der Parellellinien (in German). Reprinted in English translation asRobert Bonola, ed. (1955). "Geometric Investigations on the Theory of Parallel Lines".Non-Euclidean Geometry. Dover.ISBN0-486-60027-0.{{cite book}}:ISBN / Date incompatibility (help)
Richard, Jules (1905). "Les principes des mathématiques et le problème des ensembles".Revue Générale des Sciences Pures et Appliquées (in French).16: 541. Reprinted in English translation as "The principles of mathematics and the problems of sets" invan Heijenoort 1976, pp. 142–144.
Skolem, Thoralf (1920). "Logisch-kombinatorische Untersuchungen über die Erfüllbarkeit oder Beweisbarkeit mathematischer Sätze nebst einem Theoreme über dichte Mengen".Videnskapsselskapet Skrifter, I. Matematisk-naturvidenskabelig Klasse (in German).6:1–36.
Weyl, Hermann (1918).Das Kontinuum. Kritische Untersuchungen über die Grundlagen der Analysis (in German). Leipzig.{{cite book}}: CS1 maint: location missing publisher (link)
