What A General Diagonal Argument Looks Like (Category Theory)

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
with inspiration from this motivating paper by Yanofsky

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

[Thricery]

====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

[venividi]

Bruh, how can you make one of the very best math explainer videos on youtube and then just stop!? Can you imagine how disappointed I was to finish this video and go to your page to start watching them all?

[frantiseknavrkal]

Thinking about category theory as the linguistics of mathematics is a big breakthrough for me. I think this might be the best introduction to category theory I have seen so far. Could you make videos exploring more of category theory from this perspective?

[kesleta]

This is the best introduction to category theory I've ever seen. It managed to actually motivate category theory for me. Calling it the "linguistics of mathematics" was a really clever metaphor.

[jamesmstern]

This video is a shining example of clarity.

[TheDoh]

That second version of Cantor's proof made it finally make sense to me, i've seen it explained countless times before but i've never felt it was rigorous enough. Awesome video!

[jacoblojewski]

This was a really cool view of diagonal arguments that I'd never seen before. I really like the (new to me) view that diagonal functions enable self reference! And everyone knows self-reference opens to door to all sorts of contradictions, so it makes perfect sense in hindsight!

[luketyler]

That was an amazing video! I had an intuitive feeling in the back of my head that those proofs were similar, but this really opened my eyes

[AlonAltman]

I really love this video. Cantor's diagonal and the simple halting problem proof you described are my two favorite proofs in math, and it's really nice to see how well they fit together. In fact, I thought about making a SOME2 about one or both of those, but you've done it better than I ever could, so congrats!

[michaelzumpano]

That was a powerful intuitive explanation of the diagonal argument. I’m glad you didn’t stop there. I’m glad you did the math after giving us the aerial view. Subscribed.

[alejrandom]

4:03 the way you lay it out in such a way that it already remembers of the barber's paradox...

[johnchessant]

Very neat perspective! I knew about the diagonal argument and the various self-referential paradoxes separately and never thought they were actually instances of the same concept

[ajl]

This is probably the best math video I've ever watched! Really added a lot to my understanding of diagonal arguments and category theory.

[AlhunAydin]

Amazing quality stuff! Finally someone lucidly shows the path from diagonal argument (Cantor) to the fundamental limitations of math (Gödel), comp. sci (Turing) and philosophy/language (Liar's & Russell)! Brain orgasm, literally! 🥳

[fireclub]

Really beautiful and intuitive explanation of how the capability for self reference relative to a base set like {0, 1}, {halts, doesn’t halt} etc. leads to the non-existence of functions that describe everything you care about (infinite binary seqs, programs/data) in terms of that base set. Like, if the the collection of things you’re trying to describe via some property is TOO expressive, through being able to refer to itself having the property you care about, it can actually prevent you from having any hope of describing everything in terms of that property at all! Kinda feels like someone trying to run a classification algorithm and ending up having data points that lie directly ON your decision boundary, rather than on either side.

[IustinThe_Human]

amazing insight between those seemingly distant concept

[laukei]

probably the best intro to what's great about the categorical point of view I've ever seen.
kudos for your fantastic work.

[lexinwonderland]

what a brilliant comparison with language!! i love seeing overlaps like that. keep up the great work!!

[kartiksunaad]

Oh man, I liked this video so much that I hit a like from all my google accounts. Really great work!

[ThingsToSay]

This is an excellent video! I think this kind of application of category theory to make sense of key concepts in mathematics and logic is the best use for it - using abstraction to show (just) the important stuff is exactly what cats should be for! Bravo, and I'm looking forward to more!