← Back to Math Roadmap

Mathematical Logic

Formal systems, proofs, truth, and the limits of mathematical knowledge — the foundations of mathematics.

Propositional and Predicate Logic

▼
Propositional logic deals with statements that are either true or false, connected by logical operators: AND (conjunction), OR (disjunction), NOT (negation), implies (conditional), and if and only if (biconditional). Truth tables systematically evaluate the truth of compound statements. De Morgan's laws show how to negate AND and OR expressions. Predicate logic (first-order logic) extends propositional logic with quantifiers: "for all" (universal quantifier, an upside-down A) and "there exists" (existential quantifier, a backwards E). Predicates are statements with variables, like "x is prime." First-order logic is expressive enough to formalize almost all of mathematics.
De Morgan's law. The negation of an AND is the OR of the negations. Similarly, the negation of an OR is the AND of the negations.

Proof Methods

▼
Mathematics advances through proofs — airtight logical arguments that establish truth from axioms. Direct proof assumes premises and derives the conclusion through a chain of logical deductions. Proof by contradiction assumes the negation of what you want to prove and shows this leads to an impossibility (a contradiction). Proof by induction proves a statement for all natural numbers by showing it holds for one (the base case) and that if it holds for k then it holds for k plus one (the inductive step) — like dominoes falling. Proof by contrapositive proves "if P then Q" by proving "if not Q then not P" instead. Each method has its own domain of applicability.

Gödel's Incompleteness Theorems

▼
Kurt Gödel's incompleteness theorems (1931) are among the most profound results in all of human thought. The First Incompleteness Theorem states that any consistent formal system capable of expressing basic arithmetic contains true statements that cannot be proved within that system. The Second Incompleteness Theorem states that such a system cannot prove its own consistency. Gödel achieved this by encoding mathematical statements as numbers (Gödel numbering) and constructing a self-referential statement equivalent to "this statement is not provable." The implications are staggering: there are mathematical truths that can never be formally proved. Mathematics can never be complete. Analogous results include Turing's proof that the halting problem is undecidable — no algorithm can determine in general whether a program will halt or run forever.

Key Concepts

▼
Key Concepts
Axiom: a statement accepted as true without proof, serving as a starting point. Theorem: a statement proved to be true using axioms and previously proved theorems. Model: an interpretation that makes all axioms true. Consistency: the system does not contain contradictions (both P and not P cannot be proved). Completeness: every true statement is provable. Gödel showed that for sufficiently powerful systems, you cannot have both consistency and completeness. Computability: what can be algorithmically computed. Turing machines formalize this concept. The Church-Turing thesis posits that anything computable is computable by a Turing machine.

Truth Table Explorer

▼
Build compound logical statements and see their truth tables computed in real time. Explore how logical operators combine truth values.

Turing Machines and the Limits of Computation

▼
Turing Machines and the Limits of Computation
Alan Turing (1936) defined computation via a simple machine: infinite tape, read/write head, finite states with transition rules. The Church-Turing thesis asserts this captures ALL of computation. Turing proved the Halting Problem is undecidable: no algorithm can determine whether an arbitrary program halts. This is the computational analog of Gödel's incompleteness: fundamental limits to algorithmic knowledge. These limits inform computational complexity, AI safety, and the philosophy of mind.