Schola Arcana › Mathematical Logic

Mathematical Logic

from first-order sentences to the completeness theorem — and beyond
10 months ILLC prerequisite Oxford MFoCS 3 phases
This is the one gap that stands between you and the programs you want. Not a wide gap — but a precise one. The completeness theorem is what separates a student who has studied logic from one who has understood it. Enderton. Oliart. Every exercise. No shortcuts. The cathedral is built proof by proof.
your position

Where you stand

Mathematical Logic — overall progress
0%
Phase 1
Completeness
Phase 2
Consequences
Phase 3
Incompleteness

You have first-order logic. Syntax, semantics, structures, truth. That is the foundation — you are already standing at the right door. What lies ahead is the proof that formal provability and semantic truth coincide. That is the completeness theorem, and it is beautiful.

weekly output rule (sacred)
one proof written in full · every week · no exceptions
Enderton exercise → LaTeX → Proof Vault
phase 1 · months 1–2

The completeness theorem

This is the target. Every valid first-order sentence — true in every model — is formally provable. The proof constructs a canonical model from a maximal consistent set of sentences. This is the Henkin construction, and it is the specific argument the ILLC admissions board will expect you to know.

PHASE 01
Enderton — A Mathematical Introduction to Logic
Chapter 2 is your entire world for two months
primary text ▼
§2.1 — 2.3
First-order languages
Variables, constants, function symbols, predicate symbols, terms, atomic formulas, well-formed formulas. The grammar of formal thought.
week 1–2
§2.4 — 2.5
Structures and truth
What it means for a sentence to be true in a structure. Satisfaction, models, validity. The semantic side of the theorem.
week 3–4
§2.6
Formal proofs and soundness
Axioms, rules of inference, formal derivations. Soundness: everything provable is valid. The easy direction — but you must know it precisely.
week 5
§2.7
The completeness theorem
The Henkin construction. Build a maximal consistent set. Construct the term model. Every valid sentence is provable. This is the crown of Phase 1.
week 6–8

How to work through Enderton

each session read the section once, then immediately do every exercise before moving on
oliart bring your written proofs every week — especially §2.7. work through the Henkin construction with him specifically
proof vault every exercise you complete goes into the vault as a LaTeX file — timestamped, public
stuck? reread the definitions from the beginning of the relevant section. in logic, confusion is almost always a sign that a definition wasn't absorbed fully
End of month 2: you can state and prove the completeness theorem from memory, reconstruct the Henkin construction, and explain why compactness follows immediately. Oliart can confirm this in his letter. The ILLC requirement is closed.
phase 2 · month 3

Consequences of completeness

Completeness is not the end — it is the beginning. From it, two of the most powerful theorems in all of logic fall out almost immediately. These are theorems every ILLC student is expected to know cold.

PHASE 02
Compactness + Löwenheim-Skolem
The two great consequences · still Enderton Ch. 2–3
consequences ▼
compactness theorem
If every finite subset of Γ is satisfiable, then Γ is satisfiable
Falls directly out of completeness. Infinitely many axioms are satisfiable iff every finite chunk is. Has wild consequences — you can produce non-standard models of arithmetic from it.
month 3, week 1
Löwenheim-Skolem theorem
If a theory has an infinite model it has models of every infinite cardinality
No first-order theory can pin down a unique infinite cardinality. The reals and the rationals satisfy the same first-order sentences. Deeply strange. Essential for model theory.
month 3, week 2
non-standard models
Arithmetic has non-standard models
Using compactness, construct a model of Peano arithmetic containing infinite natural numbers. The integers are not first-order categorical. This blew your mind the first time. Write about it.
month 3, week 3
optional deepening
Ebbinghaus — Mathematical Logic
Covers the same material with a different proof style. Read alongside Enderton for alternative intuitions. More algebraic in flavor. Good for proof vault variety.
supplementary
  • Compactness theorem — statement, proof from completeness, and at least two applications
    §2.8
  • Downward Löwenheim-Skolem — every satisfiable theory has a countable model
    §2.8
  • Upward Löwenheim-Skolem — models of every infinite cardinality
    §2.8
  • Non-standard models of arithmetic — compactness applied to Peano axioms
    application
End of month 3: completeness, compactness, and Löwenheim-Skolem all under your belt. You can speak about the limits of first-order logic precisely. Model theory is now open to you.
phase 3 · month 3–4

Gödel's incompleteness theorems

You have completeness — now you need incompleteness. These are not contradictions. Completeness says every valid sentence is provable. Incompleteness says some true arithmetical sentences are not provable in any consistent formal system. They operate in different domains and together they define the shape of mathematical knowledge.

PHASE 03
Smullyan — Gödel's Incompleteness Theorems
The crown · connects to recursion theory and TOC
the crown ▼
Gödel numbering
Encoding syntax as arithmetic
Every formula, proof, and symbol gets a unique natural number. Arithmetic can then talk about its own proofs. This is the key move — and it connects directly to Turing machines.
week 1
First incompleteness theorem
No consistent system proves all arithmetical truths
In any consistent formal system strong enough to encode arithmetic, there exists a sentence that is true but unprovable. The Gödel sentence: "I am not provable."
week 2–3
Second incompleteness theorem
No consistent system proves its own consistency
Hilbert's program collapses here. No formal system can prove from within itself that it will never derive a contradiction. The most devastating theorem in the history of mathematics.
week 3–4
connection to Sipser
Incompleteness ↔ undecidability
Gödel's proof and Turing's halting problem are the same idea in different clothes. Incompleteness → there are true sentences no Turing machine can prove. This is your bridge back to TOC.
synthesis
  • Gödel numbering — encoding formulas and proofs as natural numbers
    foundations
  • Representability in arithmetic — recursive functions are representable in Peano arithmetic
    key lemma
  • The Gödel sentence — construction of a sentence that asserts its own unprovability
    ★ first theorem
  • First incompleteness theorem — full proof for any consistent, sufficiently strong system
    ★ first theorem
  • Second incompleteness theorem — Con(T) is not provable in T if T is consistent
    ★ second theorem
  • Connection to the halting problem — incompleteness as undecidability in disguise
    synthesis
End of Phase 3: you understand why Hilbert's program failed, what it means for mathematics to have true but unprovable sentences, and how this connects to everything you already know about computability. Write a proof vault entry that explains incompleteness to someone who knows completeness. That is your synthesis artifact.
proof vault targets

What goes in the vault

These are the proofs that belong in your vault by the end of this track. Every one is a LaTeX document — formal, complete, dated.

THM
Soundness theorem for first-order logic
If Γ ⊢ φ then Γ ⊨ φ · proof by induction on derivation length
month 1
THM
Lindenbaum's lemma
Every consistent set of sentences extends to a maximal consistent set
month 2
THM ★
Completeness theorem — full Henkin proof
If Γ ⊨ φ then Γ ⊢ φ · the complete proof including Henkin extension and term model construction
month 2 ★
THM
Compactness theorem
Γ satisfiable iff every finite subset of Γ is satisfiable · proof from completeness + one application
month 3
THM
Downward Löwenheim-Skolem
Every satisfiable theory has a countable model
month 3
THM ★
First incompleteness theorem
No consistent sufficiently strong system proves all arithmetical truths · full Gödel proof
month 4 ★
ESSAY
Synthesis essay — completeness and incompleteness
Why they are not contradictions · what they together say about the limits of formal systems · your own words
month 4
canon

The books

primary · phase 1–2
Enderton — A Mathematical Introduction to Logic
The canonical text. Chapter 2 is your entire Phase 1 and 2. Clear, rigorous, complete. Do every exercise. This is the book.
start here
primary · phase 3
Smullyan — Gödel's Incompleteness Theorems
Clean, elegant proof of both incompleteness theorems. More readable than Gödel's original. Presupposes completeness — read after Enderton Ch. 2.
phase 3
supplementary
Ebbinghaus — Mathematical Logic
Alternative proof style for the completeness theorem. More algebraic. Good when Enderton's approach feels stuck. Same theorems, different angle.
optional depth
already yours
Sipser — Introduction to the Theory of Computation
Read Ch. 4–5 again after Gödel. The halting problem and incompleteness are the same idea. Turing and Gödel saw the same thing from different directions.
synthesis read
pink, but lethal. 💗 — the completeness theorem is the spine. everything else is the cathedral built around it.
schola arcana · mathematical logic track · ILLC + Oxford MFoCS preparation