Level 8: The limits of logic

Logic and puzzles · level 8 of 8 · rough age 17 and beyond (a guide for parents; anyone can start anywhere)

In level 7 you learned how proofs work. In this level you turn logic on itself: what exactly can be said in symbols, what we must assume before we prove anything, and what proof and computation can never do. You meet the discoveries of the early twentieth century that changed mathematics: Russell's paradox, Gödel's incompleteness theorems and Turing's halting problem. The level ends with the most famous open question in computer science.

Lesson	You will be able to
Predicate logic	Translate statements about objects into symbols with \(\forall\) and \(\exists\), and negate complicated statements step by step
Axioms	Explain Euclid's postulates, why changing the parallel postulate gives new geometries, and how the Peano axioms build the whole numbers
Russell's paradox and sets	Follow Russell's paradox, explain why "the set of all sets" causes trouble, and say how careful axioms avoid it
Gödel's incompleteness theorems	State what Gödel proved about consistent systems for arithmetic, sketch the idea, and say what it does not mean
Turing and the halting problem	Explain in plain words why no program can decide for every program whether it stops
P versus NP	Tell checking an answer from finding one, recognise problems in NP, and explain what the open question asks

Previous: Level 7: how a proof works · This is the last level. · Logic topic page