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.