Mathematical logic and foundations Topic
Mathematical logic
Summary
Mathematical logic is the study of formal languages, formal proofs and the meaning of formulas with the methods of mathematics. A formal system has a language, axioms and rules of inference, and a proof in the system is a finite sequence of formulas that obeys these rules. Logic gives precise meanings to the words statement, proof and truth, so it supports the foundations of mathematics, and it has many uses in computer science. Boole and Frege started the modern subject in the 19th century, and the results of Gödel, Tarski, Gentzen and Church in the 1930s gave it its present form. This topic collects the mathematical logic pages of math2. Its sub-areas are listed below, in reading order. Reasoning and proof, model theory, set theory, computability theory, and type theory and constructive mathematics have their own topics.
Remarks
What the area is about
Mathematical logic studies the reasoning of mathematics with the methods of mathematics. Its objects are formal languages, the formal systems that derive formulas of these languages, and the structures in which the formulas are true or false. The area asks what can be expressed in a language, what can be proved in a system, and how proof and truth are related.
Logic has two roles in mathematics. As a branch of mathematics it has its own definitions, theorems and open problems, like algebra or topology. As a foundation it gives the exact meaning of "statement", "proof" and "theorem", and so it tells which arguments the other branches may use.
Logic is traditionally divided into four branches.
- Proof theory studies proofs as finite objects: their structure, their transformations and the strength of theories.
- Model theory studies the relation between theories and the structures that satisfy them.
- Set theory studies sets, the objects from which most of mathematics is built, and the axioms that describe them.
- Computability theory studies which functions and sets an algorithm can compute, and how hard the others are.
The four branches are linked. Gödel's completeness theorem joins proof theory and model theory: a sentence of first-order logic is provable exactly when it is true in every model. The incompleteness theorems join proof theory and computability: a consistent theory with a computable set of axioms that contains enough arithmetic leaves some sentence undecided. Set theory builds new models of its axioms with model-theoretic methods, and computability theory shows that some logics are undecidable. In math2 this area holds proof theory and the logics themselves, and model theory, set theory and computability theory have their own areas.
The main theorems of the area are the following.
- The completeness theorem (Gödel, 1929): first-order provability equals truth in all models.
- The compactness theorem: a set of first-order sentences has a model if each finite subset has a model.
- The incompleteness theorems (Gödel, 1931): a consistent, effectively axiomatized theory that contains enough arithmetic does not decide every sentence, and it does not prove its own consistency.
- Tarski's undefinability theorem: arithmetical truth is not definable in arithmetic.
- Church's theorem (Church and Turing, 1936): validity in first-order logic is undecidable.
- The cut-elimination theorem (Gentzen): each proof in the sequent calculus can be transformed into a proof without the cut rule.
Logic has many uses in computer science. Programs are checked by model checking in modal and temporal logics. The Boolean satisfiability problem was the first problem shown to be NP-complete, and SAT solvers decide large instances of it in practice. The Curry-Howard correspondence identifies proofs with programs, and it is the base of type theory and of proof assistants. Descriptive complexity theory describes complexity classes by the logics that define them.
History
Aristotle gave the first formal logic, the syllogistic, in the 4th century BC, and the Stoics studied the logic of connectives. George Boole treated logic as algebra in 1847 and 1854. Gottlob Frege gave the first formal language with quantifiers in his Begriffsschrift of 1879. Whitehead and Russell derived a large part of mathematics in a formal system in Principia Mathematica (1910 to 1913). In the 1920s David Hilbert proposed his program: formalize mathematics and prove its consistency by finitary means.
The 1930s gave the subject its present form. Gödel proved the completeness theorem in 1929 and the incompleteness theorems in 1931. Alfred Tarski defined truth in a formal language in 1933. Gerhard Gentzen introduced natural deduction and the sequent calculus in 1934 and 1935, and he proved the consistency of arithmetic in 1936. Alonzo Church and Alan Turing showed in 1936 that first-order validity is undecidable.
After 1950 the four branches grew into separate fields. Saul Kripke and others gave a semantics for modal and intuitionistic logic in the late 1950s and the 1960s. Paul Cohen invented forcing in 1963 and proved that the continuum hypothesis does not follow from the axioms of ZFC. The history of mathematical logic gives a longer account.
How to read the area
A reader who is new to logic starts with logic, formal systems and foundations, which gives the general notions, and with propositions, connectives and quantifiers. Then the core course follows, in this order. The propositional calculus treats the logic of connectives completely. First-order languages and syntax, structures, satisfaction and truth and proof systems for first-order logic give the syntax, the semantics and the proofs of first-order logic. Completeness, compactness and interpolation joins the semantics and the proofs.
After the core course the reader can choose among four lines.
- Limits of formal systems: decidability, formal arithmetic, the incompleteness theorems and natural independence results.
- Proof theory: structural proof theory, ordinal analysis, proof interpretations, provability logic, reverse mathematics, bounded arithmetic and proof complexity. This line needs the incompleteness theorems.
- Non-classical logics: modal logic, then correspondence and bisimulation and applied modal logics, and also intuitionistic, many-valued, substructural and other non-classical logics.
- Algebra and truth: algebraic logic and truth and the semantic paradoxes.
Second-order logic and extensions of first-order logic can be read at any time after the core course.
Related areas
Reasoning and proof treats logic as a tool of practice: how to read statements and how to write proofs. Model theory, set theory and computability theory are the other three classical branches of logic. Type theory and constructive mathematics holds the lambda calculus, the Curry-Howard correspondence and constructive mathematics, and category theory holds categorical logic and toposes. Order, lattices and universal algebra holds Boolean and Heyting algebras as algebras. Theory of computation holds SAT as a problem and the logics of programs, and mathematical software and formalization holds proof assistants and automated theorem proving. Philosophy of mathematics holds logicism, formalism and intuitionism as views of mathematics, and history of mathematics holds the history of logic beyond the survey essay.
Sub-areas
- Logic, formal systems and foundations
- Propositions, connectives and quantifiers
- The propositional calculus
- First-order languages and syntax
- Structures, satisfaction and truth
- Proof systems for first-order logic
- Completeness, compactness and interpolation
- Second-order logic and extensions of first-order logic
- Decidability of logics and theories
- Formal arithmetic and its fragments
- Gödel's incompleteness theorems and related limits
- Natural independence results and fast-growing functions
- Structural proof theory
- Ordinal analysis and ordinal notations
- Proof interpretations and conservation results
- Provability and interpretability logics
- Reverse mathematics and subsystems of second-order arithmetic
- Bounded arithmetic
- Propositional proof complexity
- Syntax, Kripke semantics and completeness of modal logic
- Modal correspondence, bisimulation and extended modal logics
- Applied modal logics
- Intuitionistic and intermediate logics
- Many-valued and fuzzy logics
- Substructural, linear and relevance logics
- Paraconsistent, free, non-monotonic and other non-classical logics
- Algebraic logic
- Truth and the semantic paradoxes
Everything in this topic
The members of this topic and each page that they need, 28 pages in all.
Show the path as a graph
- no evidence level
- Algebraic logic topic member
- Applied modal logics topic member
- Bounded arithmetic topic member
- Completeness, compactness and interpolation topic member
- Decidability of logics and theories topic member
- First-order languages and syntax topic member
- Formal arithmetic and its fragments topic member
- Gödel's incompleteness theorems and related limits topic member
- Intuitionistic and intermediate logics topic member
- Logic, formal systems and foundations topic member
- Many-valued and fuzzy logics topic member
- Modal correspondence, bisimulation and extended modal logics topic member
- Natural independence results and fast-growing functions topic member
- Ordinal analysis and ordinal notations topic member
- Paraconsistent, free, non-monotonic and other non-classical logics topic member
- Proof interpretations and conservation results topic member
- Proof systems for first-order logic topic member
- Propositional proof complexity topic member
- Propositions, connectives and quantifiers topic member
- Provability and interpretability logics topic member
- Reverse mathematics and subsystems of second-order arithmetic topic member
- Second-order logic and extensions of first-order logic topic member
- Structural proof theory topic member
- Structures, satisfaction and truth topic member
- Substructural, linear and relevance logics topic member
- Syntax, Kripke semantics and completeness of modal logic topic member
- The propositional calculus topic member
- Truth and the semantic paradoxes topic member
About this page
| Tag | DYJ0KGTPMR |
|---|---|
| URI | m2://DYJ0KGTPMR |
| Kind | topic |
| Writing | W0 stub |
| MSC | 03Bxx, 03Fxx, 03Gxx |
| Changed | 17 November 2026 |
Markdown · JSON · Edit on GitHub
What this page needs for W1
- a same_as or a source (0 of 1)
- an inventory row: the row of the inventory that the node accounts for (0 of 1)
- a source with a locator (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.
History
Each change to this page, from its provenance log. A change by an agent names its run.
| Date | Change | Field | By |
|---|---|---|---|
| 2026-11-17 | add | the whole node | tamnd |
| 2026-11-17 | change | the section Remarks | tamnd |
What links here
Nodes in this topic
- Intuitionistic and intermediate logics
- Provability and interpretability logics
- Truth and the semantic paradoxes
- Proof interpretations and conservation results
- Substructural, linear and relevance logics
- Reverse mathematics and subsystems of second-order arithmetic
- Propositional proof complexity
- Applied modal logics
- Decidability of logics and theories
- Completeness, compactness and interpolation
- Logic, formal systems and foundations
- Gödel's incompleteness theorems and related limits
- The propositional calculus
- Second-order logic and extensions of first-order logic
- Paraconsistent, free, non-monotonic and other non-classical logics
- Structures, satisfaction and truth
- Propositions, connectives and quantifiers
- First-order languages and syntax
- Formal arithmetic and its fragments
- Algebraic logic
- Structural proof theory
- Bounded arithmetic
- Syntax, Kripke semantics and completeness of modal logic
- Modal correspondence, bisimulation and extended modal logics
- Natural independence results and fast-growing functions
- Proof systems for first-order logic
- Many-valued and fuzzy logics
- Ordinal analysis and ordinal notations