Editing Mathematical logic (section)

==History==
Mathematical logic emerged in the mid-19th century as a subfield of mathematics, reflecting the confluence of two traditions: formal philosophical logic and mathematics.{{sfnp|Ferreirós|2001|p=443}} Mathematical logic, also called 'logistic', 'symbolic logic', the '[[Boolean algebra|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.{{sfnp|Bochenski|1959|loc=Sec. 0.1, p. 1}} Before this emergence, logic was studied with [[rhetoric]], with ''calculationes'',{{sfnp|Swineshead|1498}} through the [[syllogism]], and with [[philosophy]]. The first half of the 20th century saw an explosion of fundamental results, accompanied by vigorous debate over the foundations of mathematics.

=== Early history ===
{{Further|History of logic}}
Theories of logic were developed in many cultures in history, including in ancient [[Logic in China|China]], [[Logic in India|India]], [[Logic in Greece|Greece]], [[Ancient Roman philosophy|Roman empire]] and the [[Logic in Islamic philosophy|Islamic world]]. Greek methods, particularly [[Aristotelian logic]] (or term logic) as found in the ''[[Organon]]'', found wide application and acceptance in Western science and mathematics for millennia.{{sfnp|Boehner|1950|p=xiv}} The [[Stoicism|Stoics]], especially [[Chrysippus]], began the development of [[Propositional calculus|propositional logic]]. In 18th-century Europe, attempts to treat the operations of formal logic in a symbolic or algebraic way had been made by philosophical mathematicians including [[Gottfried Wilhelm Leibniz|Leibniz]] and [[Johann Heinrich Lambert|Lambert]], but their labors remained isolated and little known.

=== 19th century ===
<!-- symbolic logic -->
In the middle of the nineteenth century, [[George Boole]] and then [[Augustus De Morgan]] presented systematic mathematical treatments of logic.  Their work, building on work by algebraists such as [[George Peacock (mathematician)|George Peacock]], extended the traditional Aristotelian doctrine of logic into a sufficient framework for the study of [[foundations of mathematics]].{{sfnp|Katz|1998|p=686}} In 1847, [[Vatroslav Bertić]] made substantial work on algebraization of logic, independently from Boole.<ref>{{Cite web |title=Bertić, Vatroslav |url=https://www.enciklopedija.hr/clanak/bertic-vatroslav |access-date=2023-05-01 |website=www.enciklopedija.hr}}</ref> [[Charles Sanders Peirce]] later built upon the work of Boole to develop a logical system for relations and quantifiers, which he published in several papers from 1870 to 1885.

[[Gottlob Frege]] presented an independent development of logic with quantifiers in his ''[[Begriffsschrift]]'', published in 1879, a work generally considered as marking a turning point in the history of logic. Frege's work remained obscure, however, until [[Bertrand Russell]] began to promote it near the turn of the century.  The two-dimensional notation Frege developed was never widely adopted and is unused in contemporary texts.

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

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

<!-- arithmetic -->
In logic, the term ''arithmetic'' refers to the theory of the [[natural number]]s. [[Giuseppe Peano]]{{sfnp|Peano|1889}} published a set of axioms for arithmetic that came to bear his name ([[Peano axioms]]), using a variation of the logical system of Boole and Schröder but adding quantifiers. Peano was unaware of Frege's work at the time. Around the same time [[Richard Dedekind]] showed that the natural numbers are uniquely characterized by their [[mathematical induction|induction]] properties. Dedekind proposed a different characterization, which lacked the formal logical character of Peano's axioms.{{sfnp|Dedekind|1888}} 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.

<!-- geometry -->
In the mid-19th century, flaws in Euclid's axioms for geometry became known.{{sfnp|Katz|1998|p=774}}  In addition to the independence of the [[parallel postulate]], established by [[Nikolai Lobachevsky]] in 1826,{{sfnp|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{{sfnp|Hilbert|1899}} developed a complete set of [[Hilbert's axioms|axioms for geometry]], building on [[Pasch's axiom|previous work]] by Pasch.{{sfnp|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 [[Continuous, nowhere differentiable function|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 [[Bernard Bolzano|Bolzano]] in 1817,{{sfnp|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, a definition still employed in contemporary texts.{{sfnp|Dedekind|1872}}

[[Georg Cantor]] developed the fundamental concepts of infinite set theory. His early results developed the theory of [[cardinality]] and [[Cantor's first uncountability proof|proved]] that the reals and the natural numbers have different cardinalities.{{sfnp|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 [[Cantor's diagonal argument|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.{{sfnp|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, [[David Hilbert|Hilbert]] posed a famous list of [[Hilbert's problems|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.

==== Set theory and paradoxes ====
[[Ernst Zermelo]] gave a proof that [[Well-ordering theorem|every set could be well-ordered]], a result [[Georg Cantor]] had been unable to obtain.{{sfnp|Zermelo|1904}} 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.{{sfnp|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]]{{sfnp|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 (mathematician)|Jules Richard]]  discovered [[Richard's paradox]].{{sfnp|Richard|1905}}

Zermelo provided the first set of axioms for set theory.{{sfnp|Zermelo|1908b}} 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.{{sfnp|Ferreirós|2001|p=445}}

Fraenkel{{sfnp|Fraenkel|1922}} proved that the axiom of choice cannot be proved from the axioms of Zermelo's set theory with [[urelements]]. Later work by [[Paul Cohen]]{{sfnp|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 (mathematics)|forcing]], which is now an important tool for establishing [[independence result]]s in set theory.<ref>See also {{harvnb|Cohen|2008}}.</ref>

==== Symbolic logic ====
[[Leopold Löwenheim]]{{sfnp|Löwenheim|1915}} and [[Thoralf Skolem]]{{sfnp|Skolem|1920}} obtained the [[Löwenheim–Skolem theorem]], which says that [[first-order logic]] cannot control the [[Cardinal number|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]] [[structure (mathematical logic)|model]]. This counterintuitive fact became known as [[Skolem's paradox]].
[[File:Young Kurt Gödel as a student in 1925.jpg|thumb|Portrait of young [[Kurt Gödel]] as a student in [[Vienna]],1925.]]
In his doctoral thesis, [[Kurt Gödel]] proved the [[completeness theorem]], which establishes a correspondence between syntax and semantics in first-order logic.{{sfnp|Gödel|1929}} 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.{{efn|name=HilbertBernays1934_PlusNote}}

Gödel's theorem shows that a [[consistency]] proof of any sufficiently strong, effective axiom system cannot be obtained in the system itself, if the system is consistent, nor in any weaker system. This leaves open the possibility of consistency proofs that cannot be formalized within the system they consider. Gentzen proved the consistency of arithmetic using a finitistic system together with a principle of [[transfinite induction]].{{sfnp|Gentzen|1936}} Gentzen's result introduced the ideas of [[cut elimination]] and [[proof-theoretic ordinal]]s, 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.{{sfnp|Gödel|1958}}

The first textbook on symbolic logic for the layman was written by [[Lewis Carroll]],<ref>Lewis Carroll: SYMBOLIC LOGIC Part I Elementary. pub. Macmillan 1896. Available online at: https://archive.org/details/symboliclogic00carr</ref> author of ''[[Alice's Adventures in Wonderland]]'', in 1896.{{sfnp|Carroll|1896}}

====Beginnings of the other branches====
[[Alfred Tarski]] developed the basics of [[model theory]].

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

The study of computability came to be known as recursion theory or [[computability theory]], because early formalizations by Gödel and Kleene relied on recursive definitions of functions.{{efn|A detailed study of this terminology is given by {{harvnb|Soare|1996}}.}} When these definitions were shown equivalent to Turing's formalization involving [[Turing machine]]s, it became clear that a new concept &ndash; the [[computable function]] &ndash; 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{{sfnp|Kleene|1943}} introduced the concepts of relative computability, foreshadowed by Turing,{{sfnp|Turing|1939}} and the [[arithmetical hierarchy]]. Kleene later generalized recursion theory to higher-order functionals. Kleene and [[Georg Kreisel]] studied formal versions of intuitionistic mathematics, particularly in the context of proof theory.
<!-- Perhaps it is better to stop this history around 1950 -->