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!
This video has been submitted to the 3Blue1Brown Summer of Maths Exposition 2
#some2 #mathematics #maths