Diagonal Arguments are a powerful tool in maths, and appear in several different fundamental results, like Cantor’s original Diagonal argument proof (there exist uncountable sets, or “some infinities are bigger than other infinities”), Turing’s Halting Problem, Gödel’s incompleteness theorems, Russell’s Paradox, the Liar Paradox, and even the Y Combinator.
In this video, I try and motivate what a general diagonal argument looks like, from first principles. It should be accessible to anyone who’s comfortable with functions and sets.
The main result that I’m secretly building up towards is Lawvere’s theorem in Category Theory.
[https://link.springer.com/chapter/10.1007/BFb0080769]
with inspiration from this motivating paper by Yanofsky.
[https://www.jstor.org/stable/3109884].
This video will be followed by a more detailed video on just Gödel’s incompleteness theorems, building on the idea from this video.
====Timestamps====
00:00 Introduction.
00:59 A first look at uncountability.
05:04 Why generalise?
06:53 Mathematical patterns.
07:40 Working with functions and sets.
11:40 Second version of Cantor’s Proof.
13:40 Powersets and Cantor’s theorem in its generality.
15:38 Proof template of Diagonal Argument.
16:40 The world of Computers.
21:05 Gödel numbering.
23:05 An amazing program (setup of the Halting Problem)
25:05 Solution to the Halting Problem.
29:49 Comparing two diagonal arguments.
31:13 Lawvere’s theorem.
32:49 Diagonal function as a way for encoding self-reference.
35:11 Summary of video.
35:44 Bonus treat — Russell’s Paradox.
CORRECTIONS
21:49 — I pronounce “Gödel” incorrectly throughout the video, sorry! Thanks to those who have pointed it out.
- Let me know if you spot anything else!
Leave a reply