Mathematical Logic

Intermediate

Mathematical logic is the branch of mathematics that studies formal systems, symbolic reasoning, and the foundations of mathematics itself. It provides the rigorous framework through which mathematicians and computer scientists express statements, define proofs, and analyze the structure of valid arguments. The discipline emerged in the nineteenth century from the work of George Boole, Gottlob Frege, and others who sought to reduce mathematical reasoning to a precise symbolic calculus, ultimately giving rise to propositional logic, predicate logic, and formal proof theory.

The field is traditionally divided into four major sub-areas: set theory, model theory, proof theory, and computability theory (recursion theory). Set theory investigates the nature of collections and provides the axiomatic basis (most commonly Zermelo-Fraenkel with the Axiom of Choice, or ZFC) on which virtually all of modern mathematics is built. Model theory studies the relationship between formal languages and their interpretations, exploring when and how structures satisfy given sentences. Proof theory analyzes the structure of mathematical proofs themselves, while computability theory examines which problems can be solved algorithmically and which cannot.

Mathematical logic has produced some of the most profound intellectual results of the twentieth century, including Goedel's Incompleteness Theorems, which demonstrated inherent limitations in every sufficiently powerful formal system, and the Church-Turing thesis, which formalized the intuitive notion of computability. Today the field underpins programming language design, automated theorem proving, formal verification of software and hardware, database query languages, and artificial intelligence. A solid understanding of mathematical logic is essential for anyone pursuing advanced work in mathematics, computer science, philosophy, or linguistics.

Practice a little. See where you stand.

Ready to practice?5 minutes. No pressure.

Take the Quiz Learn First

Quiz

Reveal what you know — and what needs work

Adaptive Learn

Responds to how you reason, with real-time hints

Start here

Flashcards

Build recall through spaced, active review

Cheat Sheet

The essentials at a glance — exam-ready

Glossary

Master the vocabulary that unlocks understanding

Learning Roadmap

A structured path from foundations to mastery

Book

Deep-dive guide with worked examples

Key Concepts

The branch of logic that deals with propositions (statements that are either true or false) and logical connectives such as AND, OR, NOT, IMPLIES, and IF AND ONLY IF. It provides the simplest formal system for reasoning about truth values.

Example

The compound statement 'If it is raining AND I have no umbrella, THEN I will get wet' can be symbolized as (P AND Q) -> R, and its truth value can be computed from the truth values of P, Q, and R using truth tables.

An extension of propositional logic that includes quantifiers (for all, there exists) and predicates that express properties of objects and relations among them, allowing statements about all or some elements in a domain.

Example

The statement 'Every even number greater than 2 is the sum of two primes' is expressed as: for all x, (Even(x) AND x > 2) -> exists p exists q (Prime(p) AND Prime(q) AND x = p + q). This is Goldbach's conjecture.

Two landmark theorems proved by Kurt Goedel in 1931. The first states that any consistent formal system capable of expressing basic arithmetic contains true statements that cannot be proved within the system. The second states that such a system cannot prove its own consistency.

Example

In Peano Arithmetic, Goedel constructed a sentence G that effectively says 'This sentence is not provable.' If the system is consistent, G is true but unprovable, demonstrating an inherent limitation of formal systems.

The axiomatic framework formulated by Zermelo and Fraenkel (with the Axiom of Choice) that provides the standard foundation for virtually all of modern mathematics. It defines the rules for constructing and manipulating sets.

Example

Using ZFC axioms, one can construct the natural numbers: 0 is the empty set, 1 is {empty set}, 2 is {empty set, {empty set}}, and so on, building all of arithmetic from pure set-theoretic notions.

The study of the relationship between formal languages (syntax) and their interpretations or structures (semantics). It investigates which sentences are true in which structures and how different models relate to one another.

Example

The Loewenheim-Skolem theorem shows that if a first-order theory has an infinite model, it has models of every infinite cardinality. So first-order Peano Arithmetic, intended to describe the natural numbers, also has uncountable models.

The sub-field of mathematical logic that studies mathematical proofs as formal objects. It analyzes the structure, strength, and properties of proof systems, and provides tools for showing consistency and comparing the power of different axiomatic systems.

Example

Gentzen's cut-elimination theorem shows that any proof in the sequent calculus that uses the cut rule can be transformed into a proof without it, which has deep consequences for the decidability and structure of proofs.

The branch of mathematical logic that studies which functions on the natural numbers are computable by an algorithm and which problems are decidable. It classifies problems by their degree of unsolvability using Turing machines and recursive functions.

Example

The Halting Problem is undecidable: there is no algorithm that can determine, for every program and input pair, whether the program will eventually halt or run forever. Turing proved this in 1936.

A logical system is sound if every provable statement is true in all models, and complete if every statement true in all models is provable. Goedel's Completeness Theorem (1929) establishes that first-order predicate logic is both sound and complete.

Example

In first-order logic, if a sentence is true in every possible interpretation (i.e., it is logically valid), then there exists a formal proof of that sentence from the axioms and inference rules of the system.

An algebraic structure that captures the essential operations of propositional logic (AND, OR, NOT) and set operations (intersection, union, complement). It obeys laws such as commutativity, associativity, distributivity, and De Morgan's laws.

Example

In digital circuit design, the expression NOT(A AND B) is equivalent to (NOT A) OR (NOT B) by De Morgan's law, allowing engineers to simplify and optimize logic gates.

A formal language is a precisely defined set of strings over a given alphabet, constructed according to explicit grammatical rules. In logic, the syntax specifies how to build well-formed formulas (wffs) from symbols, variables, connectives, and quantifiers.

Example

In propositional logic, the string '(P -> (Q AND R))' is a well-formed formula, whereas 'P -> -> Q' violates the syntactic rules and is not a valid formula.

One concept at a time.

Explore your way

Choose a different way to engage with this topic — no grading, just richer thinking.

Explore your way — choose one:

Explore with AI →

Curriculum alignment— Standards-aligned

Grade level

College+

Learning objectives

•Analyze Gödel's incompleteness theorems and their implications for the limits of formal axiomatic systems and provability
•Apply model theory concepts including satisfaction, elementary equivalence, and compactness theorem to study logical structures formally
•Evaluate set theory axioms including ZFC, the Axiom of Choice, and the Continuum Hypothesis for foundational mathematics
•Distinguish between constructive and classical logic, computability theory, and proof theory regarding mathematical reasoning foundations

Recommended Resources

This page contains affiliate links. We may earn a commission at no extra cost to you.

Books

A Mathematical Introduction to Logic

by Herbert B. Enderton

Logic: The Laws of Truth

by Nicholas J.J. Smith

Introduction to Mathematical Logic

by Elliott Mendelson

Goedel, Escher, Bach: An Eternal Golden Braid

by Douglas Hofstadter

A Course in Mathematical Logic for Mathematicians

by Yu. I. Manin

Courses

Introduction to Mathematical Thinking

CourseraEnroll

Introduction to Logic

CourseraEnroll

Language, Proof and Logic

edXEnroll

My Progress Focus Mode

STEM & Engineering

Discrete Mathematics

The study of mathematical structures that are fundamentally discrete rather than continuous, forming the theoretical foundation of computer science and algorithm design.

Intermediate

Mathematical Logic

Quiz

Adaptive Learn

Flashcards

Cheat Sheet

Glossary

Learning Roadmap

Book

Key Concepts

Propositional Logic

Predicate Logic (First-Order Logic)

Goedel's Incompleteness Theorems

Set Theory (ZFC)

Model Theory

Proof Theory

Computability Theory

Completeness and Soundness

Boolean Algebra

Formal Language and Syntax

Explore your way

Grade level

Learning objectives

Recommended Resources

Books

A Mathematical Introduction to Logic

Logic: The Laws of Truth

Introduction to Mathematical Logic

Goedel, Escher, Bach: An Eternal Golden Braid

A Course in Mathematical Logic for Mathematicians

Courses

Introduction to Mathematical Thinking

Introduction to Logic

Language, Proof and Logic

Related Topics

Discrete Mathematics