Math 2.0

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.

Second-order logic and extensions of first-order logic can be read at any time after the core course.

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

  1. Logic, formal systems and foundations
  2. Propositions, connectives and quantifiers
  3. The propositional calculus
  4. First-order languages and syntax
  5. Structures, satisfaction and truth
  6. Proof systems for first-order logic
  7. Completeness, compactness and interpolation
  8. Second-order logic and extensions of first-order logic
  9. Decidability of logics and theories
  10. Formal arithmetic and its fragments
  11. Gödel's incompleteness theorems and related limits
  12. Natural independence results and fast-growing functions
  13. Structural proof theory
  14. Ordinal analysis and ordinal notations
  15. Proof interpretations and conservation results
  16. Provability and interpretability logics
  17. Reverse mathematics and subsystems of second-order arithmetic
  18. Bounded arithmetic
  19. Propositional proof complexity
  20. Syntax, Kripke semantics and completeness of modal logic
  21. Modal correspondence, bisimulation and extended modal logics
  22. Applied modal logics
  23. Intuitionistic and intermediate logics
  24. Many-valued and fuzzy logics
  25. Substructural, linear and relevance logics
  26. Paraconsistent, free, non-monotonic and other non-classical logics
  27. Algebraic logic
  28. 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
Algebraic logic, topic, no evidence levelAlgebraic logictopicApplied modal logics, topic, no evidence levelApplied modal logicstopicBounded arithmetic, topic, no evidence levelBounded arithmetictopicCompleteness, compactness and interpolation, topic, no evidence levelCompleteness, compact…topicDecidability of logics and theories, topic, no evidence levelDecidability of logic…topicFirst-order languages and syntax, topic, no evidence levelFirst-order languages…topicFormal arithmetic and its fragments, topic, no evidence levelFormal arithmetic and…topicGödel's incompleteness theorems and related limits, topic, no evidence levelGödel's incompletenes…topicIntuitionistic and intermediate logics, topic, no evidence levelIntuitionistic and in…topicLogic, formal systems and foundations, topic, no evidence levelLogic, formal systems…topicMany-valued and fuzzy logics, topic, no evidence levelMany-valued and fuzzy…topicModal correspondence, bisimulation and extended modal logics, topic, no evidence levelModal correspondence,…topicNatural independence results and fast-growing functions, topic, no evidence levelNatural independence …topicOrdinal analysis and ordinal notations, topic, no evidence levelOrdinal analysis and …topicParaconsistent, free, non-monotonic and other non-classical logics, topic, no evidence levelParaconsistent, free,…topicProof interpretations and conservation results, topic, no evidence levelProof interpretations…topicProof systems for first-order logic, topic, no evidence levelProof systems for fir…topicPropositional proof complexity, topic, no evidence levelPropositional proof c…topicPropositions, connectives and quantifiers, topic, no evidence levelPropositions, connect…topicProvability and interpretability logics, topic, no evidence levelProvability and inter…topicReverse mathematics and subsystems of second-order arithmetic, topic, no evidence levelReverse mathematics a…topicSecond-order logic and extensions of first-order logic, topic, no evidence levelSecond-order logic an…topicStructural proof theory, topic, no evidence levelStructural proof theo…topicStructures, satisfaction and truth, topic, no evidence levelStructures, satisfact…topicSubstructural, linear and relevance logics, topic, no evidence levelSubstructural, linear…topicSyntax, Kripke semantics and completeness of modal logic, topic, no evidence levelSyntax, Kripke semant…topicThe propositional calculus, topic, no evidence levelThe propositional cal…topicTruth and the semantic paradoxes, topic, no evidence levelTruth and the semanti…topic
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Algebraic logic topic member
  2. Applied modal logics topic member
  3. Bounded arithmetic topic member
  4. Completeness, compactness and interpolation topic member
  5. Decidability of logics and theories topic member
  6. First-order languages and syntax topic member
  7. Formal arithmetic and its fragments topic member
  8. Gödel's incompleteness theorems and related limits topic member
  9. Intuitionistic and intermediate logics topic member
  10. Logic, formal systems and foundations topic member
  11. Many-valued and fuzzy logics topic member
  12. Modal correspondence, bisimulation and extended modal logics topic member
  13. Natural independence results and fast-growing functions topic member
  14. Ordinal analysis and ordinal notations topic member
  15. Paraconsistent, free, non-monotonic and other non-classical logics topic member
  16. Proof interpretations and conservation results topic member
  17. Proof systems for first-order logic topic member
  18. Propositional proof complexity topic member
  19. Propositions, connectives and quantifiers topic member
  20. Provability and interpretability logics topic member
  21. Reverse mathematics and subsystems of second-order arithmetic topic member
  22. Second-order logic and extensions of first-order logic topic member
  23. Structural proof theory topic member
  24. Structures, satisfaction and truth topic member
  25. Substructural, linear and relevance logics topic member
  26. Syntax, Kripke semantics and completeness of modal logic topic member
  27. The propositional calculus topic member
  28. Truth and the semantic paradoxes topic member
About this page
TagDYJ0KGTPMR
URIm2://DYJ0KGTPMR
Kindtopic
WritingW0 stub
MSC03Bxx, 03Fxx, 03Gxx
Changed17 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.

The changes to this page, the oldest first
DateChangeFieldBy
2026-11-17addthe whole nodetamnd
2026-11-17changethe section Remarkstamnd

What links here

Nodes in this topic