Foundations & Logic

⚡ Key Takeaways

Foundations & Logic is the systematic study of the principles, languages, and axiom systems that underpin all of mathematics. Its central result: formal reasoning can be captured by precise symbolic systems (propositional and predicate logic), but these systems have inherent limits — most famously, Gödel's incompleteness theorems. It applies wherever rigorous proof is required (analysis, algebra, computer science). Developed primarily 1879–1940 by Frege, Russell, Hilbert, Gödel, Tarski, and others.

💡 The Core Insight

Mathematics can be reduced to manipulating strings of symbols according to explicit rules — yet this very formalization reveals an unbridgeable gap between what is true and what is provable. Logic separates syntax (formal derivation, pure symbol-pushing) from semantics (meaning, truth in structures), and the deepest theorems of the field measure exactly when these two coincide and when they cannot.

DefinitionPropositional Language

A propositional language consists of:

Atomic propositions $p, q, r, \dots$ (sentence letters).
Connectives: $\neg$ (not), $\wedge$ (and), $\vee$ (or), $\rightarrow$ (implies), $\leftrightarrow$ (iff).
Formulas built recursively: each atom is a formula; if $\varphi, \psi$ are formulas, so are $\neg\varphi$ , $(\varphi \wedge \psi)$ , $(\varphi \vee \psi)$ , $(\varphi \rightarrow \psi)$ , $(\varphi \leftrightarrow \psi)$ .

A truth assignment $v$ maps each atom to $\{0,1\}$ (false/true) and extends to all formulas via truth tables.

DefinitionFirst-Order Language

A first-order language $\mathcal{L}$ adds:

Variables $x, y, z, \dots$ ranging over a domain.
Quantifiers $\forall$ (for all), $\exists$ (there exists).
Predicate (relation) symbols $P, Q, \dots$ , function symbols $f, g, \dots$ , and constants $c, d, \dots$ .
Terms: variables, constants, and $f(t_1,\dots,t_n)$ for terms $t_i$ .
Atomic formulas: $P(t_1,\dots,t_n)$ and (with equality) $t_1 = t_2$ .

A structure (model) $\mathcal{M} = (M, I)$ supplies a nonempty domain $M$ and an interpretation $I$ assigning relations, functions, and elements to the symbols. The satisfaction relation $\mathcal{M} \models \varphi[s]$ (with variable assignment $s$ ) is defined by Tarski's recursion.

DefinitionValidity, Satisfiability, Entailment

For a set of formulas $\Gamma$ and a formula $\varphi$ :

$\varphi$ is valid ( $\models \varphi$ ) if true in every structure under every assignment.
$\varphi$ is satisfiable if true in some structure.
$\Gamma$ semantically entails $\varphi$ , written $\Gamma \models \varphi$ , if every model of all of $\Gamma$ is a model of $\varphi$ .
$\Gamma$ proves $\varphi$ , written $\Gamma \vdash \varphi$ , if there is a finite formal derivation of $\varphi$ from $\Gamma$ using the axioms and inference rules (e.g. modus ponens and generalization).

TheoremGödel Completeness Theorem (1929)

For first-order logic, provability and entailment coincide:

4

\quad \Gamma \vdash \varphi \;\;\Longleftrightarrow\;\; \Gamma \models \varphi

Derivation hint: Soundness ( $\Rightarrow$ ) is an induction on derivation length; completeness ( $\Leftarrow$ ) is proved contrapositively — if $\Gamma \not\vdash \varphi$ then $\Gamma \cup \{\neg\varphi\}$ is consistent, hence (Henkin construction) has a model.

TheoremCompactness Theorem

A set $\Gamma$ of first-order sentences has a model if and only if every finite subset of $\Gamma$ has a model.

TheoremGödel First Incompleteness Theorem (1931)

Any consistent, recursively axiomatizable theory $T$ that interprets elementary arithmetic (e.g. Peano Arithmetic, PA) is incomplete: there exists a sentence $G_T$ such that

5

\quad T \nvdash G_T \quad\text{and}\quad T \nvdash \neg G_T

yet $G_T$ is true in the standard model $\mathbb{N}$ . Derivation hint: Arithmetize syntax (Gödel numbering), construct via the diagonal lemma a sentence asserting "I am not provable in $T$ "; consistency forbids proving it, $\omega$ -consistency forbids refuting it.

TheoremGödel Second Incompleteness Theorem

For $T$ as above, if $T$ is consistent then $T$ cannot prove its own consistency statement $\mathrm{Con}(T)$ :

6

\quad T \nvdash \mathrm{Con}(T), \qquad \text{where } \mathrm{Con}(T) \equiv \neg\,\mathrm{Prov}_T(\ulcorner 0=1 \urcorner)

Derivation hint: Formalize the First Theorem's argument inside $T$ ; the provable equivalence $T \vdash \mathrm{Con}(T) \rightarrow G_T$ combined with $T \nvdash G_T$ yields $T \nvdash \mathrm{Con}(T)$ .

ProofSketch of the First Incompleteness Theorem

1. Gödel numbering. Assign to every symbol, formula, and finite proof a unique natural number. Syntactic operations (substitution, "is an axiom", "is a proof of") become arithmetical relations on these codes. 2. Representability. Because $T$ interprets arithmetic, every primitive recursive relation is representable in $T$ : there is a formula $\mathrm{Proof}_T(p, n)$ that holds (and is provable) exactly when $p$ codes a $T$ -proof of the formula coded by $n$ . 3. Provability predicate. Define $\mathrm{Prov}_T(n) \equiv \exists p\,\mathrm{Proof}_T(p,n)$ — " $n$ is provable". 4. Diagonal lemma. For any formula $\psi(x)$ there exists a sentence $\sigma$ with $T \vdash \sigma \leftrightarrow \psi(\ulcorner\sigma\urcorner)$ . Apply it to $\psi(x) \equiv \neg\mathrm{Prov}_T(x)$ to obtain $G_T$ with $T \vdash G_T \leftrightarrow \neg\mathrm{Prov}_T(\ulcorner G_T\urcorner)$ . 5. If $T$ is consistent, $T \nvdash G_T$ . Suppose $T \vdash G_T$ . Then a proof exists, so $\mathrm{Prov}_T(\ulcorner G_T\urcorner)$ is true and provable, giving $T \vdash \mathrm{Prov}_T(\ulcorner G_T\urcorner)$ . But $G_T$ says the opposite, contradicting consistency. 6. If $T$ is $\omega$ -consistent, $T \nvdash \neg G_T$ . A symmetric argument over the codes of would-be proofs. 7. Conclusion. $G_T$ is undecided by $T$ yet, reading it from outside, it truthfully asserts its own unprovability — so it is true in $\mathbb{N}$ . $\qquad\blacksquare$

∎

KG

Kurt Gödel

1906–1978

Austrian-American logician, the central figure of 20th-century foundations. In his 1929 doctoral thesis he proved the completeness of first-order logic; in 1931, at age 25, he proved the incompleteness theorems, overturning Hilbert's program to secure mathematics by finitary consistency proofs. He later proved the relative consistency of the Axiom of Choice and the Continuum Hypothesis with ZF (via the constructible universe $L$ ), discovered rotating-universe solutions to Einstein's equations, and was a close colleague of Einstein at Princeton. His work permanently reshaped how mathematicians understand the limits of formal systems.

🧠 Intuition

Think of a formal theory as a game: axioms are the starting position, inference rules are the legal moves, and theorems are the positions reachable from the start. Semantics asks instead which positions are "good" (true in some intended world). The completeness theorem says, remarkably, that for first-order logic these two notions coincide — every truth is reachable. But once a theory can talk about its own moves (arithmetic codes proofs), it can construct a self-referential sentence — a logical analogue of "this statement cannot be reached by any legal sequence of moves." If the game is consistent, that sentence is indeed unreachable, hence true but unprovable. Incompleteness is therefore not a flaw of cleverness; it is the price of any system rich enough to describe itself.

Figure

The syntax–semantics square: how

\vdash

and

\models

relate, with the boundary where they diverge

ExampleTruth-table validity check

Given: Determine whether $((p \rightarrow q) \wedge p) \rightarrow q$ (modus ponens) is valid.

Steps: Enumerate all $2^2 = 4$ assignments to $(p,q)$ and evaluate the antecedent $A = (p\rightarrow q)\wedge p$ and the whole formula $A \rightarrow q$ .

$p$	$q$	$p\rightarrow q$	$A$	$A\rightarrow q$
1	1	1	1	1
1	0	0	0	1
0	1	1	0	1
0	0	1	0	1

The final column is $1$ in every row.

Answer: $\boxed{\models ((p\rightarrow q)\wedge p)\rightarrow q \text{ — the formula is a tautology (valid).}}$

ExampleUsing compactness to build an infinite model

Given: A theory $T$ has, for each $n$ , a model with at least $n$ elements. Show $T$ has an infinite model.

Steps: 1. For each $n\ge 2$ introduce the sentence $\lambda_n \equiv \exists x_1\cdots\exists x_n \bigwedge_{i<j}(x_i \neq x_j)$ ("there are at least $n$ distinct elements"). 2. Form $T' = T \cup \{\lambda_n : n\ge 2\}$ . 3. Take any finite subset $\Delta \subseteq T'$ . It mentions only $\lambda_2,\dots,\lambda_N$ for some largest $N$ . By hypothesis $T$ has a model with $\ge N$ elements, which satisfies all of $\Delta$ . So $\Delta$ is satisfiable. 4. Every finite subset is satisfiable $\Rightarrow$ by Compactness, $T'$ has a model $\mathcal{M}$ . 5. $\mathcal{M} \models \lambda_n$ for all $n$ , so $|M| \ge n$ for every $n$ .

Answer: $\boxed{T \text{ has a model with infinitely many elements.}}$ (This is why "finiteness" is not first-order expressible.)

⚠️ Common mistake

"Gödel's theorem shows mathematics is contradictory / unreliable." False. Incompleteness says a sufficiently strong consistent theory cannot prove every truth about arithmetic, and cannot prove its own consistency — not that it is inconsistent. Working mathematics is unaffected; the undecidable sentences are exotic self-referential constructions (though natural examples like Goodstein's theorem and the Paris–Harrington principle also exist).

"⊢ and ⊨ are the same thing." Only for first-order logic (validity), by completeness. For a theory like PA they diverge: there are sentences entailed by truth in $\mathbb{N}$ that are not derivable from the axioms.

Counterexample

The Continuum Hypothesis (CH). One might expect every well-posed mathematical question to be decidable from the standard axioms ZFC. But Gödel (1940) showed ZFC cannot refute CH, and Cohen (1963, via forcing) showed ZFC cannot prove it. Thus

\text{ZFC} \nvdash \text{CH} \quad\text{and}\quad \text{ZFC} \nvdash \neg\text{CH},

a concrete, natural statement about the size of $\mathbb{R}$ that the accepted axioms leave genuinely undecided — a vivid counterexample to the dream of a single complete foundation.

connection

Foundations and logic sit beneath the entire edifice of mathematics. Set Theory provides the objects (ZFC axioms) over which logic quantifies, and incompleteness/forcing are studied there. Model Theory is the semantic branch — studying structures, definability, and the Löwenheim–Skolem and compactness theorems. Proof Theory is the syntactic branch — ordinal analysis and the consistency strength of theories. Computability Theory is intimately linked: the recursively axiomatizable hypothesis and the diagonal lemma connect directly to Turing Machines and the unsolvability of the Halting Problem, which is essentially the First Incompleteness Theorem in computational dress. Category Theory offers an alternative structural foundation via Topos Theory.

🔬 Where this appears

⏳ History

- 1854 — George Boole publishes An Investigation of the Laws of Thought, algebraizing propositional logic.

- 1879 — Gottlob Frege's Begriffsschrift introduces quantifiers and the first complete formal predicate logic.

- 1889 — Giuseppe Peano formulates his axioms for arithmetic.

- 1899 — David Hilbert's Foundations of Geometry establishes the modern axiomatic method and the program of consistency proofs.

- 1901–1910 — Russell discovers his paradox (1901); Russell & Whitehead's Principia Mathematica (1910–13) attempts a logicist foundation via type theory.

- 1908–1922 — Zermelo (1908) and Fraenkel/Skolem refine the ZFC axioms of set theory.

- 1929–1931 — Gödel proves completeness (1929), then the two incompleteness theorems (1931); Tarski develops the semantic definition of truth (published 1933/35).

- 1936 — Church and Turing independently establish the undecidability of first-order validity (the Entscheidungsproblem) and formalize computability; Gentzen gives a consistency proof of PA via transfinite induction to

\varepsilon_0

(1936).

- 1940 / 1963 — Gödel proves Con(ZF)→Con(ZFC + CH) via

L

; Cohen invents forcing, proving the independence of CH and AC, earning the 1966 Fields Medal.

open-problem

Several deep questions remain at the frontier of foundations:

Resolving the Continuum Hypothesis. Since CH is independent of ZFC, the search continues for new axioms (large-cardinal hypotheses, forcing axioms like MM, or Woodin's "Ultimate- $L$ " program) that would settle the size of the continuum on principled grounds. Whether there is a "correct" answer is philosophically contested (set-theoretic pluralism vs. realism).
Consistency strength hierarchy. The strengths of theories are linearly ordered by large cardinals empirically, but why this near-linearity holds has no general explanation.
Reverse mathematics asks which axioms are necessary to prove given theorems of ordinary mathematics; the program (Friedman, Simpson) has revealed surprising fine structure (the "big five" subsystems of second-order arithmetic) but does not exhaust all theorems.
Foundational pluralism. Whether set theory, type theory (HoTT / univalent foundations), or category theory is the "right" foundation — or whether the question is even meaningful — remains open.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also