The Math That Broke Mathematics — Notes from CMU CS 15-251
NOTE: This blog and all the blogs that are released or yet to be released in this series are AI generated using Claude Opus. I take notes for each lecture, ask doubts to LLMs and people I know IRL and compile everything in one place and then make AI write a blog post for me. That being said, this paragraph is written by me without AI and I assure you that the rest of this blog post is NOT AI slop. I read this myself and got it reviewed by a couple people before posting. Based on feedback and reading it myself, I have refined it further and added more content or dumbed down certain parts for myself (as I do not have a strong math background) and other readers like me. I am open to criticism, suggestions, reviews or any other thoughts you may have. Feel free to reach out via any method (Avoid Twitter as DMs there are full of porn bots and they do nothing to fix it, LinkedIn DMs or emails would be better, but I’m busy so might reply late).
I’ve been self-studying Great Ideas in Theoretical Computer Science (CS 15-251) from CMU, taught by Professor Ryan O’Donnell. It’s a legendary course that asks the deepest question in all of computer science: What can be computed?
These are my notes from Lectures 1 through 5. This isn’t a textbook — it’s more like the blog post I wish existed when I started. I’ll walk you through the ideas, the history, the proofs, the paradoxes, and the moments where your intuition just completely shatters.
Let’s begin at the end of the 19th century, with a man who thought he could conquer all of mathematics.
Part I: Hilbert’s Dream and Its Destruction
David Hilbert and “The Problems of Mathematics”
In 1900, at the International Congress of Mathematicians in Paris, David Hilbert — one of the most influential mathematicians to ever live — stood before his peers and laid out 23 unsolved problems that he believed would define mathematics for the coming century.
But Hilbert had a bigger, more ambitious vision behind those problems. He believed mathematics was complete and decidable:
- Complete: Every true mathematical statement can be proven.
- Decidable: There exists a mechanical procedure — an algorithm — to determine whether any statement is true or false.
This vision is called Hilbert’s Program: can we build a perfect, all-knowing math machine?
Hilbert’s Three Questions (1928)
Hilbert eventually crystallized his program into three precise questions:
| Question | What Hilbert Asked |
|---|---|
| Is math Complete? | Can every true mathematical statement be proven? |
| Is math Consistent? | Can math ever contradict itself? |
| Is math Decidable? | Is there an algorithm that can determine the truth of any statement? |
Hilbert desperately wanted the answer to all three to be YES.
He got NO to every single one.
Hilbert’s 10th Problem — A Taste of Undecidability
Among Hilbert’s 23 problems, the 10th asked:
“Is there an algorithm that can determine whether any polynomial equation with integer coefficients has an integer solution?”
These are called Diophantine equations — equations where you’re only interested in integer solutions.
Easy example:
x² + y² = z²Does this have integer solutions? Yes! For instance, (3, 4, 5) — the classic Pythagorean triple.
Harder example:
x² + y² = 3Does this have integer solutions? No. You can check: 0² + 0² = 0, 1² + 1² = 2, 1² + 2² = 5 — no pair of integers squares to 3.
Hilbert wanted a single algorithm that could answer this question for ALL such equations, no matter how complex. In 1970, Yuri Matiyasevich proved the answer is NO — building on decades of work by Martin Davis, Hilary Putnam, and Julia Robinson (the DPRM theorem). The proof showed that Diophantine equations are powerful enough to encode any computable problem, including ones that are provably undecidable.
Kurt Gödel — The First Blow (1931)
Before anyone even addressed algorithms, a 25-year-old Austrian logician named Kurt Gödel dropped an absolute bombshell with his Incompleteness Theorems:
First Incompleteness Theorem:
In any consistent formal system powerful enough to do basic arithmetic, there exist statements that are true but unprovable within that system.
Second Incompleteness Theorem:
Such a system cannot prove its own consistency.
The key trick: Gödel constructed a statement that essentially says:
“This statement cannot be proven.”
If you can prove it, then it says it can’t be proven — contradiction! If you can’t prove it, then what it says is true — so it’s a true statement that can’t be proven!
Let that sink in. Gödel proved that math has permanent blind spots. No matter how many axioms you add, there will always be true things you can’t prove. And math can’t even vouch for its own sanity.
Analogy: Imagine writing a legal code so thorough it covers every possible situation. Gödel proved this is impossible — no matter how many laws you write, there will always be situations your laws can’t handle. You can add new laws for those gaps, but then new gaps appear. It never ends.
The Entscheidungsproblem — The Decision Problem
Gödel killed completeness. But decidability — Hilbert’s third question — was still technically open. Maybe an algorithm could still decide things, even if proofs had limits?
In 1928, Hilbert (with Wilhelm Ackermann) sharpened this into one precise question called the Entscheidungsproblem (German for “decision problem”):
“Is there an algorithm that takes any mathematical statement as input and outputs YES or NO — whether it’s provable?”
This single question launched the entire field of theoretical computer science. But to answer it, someone first needed to define what an “algorithm” even is.
Issues that the Entscheidungsproblem was trying to solve:
Take the statement: “Every even number greater than 2 is the sum of two primes.”
-
Natural language is too ambiguous for a machine. Before you can feed any statement to an algorithm, you need to express it in a precise formal symbolic language — no English, no ambiguity. First Order Logic was only just being developed to solve this.
-
“Algorithm” had no mathematical definition. Everyone intuitively knew what following a step-by-step procedure meant, but there was no formal mathematical object called an algorithm. And you cannot prove “no algorithm exists for X” if you haven’t precisely defined what an algorithm is — that’s like proving unicorns don’t exist without defining what a unicorn is. This is the core problem Church and Turing set out to solve.
-
No computers existed. “Computation” meant a human with paper and pencil following rules. There was no hardware, no software, no programming language to even test ideas on. Everything had to be figured out from pure abstract reasoning.
Alonzo Church — Lambda Calculus (1936)
Alonzo Church at Princeton took the first crack at it. His approach: define “algorithm” formally, then show no such algorithm can exist for the Entscheidungsproblem.
He invented Lambda Calculus — a minimal formal system where everything is a function:
λx. x + 1 → a function that adds 1 to x
(λx. x + 1) 5 → apply it to 5, get 6It looks nothing like a “computer,” but it turns out to be powerful enough to compute anything computable. Church used it to prove the Entscheidungsproblem’s answer is no.
But Gödel wasn’t convinced. He thought lambda calculus was too narrow — maybe there were intuitively computable things that lambda calculus couldn’t handle. Fair criticism. The definition needed independent validation.
How EXACTLY did Lambda Calculus help?
Remember the problem — before you can prove “no algorithm exists,” you need to define what an algorithm is. Otherwise you’re just saying “no thing exists” without saying what kind of thing.
Church’s answer was: an algorithm is anything expressible as a lambda calculus function. That’s your definition of computation.
Once you have that definition, you can ask precise questions. Church then identified a specific problem called the Halting Problem for Lambda Calculus (more on this later) — essentially, given a lambda expression, does it ever reduce down to a final answer or does it keep reducing forever? He proved no lambda calculus function can decide this for all inputs.
And since lambda calculus is computation by definition, that means no algorithm can decide it. Entscheidungsproblem answered — NO.
How was it narrow?
Gödel’s objection was basically: “you just defined computation to be lambda calculus. That’s circular. How do you know your definition actually captures everything a human can compute mechanically?”
Maybe there are processes a human can clearly follow step by step that lambda calculus simply can’t express. If so, Church hasn’t proven the Entscheidungsproblem is unsolvable — he’s only proven it’s unsolvable within lambda calculus, which is a much weaker statement.
It’s like defining “vehicle” as “car” and then proving buses don’t exist. Your proof is only as good as your definition.
That’s why Turing’s independent approach mattered so much — he came from a completely different direction, with a completely different model, and got the exact same answer. Two independent definitions of computation agreeing with each other is much harder to dismiss.
Alan Turing — The Turing Machine (1936)
That validation came from Alan Turing, who approached the same problem from a completely different angle. Instead of abstract functions, he imagined a human doing computation mechanically — following rules on paper, step by step.
He abstracted this into the Turing Machine:
- An infinite tape divided into cells (your memory/paper)
- A read/write head that moves left or right (your pencil)
- A finite set of states (your rulebook)
- A transition function: given current state + symbol under head → write a symbol, move left/right, change state
State: q1, Read: 0 → Write: 1, Move: Right, New State: q2
State: q2, Read: 1 → Write: 0, Move: Left, New State: q1Dead simple mechanically, but it can compute anything computable.
Turing also used this to kill the Entscheidungsproblem — he proved the Halting Problem is undecidable: no algorithm can determine whether an arbitrary program will halt or run forever.
What exactly is the Halting Problem proof :
The Halting Problem asks: can you write a program that looks at any other program and tells you whether it will finish or run forever?
First, understand why this matters. Some programs finish:
print("hello")
← done, halts immediatelySome programs run forever:
while True:
print("hello")
← never stops, infinite loopAnd some are not obvious at all:
← some 10,000 line program doing complex math
← will this ever finish? no idea just by looking at itTuring asked: can we build one single program H that takes any program + its input, and always correctly answers “halts” or “runs forever”?
The proof that it’s impossible:
Assume H exists. It looks like this:
H(program, input) → "halts" or "runs forever"Now build a new diabolical program D that uses H against itself:
D(program):
if H(program, program) says "halts":
loop forever
else:
haltD takes a program, asks H what it does when run on itself, then does the opposite.
Now run D on itself — D(D):
- If
D(D)halts → H said “halts” → but D loops forever when H says that → contradiction - If
D(D)loops forever → H said “runs forever” → but D halts when H says that → contradiction
Both cases explode. H cannot exist.
The Grand Unification: Turing Machine = Lambda Calculus
Two completely different formalisms, invented independently, same year, 1936 — and they turned out to be exactly equivalent:
- Anything a Turing Machine can compute, Lambda Calculus can express
- Anything Lambda Calculus can compute, a Turing Machine can simulate
Gödel’s objection to lambda calculus was now dead. Two totally independent definitions of computation agreed with each other. That’s not a coincidence — it’s pointing at something deep and real about the nature of computation itself.
The Church-Turing Thesis
This convergence led to the Church-Turing Thesis — not a theorem (it can’t be formally proven), but a thesis, a claim about reality:
“Any function that is effectively computable by a human following a mechanical procedure can be computed by a Turing Machine.”
In modern terms: Turing Machines capture exactly what it means to compute. No model of computation ever invented — lambda calculus, RAM machines, Python, quantum computers (for decidability) — has been able to compute anything a Turing Machine can’t.
Why can’t it be proven? Because “effectively computable” is an informal, intuitive concept. You can’t mathematically prove something about an informal idea. But the evidence is overwhelming.
The Arc: From Hilbert to Computer Science
Hilbert (1900): "Math is complete & decidable — find me an algorithm!"
↓
Gödel (1931): "Math isn't even complete." (Incompleteness Theorems)
↓
Church (1936): Defines computation via Lambda Calculus → kills Entscheidungsproblem
Turing (1936): Defines computation via Turing Machines → kills Entscheidungsproblem
↓
Both models agree → Church-Turing Thesis: THIS is what computation means.The punchline: Hilbert asked if math could be mechanized. The answer was a hard no — and in the process of proving that, we accidentally invented computer science.
Part II: What Is a Proof?
Proposition vs. Proof
- Proposition (or Claim): A statement that is either true or false. It’s the destination.
- Proof: The logical argument that demonstrates the proposition is true. It’s the route to the destination, where every step is justified.
This distinction seems obvious. But the gap between “probably true” and “proven” is everything in mathematics.
The Collatz Conjecture — Easy to State, Impossible to Prove
The rule: Start with any positive integer n. If it’s even, divide by 2. If it’s odd, multiply by 3 and add 1. Repeat.
The claim: No matter what number you start with, you’ll eventually reach 1.
Starting from 6:
6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 ✓
Starting from 27:
27 → 82 → 41 → 124 → 62 → 31 → 94 → 47 → 142 → 71 → ...
... (111 steps later) → ... → 4 → 2 → 1 ✓A child could understand the rule. It’s been verified for every number up to about 2⁶⁸ — that’s 295,147,905,179,352,825,856 numbers checked. Every single one eventually reaches 1.
But no one has ever proven it’s true for ALL numbers.
This is the gap. Tons of evidence, zero proof. The Collatz Conjecture has been open since 1937, and the great Paul Erdős famously said: “Mathematics may not be ready for such problems.”
What Is a Conjecture?
A conjecture is a proposition that:
- Is believed to be true (usually based on strong evidence or patterns)
- Has not been proven (and not disproven either)
Once proven, a conjecture graduates to theorem status. If disproven, it’s just… false.
The Banach-Tarski Theorem — When Your Intuition Is Wrong
Now for the flip side. Consider this proposition:
A solid 3D ball can be decomposed into a finite number of pieces, and those pieces can be reassembled — using only rotations and translations, no stretching! — into TWO balls, each identical in size to the original.
One ball → cut into 5 pieces → rearrange → two balls. Same size. From nothing.
Your gut says: impossible. Violates conservation of volume, conservation of mass, basic physics, common sense.
But it’s a proven theorem. Stefan Banach and Alfred Tarski proved it in 1924.
The “catch” is that the pieces are not ordinary shapes. They’re bizarre, fractal-like, non-measurable sets — shapes so weird that the concept of “volume” doesn’t even apply to them. They require the Axiom of Choice (explained much later in this post) to construct and can’t physically exist. But mathematically? The proof is airtight.
Here’s the lesson from both examples:
| Collatz Conjecture | Banach-Tarski | |
|---|---|---|
| Feels like… | Obviously true | Obviously impossible |
| Status | Unproven conjecture | Proven theorem (1924) |
| Lesson | Intuition says true ≠ proven | Intuition says false ≠ disproven |
Intuition is not proof, in either direction.
Mathematical Terminology — The Hierarchy of Results
Here’s the full pecking order of mathematical statements:
| Term | Proven? | Role | Analogy |
|---|---|---|---|
| Axiom | No proof needed | The foundation — rules we agree to start with | Rules of the board game |
| Lemma | ✅ Proven | A helper result, built to make a bigger proof work | A tool you build first |
| Theorem | ✅ Proven | A major, important result | The big achievement |
| Proposition | ✅ Proven | A minor, less significant result | A useful fact |
| Corollary | ✅ Proven | Follows immediately from a theorem | A free bonus |
| Conjecture | ❌ Not proven | Believed true, but unproven | An educated guess |
How they fit together:
Axioms (starting rules, accepted without proof)
↓ used to prove...
Lemma: "If n² is even, then n is even" (helper result)
↓ used to prove...
Theorem: "√2 is irrational" (the big result!)
↓ immediately implies...
Corollary: "√2 cannot be written as a/b for integers a, b"Proof of the lemma — “If n² is even, then n is even”:
We prove the contrapositive: if n is odd, then n² is odd.
If n is odd, then n = 2k + 1 for some integer k. So:
n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1This is odd (it’s 2 × something + 1). So n² is odd, which means: if n² is not odd (i.e., n² is even), then n is not odd (i.e., n is even). ∎
Proof of the theorem — “√2 is irrational”:
Assume for contradiction that √2 = a/b where a and b are integers with no common factors (i.e., the fraction is fully reduced).
√2 = a/b
2 = a²/b²
2b² = a²So a² is even. By our lemma, a must be even. Write a = 2c:
2b² = (2c)² = 4c²
b² = 2c²So b² is even. By the lemma again, b must be even.
But now both a and b are even — they share a common factor of 2. This contradicts our assumption that a/b was fully reduced! Therefore √2 cannot be written as a fraction. It’s irrational. ∎
A Brief Prehistory of Proof
Euclid (~300 BCE): Wrote Elements, arguably the most influential math text in history. Started from a small set of axioms — self-evident truths like “a straight line can be drawn between any two points” — and built up hundreds of theorems via step-by-step logical deduction.
Euclid’s proof that there are infinitely many primes is still one of the most beautiful proofs ever written.
Euclid starts by assuming the opposite of what he wants to prove. He says: “okay fine, let’s say there are only finitely many primes. Let’s list them all:”
2, 3, 5, 7, 11, 13, ... , pₙThat’s our complete list. Every prime that exists is on it. No exceptions.
Now multiply every single prime on the list together, then add 1:
N = (2 × 3 × 5 × 7 × 11 × 13 × ... × pₙ) + 1What happens when you divide N by any prime on our list? Take 2 for example:
N = (2 × 3 × 5 × ...) + 1The first part is perfectly divisible by 2. But then you add 1. So N divided by 2 always leaves remainder 1. Never cleanly divides.
Same for 3:
N = (2 × 3 × 5 × ...) + 1First part divisible by 3, then +1. Remainder 1 again. This works for every single prime on our list — N is never cleanly divisible by any of them.
Now here’s the thing — every number bigger than 1 is either prime itself, or has prime factors. So N is either:
- Prime itself → but it’s not on our list → our list was incomplete
- Not prime → so it has prime factors → but we just showed no prime on our list divides it → those factors must be primes not on our list → our list was incomplete
Either way our “complete list of all primes” was missing something. Contradiction.
So the original assumption — that there are finitely many primes — must be wrong. There are infinitely many. ∎
For ~2000 years, “proof” meant clear, convincing, step-by-step logical argument — but the underlying logic itself wasn’t formalized.
19th–20th Century: First-Order Logic. Mathematicians realized natural-language proofs had hidden gaps. They formalized logic into a precise symbolic system with quantifiers (∀ “for all”, ∃ “there exists”), connectives (∧, ∨, ¬, →), and strict inference rules.
Russell & Whitehead — Principia Mathematica (1910–1913): The ultimate attempt to derive ALL of mathematics from pure logic. Starting from a tiny set of logical axioms, they tried to build everything via formal deduction. It famously takes over 300 pages to rigorously prove that 1 + 1 = 2. This effort unintentionally set the stage for Gödel — who then showed such a complete system has inherent limits.
Proof Anecdotes — When “Proven” Doesn’t Mean “Done”
These stories show that even accepted proofs can be wrong:
The Four Color Theorem:
The claim: any map can be colored using only 4 colors such that no two adjacent regions share a color.
- 1852: Conjectured by Francis Guthrie
- 1879: Alfred Kempe publishes a proof → accepted for 11 years
- 1880: Peter Tait publishes another proof
- 1890: Percy Heawood finds a bug in Kempe’s 1879 proof
- 1891: Another mathematician finds a bug in Tait’s 1880 proof
- Both “proofs” were wrong, but nobody noticed for over a decade!
- 1976: Finally proven correctly by Appel and Haken — using a computer to check 1,936 specific configurations
Classification of Finite Simple Groups: A proof spanning 100+ papers by dozens of mathematicians, totaling an estimated 10,000–15,000 pages. No single human has ever read the entire proof.
Fermat’s Last Theorem: “There are no positive integers a, b, c satisfying aⁿ + bⁿ = cⁿ for any n > 2.” Fermat scribbled this in 1637 with the note that his proof was “too large to fit in the margin.” It took 358 years and entirely new branches of mathematics before Andrew Wiles finally proved it in 1994.
Kepler’s Conjecture: The standard pyramid stacking of oranges is the densest possible sphere packing. Tom Hales announced a proof in 1998, but it included 250 pages of text plus 3 GB of computer code. Reviewers spent years and could only certify they were “99% certain” it was correct. Hales then built the Flyspeck project to formally verify the entire proof using a computer — completed in 2014.
Computer-Assisted Proofs & Coq: This is where the story converges. As proofs get longer and more complex, humans alone can’t reliably verify them. Coq (now often called Rocq) is a formal proof management system where you write proofs in a precise language and the computer checks every single logical step — no gaps, no hand-waving. If Coq accepts it, it’s guaranteed correct.
Traditional proof: Human writes → Human(s) review → "looks right to us"
Coq-verified proof: Human writes (formally) → Computer checks EVERY step → guaranteedHow to Find a Proof
There’s no single algorithm (ironic!), but here are the heuristics mathematicians actually use:
- Try small cases. Plug in n=1, 2, 3 and see what happens. Patterns jump out.
- Work backwards. Ask “what would need to be true for this to hold?” and chase it backward.
- Generalize or specialize. Sometimes proving a stronger statement is easier — counterintuitively, a stronger claim can have a cleaner inductive structure.
- Look for an extremal element. The biggest, smallest, first, last — extremal objects have exploitable properties.
- Match the technique to the statement’s shape:
- “For all n…” → induction
- “There exists…” → construction, or pigeonhole
- “If A then B” (hard directly) → contrapositive or contradiction
- “At least k things satisfy…” → counting arguments
Proof by Induction
Induction is how you prove “P(n) is true for all n ≥ n₀” using just two pieces:
- Base case: Prove P(n₀) directly.
- Inductive step: Assume P(k) is true for some arbitrary k ≥ n₀ (the inductive hypothesis). Using only this assumption, prove P(k+1).
If both hold, then P(n₀) ⇒ P(n₀+1) ⇒ P(n₀+2) ⇒ … — like dominoes, each knocks over the next, forever.
Classic example: Prove that 1 + 2 + ... + n = n(n+1)/2
Base case (n = 1): LHS = 1. RHS = 1×2/2 = 1. ✓
Inductive step: Assume 1 + 2 + ... + k = k(k+1)/2 (inductive hypothesis).
Show it holds for k+1:
1 + 2 + ... + k + (k+1)
= k(k+1)/2 + (k+1) ← by inductive hypothesis
= k(k+1)/2 + 2(k+1)/2 ← common denominator
= [k(k+1) + 2(k+1)] / 2
= (k+1)(k+2) / 2 ← factor out (k+1)This is exactly the formula with n = k+1. ✓
By induction, the formula holds for all n ≥ 1. ∎
Part III: Deductive Systems
The ATM Problem — Your First Deductive System
Setup: An ATM only dispenses $2 and $5 bills. Claim: You can withdraw any amount ≥ 4 (plus 0, 2, and 5 exactly).
This is a deductive system:
- Objects: The amounts you can withdraw (natural numbers)
- Axioms (Initial objects): 0, 2, 5 are “obtainable”
- Deduction rules: If amount
ais obtainable, thena+2anda+5are obtainable
Starting from these axioms and rules:
Start: 0, 2, 5 (axioms)
From 2: 4, 7 (+2, +5)
From 4: 6, 9 (+2, +5)
From 5: 7, 10 (+2, +5)
From 6: 8, 11 (+2, +5)
Pattern: 0, 2, 4, 5, 6, 7, 8, 9, 10, 11, ...
Missing: 1, 3 (can never be reached!)Once you have two consecutive obtainable numbers (like 4 and 5), you can keep adding 2 to both and get every number after that forever. Amounts 1 and 3 can never be produced — no combination of adding 2s and 5s to 0 ever lands on them.
The Language of Deductive Systems
| Term | Meaning |
|---|---|
| Objects | The universe of things we’re talking about |
| Axioms | Starting objects, assumed “deducible” without justification |
| Deduction Rules | Rules: “if you have X, you may deduce Z” |
| Deducible Object | Anything reachable from axioms via rules in finitely many steps |
| Derivation | The sequence of steps showing how an object was deduced — this IS the proof |
Key idea: “Deducible” = “reachable from axioms via rules in finitely many steps.” This formalizes the intuitive idea of “provable.”
Balanced Parentheses — A Beautiful Deductive System
Objects: Strings made from ( and ).
Axiom: The empty string ε is deducible.
Rules:
- Wrap: If S is deducible, then (S) is deducible.
- Concat: If S and T are both deducible, then ST is deducible.
Start: ε (axiom)
Wrap(ε): () → deducible
Concat((), ()): ()() → deducible
Wrap(()): (()) → deducible
Wrap(()()) (()()) → deducible
Concat((), (())): ()(()) → deducibleThis generates exactly the set of balanced parentheses strings. Not )(, not (() — only properly nested, properly matched strings.
Connection to binary trees: This system is structurally identical to defining binary trees recursively. Every balanced-parenthesis string corresponds to a unique binary tree, and vice versa. ( means “open a subtree,” ) means “close it,” concatenation means “siblings.”
The Balance Invariant — A Descriptive Characterization
There’s an entirely different way to characterize balanced parentheses:
A string S is balanced if and only if:
- Total balance = 0 (equal number of
(and))- For every prefix of S, the running balance ≥ 0 (never more closes than opens at any point left-to-right)
String: ( ( ) ( ) )
Balance: 1 2 1 2 1 0 ← always ≥ 0, ends at 0 → balanced ✓
String: ( ) ) (
Balance: 1 0 -1 ← drops below 0 → NOT balanced ✗This gives a checkable test instead of a constructive recipe. The deductive system tells you how to build balanced strings; the balance invariant tells you how to verify them.
Proving these are equivalent — that the constructive definition and the descriptive definition pick out the exact same set of strings — requires induction and is where the real mathematical content lives.
This is a pattern that shows up everywhere in CS and math:
Deductive system → CONSTRUCTIVE definition ("how to build it")
Invariant/test → DESCRIPTIVE definition ("how to check it")
Proving equivalence → usually requires inductionPart IV: Propositional Logic
The Five Connectives
| P | Q | ¬P (NOT) | P ∧ Q (AND) | P ∨ Q (OR) | P → Q (IMPLIES) | P ↔ Q (IFF) |
|---|---|---|---|---|---|---|
| T | T | F | T | T | T | T |
| T | F | F | F | T | F | F |
| F | T | T | F | T | T | F |
| F | F | T | F | F | T | T |
The tricky one is implication. P → Q is only false when P is true and Q is false. If P is false, the implication is vacuously true — “if pigs fly, then I’m the king of England” is technically TRUE, because pigs don’t fly, so the promise is never tested.
Formulas as a Deductive System
Well-formed formulas (WFFs) of propositional logic are defined exactly like balanced parentheses — as a deductive system!
Axioms: Every variable (P, Q, R, …) is a WFF.
Rules:
- If φ is a WFF, then (¬φ) is a WFF.
- If φ and ψ are WFFs, then (φ ∧ ψ), (φ ∨ ψ), (φ → ψ), (φ ↔ ψ) are all WFFs.
P ← WFF (axiom)
Q ← WFF (axiom)
(¬P) ← WFF (rule 1)
(P ∧ Q) ← WFF (rule 2)
((¬P) ∨ (P ∧ Q)) ← WFF (rule 2)Strings like P ∧ ∧ Q or (P ∨ ) are NOT WFFs — there’s no valid deduction sequence that produces them.
Tautology and Satisfiability
Tautology: A formula that is TRUE under every possible assignment of truth values.
Example: P ∨ ¬P (Law of Excluded Middle)
P ¬P P ∨ ¬P
T F T
F T T ← always TRUE → tautology ✓Another classic tautology: (P → Q) ↔ (¬Q → ¬P) — the contrapositive equivalence. This is why proof by contrapositive works — the two statements are logically identical.
Satisfiable: A formula where there exists at least one assignment making it TRUE.
Unsatisfiable: TRUE in zero rows. Example: P ∧ ¬P — impossible to make true.
The duality:
φ is a tautology ⟺ ¬φ is unsatisfiable
φ is satisfiable ⟺ ¬φ is NOT a tautologyWhy This Becomes a Big Deal
The brute-force way to check tautology or satisfiability: build the full truth table.
- n variables → 2ⁿ rows
- n = 20 → ~1,000,000 rows (doable)
- n = 100 → 2¹⁰⁰ ≈ more rows than atoms in the observable universe
This is the seed of the SAT problem — one of the most important problems in computer science and the canonical NP-complete problem. The question “is there a faster way?” is a modern descendant of the Entscheidungsproblem — but now the question isn’t “is it decidable?” (it obviously is — check all rows), but “how efficiently can it be decided?”
The Laws of Boolean Algebra
These let you mechanically transform formulas into equivalent forms:
De Morgan’s Laws (push negation through AND/OR, flipping the connective):
¬(P ∧ Q) ≡ (¬P) ∨ (¬Q) "NOT both" = "at least one isn't"
¬(P ∨ Q) ≡ (¬P) ∧ (¬Q) "NOT either" = "neither"Commutativity (order doesn’t matter):
P ∧ Q ≡ Q ∧ P
P ∨ Q ≡ Q ∨ PAssociativity (grouping doesn’t matter):
(P ∧ Q) ∧ R ≡ P ∧ (Q ∧ R)Distributivity (expand the brackets):
P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)
P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)Double Negation:
¬¬P ≡ PImplication rewrite (huge — converts → into ∨/¬):
P → Q ≡ ¬P ∨ QContrapositive:
P → Q ≡ ¬Q → ¬PWhy these matter: They show that {∧, ∨, ¬} — AND, OR, NOT — are enough to express ANY boolean formula. The connectives → and ↔ are just convenient shorthand. In fact, even just {NAND} alone is functionally complete — sufficient to build any boolean function.
Firstly, why {∧, ∨, ¬} is enough?
The claim is that → and ↔ are just shorthand — you can always replace them with AND, OR, NOT.
→ (implies) can be rewritten as:
P → Q is the same as ¬P ∨ QCheck it yourself — “if it’s raining, I’ll carry an umbrella” means the same as “either it’s not raining, or I’m carrying an umbrella.” Same thing.
↔ (if and only if) can be rewritten as:
P ↔ Q is the same as (P → Q) ∧ (Q → P)
which becomes (¬P ∨ Q) ∧ (¬Q ∨ P)So every connective reduces down to just AND, OR, NOT. You never actually need → or ↔ — they’re just convenient to write.
And secondly, why NAND alone is enough?
First, what is NAND?
P NAND Q = ¬(P ∧ Q)“Not both.” It’s true in every case except when both P and Q are true.
Now watch how you can build NOT, AND, OR purely from NAND:
NOT from NAND:
¬P = P NAND PNAND of something with itself. If P is true, “both true” so NAND gives false — which is ¬P. If P is false, “not both true” so NAND gives true — which is ¬P. Works perfectly.
AND from NAND:
P ∧ Q = ¬(P NAND Q)
= (P NAND Q) NAND (P NAND Q)AND is just NOT of NAND. And we already know how to do NOT using NAND.
OR from NAND:
P ∨ Q = (¬P) NAND (¬Q)
= (P NAND P) NAND (Q NAND Q)Using De Morgan’s law — NOT of NAND of NOTs.
So since you can build NOT, AND, OR purely from NAND — and since NOT, AND, OR can express everything else — NAND alone can express literally any boolean function.
This is actually why NAND gates are so important in real hardware. Chip designers can build an entire CPU using just one type of gate. Simpler manufacturing, same computational power.
Logical Entailment
A set of formulas φ₁, φ₂, …, φₙ entails ψ (written φ₁, …, φₙ ⊨ ψ) if: every assignment that makes ALL premises true ALSO makes ψ true.
This is the formal backbone of “valid argument.” Every line in a proof should be entailed by the previous lines.
Example — Modus Ponens:
Premise 1: P → Q (if P then Q)
Premise 2: P (P is true)
Conclusion: Q (therefore Q)Check: the only row where both premises are true is P=T, Q=T — and indeed Q=T there. Valid! ✓
Boolean Functions and Circuits
A boolean function of n variables maps n true/false inputs to one true/false output. A truth table is a boolean function.
There are exactly 2^(2^n) boolean functions of n variables:
n=1 → 4 functions (NOT, identity, always-T, always-F)
n=2 → 16 functions (AND, OR, XOR, NAND, NOR, IMPLIES, ...)A boolean circuit is the physical realization of a formula:
P ──┐
AND ── (P ∧ Q)
Q ──┘
(P ∧ Q) ────┐
OR ──→ output
(¬R) ────┘
Formula = symbolic/textual representation. Circuit = structural/graphical. They’re two faces of the same thing — and circuits are literally what’s inside a CPU.
Abstract logic (formulas, satisfiability)
↓
Physical computation (circuits, gates)
↓
Turing machines / algorithmsAll different “faces” of the same underlying notion of computation.
Part V: First-Order Logic — The Language of Mathematics
Why FOL?
Propositional logic only talks about fixed statements P, Q, R. It can’t express “for all numbers x…” or “there exists a string y such that…” First-order logic adds quantifiers (∀ “for all”, ∃ “there exists”) and lets you talk about objects, their properties, and relationships.
FOL is the language of essentially all real mathematics — Euclid’s axioms, Peano arithmetic, set theory.
Vocabulary: Constants, Functions, Relations
| Symbol Type | What It Represents | Example |
|---|---|---|
| Constants | Specific, named objects | a, 0, e |
| Functions | Operations: object(s) → object | Next(x), Combine(x, y) |
| Relations | Properties: TRUE or FALSE | IsPrior(x, y), = |
Crucial point: the vocabulary is just symbols with no fixed meaning. Next doesn’t inherently mean “+1.” What it actually means is determined by an interpretation.
Interpretations — Same Sentence, Different Truths
Remember FOL uses symbols like Next, Combine, a. But these symbols have no built-in meaning. They’re just names — like a variable in programming, x means nothing until you assign something to it.
So when you write:
∃x (Next(x) = Combine(a, a))You’re writing a sentence using words that mean nothing yet. It’s like writing:
"There exists an x such that BLOOP(x) equals FLOOP(a, a)"Completely meaningless until you decide what BLOOP and FLOOP actually do.
An interpretation is just you deciding what all those symbols actually mean. Once you decide, the sentence becomes either true or false.
To assign an interpretation you need to specify:
- A nonempty set
U— the universe (what kind of objects exist?) - What each constant name refers to
- What each function name actually does
- What each relation name actually tests
Worked example: Consider the sentence: ∃x (Next(x) = Combine(a, a))
In plain English: “there exists some x such that Next of x equals Combine of a with a.”
Three people look at this sentence and each decide the symbols mean something different:
Interpretation 1 — Binary Strings:
- Universe = all strings of 0s and 1s
a= the string1001Next(x)= stick a 0 at the end of xCombine(x,y)= join x and y together
So Combine(a, a) = join 1001 with 1001 = 10011001 — ends in 1. But Next(x) always ends in 0 no matter what x is. So there’s no x where Next(x) can equal something ending in 1. → FALSE
Interpretation 2a — Integers (ℤ):
- Universe = all integers (…-2, -1, 0, 1, 2…)
a= 0Next(x)= x + 1Combine(x,y)= x + y
So Combine(0, 0) = 0 + 0 = 0. We need Next(x) = 0, meaning x + 1 = 0, meaning x = -1. Is -1 an integer? Yes! → TRUE
Interpretation 2b — Natural Numbers (ℕ):
- Exactly the same as 2a, but Universe = {0, 1, 2, 3, …} — no negatives!
We still need x = -1. But -1 doesn’t exist in this universe. No valid x. → FALSE
Same sentence, three different truth values — purely based on what each person decided the symbols mean. This is exactly like propositional logic where P ∧ Q is true or false depending on what truth values you assign to P and Q — except now instead of just assigning T or F to variables, you’re assigning an entire universe with objects and functions to your symbols.
Tautology and Satisfiability in FOL
These generalize from propositional logic, but “assignment” becomes “interpretation”:
- Satisfiable: There exists some interpretation making it true
- Tautology (valid): Every interpretation makes it true
- Unsatisfiable: No interpretation makes it true
Critical difference from propositional logic: In propositional logic, you have a finite number of cases to check. Take P ∧ Q — P is either true or false, Q is either true or false, that’s it. 4 rows in a truth table. Done.
Now imagine trying to do the same thing in FOL. Take this sentence:
∃x (Next(x) = Combine(a, a))To check if this is a tautology you’d need to check every possible interpretation. But we just saw that interpretations can be:
- A universe of binary strings
- A universe of integers
- A universe of natural numbers
- A universe of real numbers
- A universe of… people? cities? colors? anything?
And for each universe, the symbols Next, Combine, a could mean completely different things.
There is no bottom to that list. You can never say “okay I’ve checked all possible universes.” Unlike propositional logic where you have 2ⁿ rows and you’re done, in FOL the number of possible interpretations is literally infinite — infinitely many possible universes, each with infinitely many ways to assign meaning to symbols.
So you can never just mechanically check all cases like a truth table. You have to construct an actual logical argument that works for every possible universe all at once. That’s what makes FOL so much harder than propositional logic.
A FOL Tautology Proof — Worked in Full
Sentence: (∃y ∀x (x = Next(y))) → (∀w ∀z (w = z))
First let’s just translate this into plain English. It’s an implication — an “if…then…” statement. Two parts:
- The “if” part: “There exists some y such that every object x equals Next(y)” — meaning every single object in the universe equals Next of some fixed y. The only way that’s possible is if the universe has exactly one element.
- The “then” part: “For all w and z, w equals z” — meaning every pair of objects are equal to each other. Again, only possible if the universe has exactly one element.
So the whole sentence is just saying: “if the universe has one element, then the universe has one element.” Which sounds obviously true — and it is. But we need to actually prove it.
Step 1: Show it’s satisfiable — find at least one interpretation where it’s true.
Pick: Universe = all integers, Next(y) = y + 1.
The “if” part says “there’s some integer y where every integer equals y+1.” That’s clearly false — no single integer equals all other integers.
Now remember from the truth table of →:
False → anything = TrueSo the whole sentence is True here. We found one interpretation where it’s true — it’s satisfiable.
Step 2: Show it’s a tautology — true under EVERY interpretation.
Let I be any interpretation. Any universe, any functions, anything. We don’t know anything about it. Two possibilities:
Case 1: The “if” part is false under I
Then we have False → (something). From the truth table that’s always True. Done.
Case 2: The “if” part is true under I
This means there really is some y where every single object in the universe equals Next(y). Every object equals the same single value. So all objects in the universe are equal to each other.
But that’s exactly what the “then” part says — every w and z are equal. So the “then” part is also true.
True → True = True. Done.
Both cases give True. Since I was literally any arbitrary interpretation, the sentence is True under every interpretation — it’s a tautology. ∎
Tarski’s Theorem — A Surprise Victory for Decidability
Remember Hilbert wanted all of math to be decidable — and Gödel/Turing proved it isn’t?
Here’s the twist: Alfred Tarski proved that the first-order theory of Euclidean geometry (equivalently, the theory of real closed fields) is decidable. There exists an algorithm that can determine whether any FOL sentence about geometry is true.
Hilbert (1900): "Math is decidable!"
Gödel (1931): Arithmetic → UNDECIDABLE, INCOMPLETE
DPRM (1970): Hilbert's 10th → UNDECIDABLE
↓
Tarski: BUT Euclidean geometry IS decidable!The dividing line: Can your theory talk about the natural numbers and their multiplication?
- YES → undecidable territory (Gödel, Turing, DPRM all bite)
- NO → you might get lucky, like geometry did
Euclidean geometry can’t express “x is a natural number” — it’s not powerful enough to encode integer arithmetic. That limitation is precisely what makes it decidable. The boundary between “what can be mechanized” and “what can’t” is subtle and depends on the theory’s expressive power.
Part VI: Set Theory, Infinity, and Cantor’s Revolution
What Is a Set?
A set is a well-defined collection of distinct objects. Notation:
{a, e, i, o, u}— the set of vowels∈means “belongs to”:3 ∈ {1, 2, 3}∉means “does not belong to”:5 ∉ {1, 2, 3}
Cantor’s Origin Story
Georg Cantor didn’t set out to invent set theory. He was working on a question in analysis: Is a Fourier series representation unique? A Fourier series represents a function as an infinite sum of sines and cosines:
f(x) = a₀ + a₁cos(x) + b₁sin(x) + a₂cos(2x) + b₂sin(2x) + ...If two different Fourier series produce the same function, must their coefficients be identical?
Cantor proved uniqueness holds even if the series disagree at finitely many points. He then pushed further — what about infinitely many exception points? He showed uniqueness still holds as long as the exceptions are “thin enough.” But to make “thin enough” precise, he needed to understand the structure of infinite sets of points.
This investigation snowballed:
Fourier Series → "Is the representation unique?"
→ What if it fails at some points?
→ Need to understand sets of exceptional points
→ What does it mean for a set to be "thin"?
→ How do you compare sizes of infinite sets?
→ SET THEORY IS BORN (1874)Set theory wasn’t born from abstract philosophy. It grew from a concrete problem in analysis.
Russell’s Paradox — The Bomb in the Foundation (1901)
In naive set theory, any rule defines a valid set. Bertrand Russell asked a devastating question:
What about R = “the set of all sets that do NOT contain themselves”?
Does R contain itself?
Case 1: R contains itself. → But R only contains sets that don’t contain themselves. → R should not contain itself. Contradiction!
Case 2: R does NOT contain itself. → Then R satisfies its own rule → R should be in R → R DOES contain itself. Contradiction!
No escape. Both cases explode. This is Russell’s Paradox, and it broke naive set theory.
The Barber Analogy: A barber shaves everyone who doesn’t shave themselves. Does the barber shave himself? Same paradox, different costume.
This forced mathematicians to rebuild set theory with strict axioms controlling what sets you’re allowed to create — leading to ZFC (Zermelo-Fraenkel with the Axiom of Choice).
Zeno’s Paradoxes — The First Brush with Infinity (~450 BC)
The Dichotomy: To walk across a room, you must first walk half the distance. But before that, a quarter. Before that, an eighth. Infinitely many steps… so how do you ever move?
Resolution — Infinite Series:
1/2 + 1/4 + 1/8 + 1/16 + ... = ?Call the sum S:
S = 1/2 + 1/4 + 1/8 + 1/16 + ...
2S = 1 + 1/2 + 1/4 + 1/8 + ...
2S = 1 + S
S = 1Not “approaching 1.” Not 0.999… It is exactly 1. Infinitely many terms, finite sum. The paradox dissolves.
Hilbert’s Infinite Hotel
A thought experiment showing how counterintuitive countable infinity is:
The hotel: Infinitely many rooms (1, 2, 3, …), ALL occupied.
One new guest arrives: Move everyone: Room n → Room n+1. Room 1 is now empty. Guest checks in. ∞ + 1 = ∞.
An infinite bus of new guests arrives: Move everyone: Room n → Room 2n (current guests go to even rooms). All odd rooms (1, 3, 5, 7, …) are now empty — infinitely many! Bus passengers fill them. ∞ + ∞ = ∞.
Infinitely many infinite buses arrive: Use a diagonal/zigzag assignment (same trick Cantor used for rationals). Every person still gets a room. ∞ × ∞ = ∞.
An uncountable crowd arrives: Every real number between 0 and 1 is a person. They DON’T fit. No matter how cleverly you rearrange, someone is always left out (by Cantor’s diagonal argument). This is where countable and uncountable infinity are fundamentally different.
| Scenario | Fits? | Why? |
|---|---|---|
| 1 new guest | ✅ | Shift everyone by 1 |
| ∞ new guests (1 bus) | ✅ | Move to even rooms, fill odds |
| ∞ buses × ∞ passengers | ✅ | Diagonal/zigzag pairing |
| Uncountably many | ❌ | Cantor’s diagonal argument |
Countable vs. Uncountable — The Full Story
A set is countable if you can pair every element with a natural number — you can list them 1st, 2nd, 3rd, … even if the list goes forever.
Natural Numbers ℕ: Obviously countable — they ARE the counting numbers.
Even Numbers: Feels like “fewer” than naturals, but:
1 → 2
2 → 4
3 → 6
n → 2n ← perfect pairing, nothing left over. Same size!Integers ℤ: Has all the negatives too — feels “twice as big.” But zigzag:
ℕ: 0 1 2 3 4 5 6 7 ...
ℤ: 0 -1 1 -2 2 -3 3 -4 ...Every integer gets a number. Countable!
Rational Numbers ℚ: Between any two rationals, infinitely more rationals exist. They’re dense. Surely there are more? Nope.
Walk the diagonals of a grid where row i, column j holds the fraction i/j:
1 2 3 4 ...
┌──────┬──────┬──────┬──────┐
1 │ 1/1 → 2/1 3/1 4/1 │
│ ↙ ↙ │
2 │ 1/2 2/2 3/2 4/2 │
│ ↙ │
3 │ 1/3 2/3 3/3 4/3 │
└──────────────────────────┘
Path: 1/1, 2/1, 1/2, 1/3, 2/2, 3/1, 4/1, 3/2, 2/3, 1/4, ...Every fraction eventually gets a position. Skip duplicates (2/2 = 1/1, etc.), and you’ve listed all rationals. Countable!
Real Numbers ℝ: Here’s where it breaks.
Cantor’s Diagonal Argument — The Proof That Changed Everything
Theorem: The real numbers between 0 and 1 are uncountable.
Proof: Suppose someone claims they can list ALL reals in [0,1]:
1st: 0. 5 1 4 8 2 6 ...
2nd: 0. 3 7 1 0 5 9 ...
3rd: 0. 8 2 6 3 4 1 ...
4th: 0. 1 9 0 7 2 8 ...
5th: 0. 4 4 3 8 9 5 ...
6th: 0. 6 1 7 5 0 3 ...
⋮Read the diagonal — 1st digit of 1st number, 2nd digit of 2nd number, etc.:
Diagonal: 0.5, 7, 6, 7, 9, 3, ...Now change every digit (e.g., add 1 to each, wrap 9→0):
New number: 0.6, 8, 7, 8, 0, 4, ...This new number is NOT on the list:
- Differs from the 1st number in its 1st digit (6 ≠ 5)
- Differs from the 2nd number in its 2nd digit (8 ≠ 7)
- Differs from the nth number in its nth digit — for every n!
No matter how cleverly you construct the list, the diagonal argument always produces a number you missed. Therefore: the reals cannot be listed. They are uncountable. ∎
| Set | Size | Type |
|---|---|---|
| Natural numbers ℕ | ℵ₀ (aleph-null) | Countable |
| Integers ℤ | ℵ₀ | Countable |
| Rationals ℚ | ℵ₀ | Countable |
| Real numbers ℝ | 𝔠 = 2^ℵ₀ | Uncountable |
Bijection, Injection, Surjection — The Toolkit
For a function f: A → B:
- Injective (one-to-one): Different inputs → different outputs. Each output hit AT MOST once.
- Surjective (onto): Every element of B is hit. Each output hit AT LEAST once.
- Bijective: Both. Each output hit EXACTLY once — a perfect pairing.
Injective only: Surjective only: Bijective:
A={1,2} B={a,b,c} A={1,2,3} B={a,b} A={1,2,3} B={a,b,c}
1 → a 1 → a 1 → a
2 → b 2 → a 2 → b
(c never hit) 3 → b 3 → c
(a hit twice) (perfect pairing)Cantor-Schröder-Bernstein Theorem: If there exists an injection A → B and an injection B → A, then |A| = |B| (a bijection exists). This is huge because injections are much easier to find than bijections.
Proving that the rationals ℚ have the same size as the natural numbers ℕ:
First, a quick reminder of what these symbols mean:
- ℕ = natural numbers = {0, 1, 2, 3, …}
- ℤ = integers = {…, -2, -1, 0, 1, 2, …}
- ℚ = rational numbers = all fractions like 1/2, -3/4, 7/1, etc.
We want to prove that ℚ is countable — meaning you can pair every rational number with a natural number, just like we did for integers and even numbers earlier.
The trick is we don’t prove it directly. We use results we already proved as stepping stones:
Step 1: Every rational number p/q can be represented as a pair (p, q) where p is an integer and q is a natural number. So ℚ fits inside ℤ × ℕ — the set of all pairs of (integer, natural number).
Step 2: We already proved ℤ is countable — same size as ℕ. So ℤ × ℕ is basically the same as ℕ × ℕ — pairs of natural numbers.
Step 3: We already proved ℕ × ℕ is countable using the diagonal grid walk from the rationals section — same size as ℕ.
So the chain looks like:
ℚ fits inside ℤ × ℕ
ℤ × ℕ is the same size as ℕ × ℕ
ℕ × ℕ is the same size as ℕ
Therefore ℚ is the same size as ℕ — countable!The point is that proving ℤ is countable and proving ℕ × ℕ is countable weren’t just fun isolated facts — they were Lego pieces that snap together to crack the ℚ problem almost for free.
Diagonalization on Binary Strings
Theorem: {0,1}^∞ (the set of all infinite binary strings) is uncountable.
Suppose you could list them all:
bit0 bit1 bit2 bit3 ...
s₀: [0] 1 0 1 ...
s₁: 1 [1] 0 0 ...
s₂: 0 1 [1] 1 ...
s₃: 1 0 0 [0] ...
⋮ ⋱Build d by flipping every diagonal entry: d_i = 1 - (s_i)_i
d = 1, 0, 0, 1, ...d differs from s_i at position i, for EVERY i. So d is not on the list. Contradiction! ∎
Since every real number in [0,1] has an infinite binary expansion, {0,1}^∞ corresponds to [0,1]. So |[0,1]| = |{0,1}^∞| = |ℝ| = 𝔠, and ℵ₀ < 𝔠.
The Axiom of Choice and the Banach-Tarski Paradox
The Axiom of Choice says: given any collection of non-empty sets, you can pick exactly one element from each, even if the collection is infinite.
Sounds obvious. The controversy is with infinite collections where you can’t specify a rule for choosing.
- Easy case: “From each set of natural numbers, pick the smallest.” Clear rule, no problem.
- Hard case: “From each set of real numbers, pick one.” What rule? There’s no “smallest” in every set of reals. The axiom says the choice exists without saying how.
The Axiom of Choice is required for the Banach-Tarski paradox. Without it, you can’t construct those bizarre non-measurable pieces that let you duplicate a ball. This is one of the main reasons some mathematicians reject it — but without it, large parts of modern mathematics break down.
The Cantor-Kronecker War
Cantor’s claims — that infinity comes in sizes, that actual completed infinities are mathematical objects — were radical. Leopold Kronecker, the most powerful mathematician in Germany, waged war against Cantor:
“God made the integers, all else is the work of man.” — Kronecker
Kronecker believed only natural numbers are “real” mathematics. He called Cantor a “corrupter of youth” and a “charlatan”, blocked his papers from publication, prevented him from getting a position at Berlin, and publicly mocked his work.
The attacks destroyed Cantor. He suffered repeated mental breakdowns, was hospitalized multiple times, and died in 1918 in a sanatorium — poor and broken.
But Cantor won. David Hilbert championed his work, declaring: “No one shall expel us from the paradise that Cantor has created.” Today, set theory is the foundation of ALL modern mathematics. Every branch — algebra, analysis, topology, logic — is built on Cantor’s ideas.
Part VII: The Grand Unification — Most Problems Are Unsolvable
Here’s the killer punchline that ties everything together.
First, a key insight: countability and algorithms are the same thing. A set is countable if and only if you can write an algorithm that lists its elements. Every example we saw — the zigzag for integers, the diagonal walk for rationals — was literally just an algorithm written out as a picture.
Now we’re going to count two things and compare them.
How many programs exist?
A program is just a finite string of code. Characters typed on a keyboard, saved to a file. So every program is a finite binary string under the hood.
We can list all possible programs the same way we listed all finite strings — all 1-character programs, then all 2-character programs, then all 3-character programs, and so on. This list goes on forever but every program eventually appears on it.
So the set of all possible programs is countable. ℵ₀ programs total, ever, across all of history and all possible future computers.
How many problems exist?
A problem is just a question with yes/no answers. Something like “is this number prime?” or “does this program halt?” For every possible input you feed in, the answer is either YES or NO.
So a problem looks like an infinite checklist:
Input 1 → YES
Input 2 → NO
Input 3 → NO
Input 4 → YES
Input 5 → YES
⋮Which is just an infinite binary string — YES=1, NO=0. And we just proved that the set of all infinite binary strings is uncountable. 𝔠 problems total.
The comparison:
ℵ₀ programs < 𝔠 problems
(countable) (uncountable)There are strictly more problems than programs. Not a little more — incomparably more. The same way there are incomparably more real numbers than natural numbers.
Think of it like trying to match them up — every program gets assigned to the problem it solves. But we have uncountably many problems and only countably many programs. Most problems will never get a program assigned to them. Not because we haven’t found the right program yet — but because there simply aren’t enough programs to go around.
Almost every problem that exists has no program that solves it. The solvable problems — the ones with algorithms — are a tiny, vanishingly rare island in an ocean of unsolvable ones.
And we proved this with zero cleverness. Just counting.
One Trick, Three Costumes
Notice the shape of these proofs:
Cantor (1891): "Suppose all binary strings are listed"
→ diagonal flip → a string NOT on the list
Gödel (1931): "Suppose all provable statements are listed"
→ diagonal trick → a true-but-unprovable statement
Turing (1936): "Suppose a halt-decider H exists"
→ diagonal trick → a program H can't decideThe same proof technique wearing three different costumes. This is arguably the single biggest unifying idea of the entire course: Cantor’s diagonalization, Gödel’s incompleteness, and Turing’s undecidability are all the same argument.
The Continuum Hypothesis — Where the Story Leaves Off
We’ve shown that ℵ₀ (the size of natural numbers) is strictly smaller than 𝔠 (the size of real numbers). Natural question: is there anything in between? Some infinite set bigger than ℕ but smaller than ℝ?
Cantor believed no — every infinite set is either ℵ₀-sized or 𝔠-sized, with nothing in between. This is called the Continuum Hypothesis, and it was literally Hilbert’s Problem #1 — the very first problem on his famous list of 23.
First — what is ZFC?
Remember how we said all of mathematics needs to start from axioms — basic rules you accept without proof, like the rules of a board game? ZFC is that rulebook for modern mathematics.
ZFC stands for Zermelo-Fraenkel set theory with the Axiom of Choice — named after the mathematicians who wrote it down. It’s a set of about 9 fundamental rules about how sets work, and essentially all of modern mathematics — algebra, geometry, analysis, everything — is built on top of these 9 rules.
When mathematicians say “proven” today, they almost always mean “proven from ZFC.”
The jaw-dropping resolution:
- Gödel (1940): proved that you cannot disprove the Continuum Hypothesis using ZFC. It doesn’t contradict the rules.
- Cohen (1963): proved that you cannot prove the Continuum Hypothesis using ZFC either. It doesn’t follow from the rules.
Together this means the Continuum Hypothesis is completely independent of ZFC — it is genuinely neither provable nor disprovable from mathematics’ standard foundations. You can add it as an extra axiom and math still works fine. You can add its opposite and math still works fine. The rulebook simply cannot settle the question either way.
Hilbert’s very first problem turned out to be a living, breathing example of exactly the incompleteness that Gödel proved doomed Hilbert’s entire program.
The Big Picture
HILBERT'S DREAM (1900–1928):
"Mathematics can be made complete, consistent, and decidable"
|
↓
┌─────────────────┼────────────────┐
↓ ↓ ↓
Complete? Consistent? Decidable?
| | |
GÖDEL 1931 GÖDEL 1931 TURING 1936
| | |
NO. CAN'T PROVE. NO.
| | |
↓ ↓ ↓
True things Math can't No algorithm
you can't verify its can solve all
prove own sanity math problemsMathematics — the most rigorous discipline humanity has ever created — has proven limitations on what it can do. These limitations aren’t temporary gaps in our knowledge. They’re fundamental and permanent, built into the fabric of logic itself.
And in proving these limitations existed, Gödel, Church, and Turing gave us something incredible in return: the entire field of computer science.
Some Famous Open Problems (Bonus)
| Problem | Year Posed | Status | Prize |
|---|---|---|---|
| Goldbach’s Strong Conjecture | 1742 | ❌ Unsolved | — |
| Twin Prime Conjecture | ~1849 | ❌ Unsolved (gap reduced to 246) | — |
| Riemann Hypothesis | 1859 | ❌ Unsolved | $1,000,000 |
| Continuum Hypothesis | 1878 | Independent of ZFC | — |
| Collatz Conjecture | 1937 | ❌ Unsolved | — |
Goldbach’s Strong Conjecture: Every even number > 2 is the sum of two primes. Tested up to 4 × 10¹⁸. Always works. Still unproven after 284 years. (The weak version — every odd number > 5 is the sum of three primes — was proven by Helfgott in 2013.)
Twin Prime Conjecture: Are there infinitely many prime pairs that differ by 2 (like (3,5), (11,13), (17,19))? In 2013, Yitang Zhang proved there are infinitely many pairs with gap ≤ 70,000,000. The Polymath project reduced this to 246. Getting from 246 to 2 remains open.
Abel-Ruffini Theorem: There’s no general formula (using +, −, ×, ÷, and roots) for solving polynomials of degree 5 or higher. Abel (died at 26 of tuberculosis) and Galois (died at 20 in a duel — his frantic notes the night before founded Group Theory) proved this.
Poincaré Conjecture: Every closed 3D shape where any loop can be shrunk to a point is topologically a sphere. Proven by Grigori Perelman in 2003, who then declined both the Fields Medal AND the $1,000,000 Millennium Prize, saying “I’m not interested in money or fame.”
That’s Lectures 1–5 of CS 15-251. We went from Hilbert’s dream of a perfect mathematical machine, through Gödel’s bombs, Turing’s Halting Problem, the invention of formal logic, and Cantor’s discovery that infinity comes in sizes — all the way to the proof that most problems are fundamentally unsolvable.
And the craziest part? All the biggest results — Cantor, Gödel, Turing — use the exact same trick: diagonalization.
One trick. Three revolutions. An entire field of science born from the ruins of a dream.