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

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?

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.

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?

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!

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!

This video is a shining example of clarity.

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

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!

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

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

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! 🥳

amazing insight between those seemingly distant concept

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

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.

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

This was actually pretty mind blowing. One of those concepts that are extremely deep and powerful but once someone explains it to you in a pedagogical sense it feels so intuitive and simple like it is something that should have been obvious all along. Amazing video, my brain will never be the same again.

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.

I love the way you motivate the proof of the halting problem. It's really surprising to see the similqrities with th classical diagonal argument!

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!

I'm late to the party here, but damn... this video is _criminally_ underexposed. A terse yet lucid illumination of a delightful, profound, and easily missed common thread. Bravo.

OMG, i'm so happy to find this (through 3b1b), for years i've been wanting to dig into this puzzling aspect of math/ reality but didn't have the skills necessary, it always felt to me like a trick in the worst case, or an obvious observation about axioms and foundations of knowledge in the best case (especially thinking of Godels incompleteness theorems, and their implications). I am "almost literally" dying to see your next lesson/ "take" on the matter, CAN"T WAIT!! :)

Great stuff! I've encountered many of these things before and always had a sense that they were connected somehow, but never had the confirmation and clarity you provide here. I love that KZfaq's index for your video ends with "cc" which reminds me of C compilers and quines and Ken Thompson's paper "Reflections on Trusting Trust". What a fertile area for thought this is. Anyway, please do make more videos; I will certainly watch!

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

Thank you! Your video shows fantastically the actual practical usefulness of category theory, which is something I never saw before.

This KZfaqr discovered this one trick, see why mathematicians hate him.

What a journey! We went from counting to computation to turing!

As fine an explanatory video of a complex topic as I've ever seen. And, as another commenter said, a great intro to category theory.

I can't believe I only now came across this video, it is the absolute best and most comprehensive explanation of diagonal arguments out there, from beginning to end. I truly hope more videos are in the making!

Great and brilliant video! I'm just become a fan of yours, I respect your times but please for all humanity don't leave KZfaq.

I love videos that let me see things in a whole new light. I've studied all the examples here but never considered their relationships.

19:36 It's possible to work with a kind of set theory where every partial function is computable, so the correspondence between programs and partial functions is perfect. In particular, if ZF is Π¹₁-consistent, then there is a computable model of ZF. Slightly less-abstractly and more-practically, in computability theory, one can define a near-equivalent to partial functions called computable functions that corresponds to programs exactly.

(I know this is pretty silly of me, but I'm just commenting to say that I just so happened to be the 1000th person to like this! It most definitely deserved it.)

Beautiful presentation of a beautiful concept. Bravo! Bahut atchah! 😃

I love lawvere's fixed point theorem and I'm glad someone is talking about it. I wrote a formalization of it in agda if you have any interest

I was learning Haskell programming language and was delighted to see many terms I've already seen there applied in maths (where they originally come from, actually)

Here's a solution to Russell's paradox using verbs and relative order, though in this case the order isn't between verb and object but between the actions denoted by repeated occurrences of a given verb. The set R includes all and only those sets which do not include themselves. The verb "include" occurs twice, and though here it's written in the same grammatical tense, usually known as the present simple, it denotes actions which in fact are performed in sequence since they are uttered in sequence. What sequence that is becomes clear when we use explicit grammatical tenses: R includes all and only those sets which didn't include themselves, (or R included all and only those sets which don't include themselves). To make it even clearer we could add in adverbial time markers: R includes now all and only those sets which didn't include themselves before. This parallels the famous barber version: The barber shaves now all and only those men who didn't shave themselves before. Contradiction gone once we make a distinction between tenses. There's already a precedent in elementary arithmetic. 2 + 3 * 4 = 14 or 20? Solve this by explicitly marking the sequence of operations we want, in this case perhaps by using brackets or a convention like PEMDAS.

At 13:00 the contradiction is much more satisfying than the first proof. The first proof has that feeling of doubt that you just haven't looked far enough. But the second proof says if somebody tries to tell me that my S is in b, I can ask well where is it? What's k? Then I can look there and prove them wrong.

Well done. I watched the whole video. Very interesting. I guess this is an example of a meta level of thinking. I will need to watch it again and do some practice before I claim to fully comprehend but it was very interesting and intriguing.

This is such an excellent video, it's a real shame it doesn't have more views!

Thank you for this beautiful, mind expanding presentation!

This is the best introduction to category theory for making proofs I have seen. Superb video sir!

This was very well explained and illustrated, kudos to you!

👏 excellent, I love category theory and this is an awesome introductory exposition.

Well done! Many thanks for your clear inside into the background of category theory.

Wow, that was brilliant. Beautifully explained the link between many fundamental results 🙂

Great great video. Looking forward to the next one about Gödel's theorem.

Very cool video ! I'm waiting for your video on Lawvere's fixed point theorem, and hopefully a bit of topos theory, which is really at the heart of all you're explaining. As an algebraic geometer, I'm used to see a topos as some kind of "space", but seeing these results which are more on the logical side of the theory is always a pleasure. Perhaps one day logic and type theory will give us a purely syntactic approach to these objects, model-independant, which will surely be useful in (higher) topos theory.

Can't wait for the follow-up video on Gödels incopleteness theorem :)

This is amazing. Applications of Category Theory are so cool

The hand waving about the 17th entry on the list is actually proves that you cannot have a list of infinite list and be able to enumerate them because there is no way to compare them. They have no end so no matter how many digits in the list you compare you can never say you have compared them all so there is no way any recursive algorithm can be designed that will answer the question are two infinite series the same series

Masterful presentation!!!

For the first example, I came up with a "counterexample"-- Write down each number, essentially "incrementing" from left-to-right in binary: .1000000... .0100000... .1100000.... .0010000... .1010000... Then if you apply the diagonalization, you get the number .00111111111... which is equal to .01, the second number on the list. (This is like the .9999..=1 thing, but for binary.) It's not a real counterargument, but is a case where the diagonalization argument fails (the diagonalization argument just needs any case where it works).

12:00 - Visually, this really looks like asking if every f: N --> {0, 1} is "representable", in the sense of Yoneda. Of course, it's not literally asking that because N doesn't have the necessary categorical structure, but I wonder if it's possible to construct a category with objects indexed by N whose Hom-sets encode L. Awesome video!

This was incredible! Thank you so much :)

Excellent video, really enjoyed it. Eagerly waiting for the continuation on Godels incompleteness theorems :)

Linguistics example really was great

Incredible! Fantastic job :)

Great analysis

Excellent. I look forward to your presentation of Godel's incompleteness theorems.

great stuff! and thank you for the links

No Y combinator? That's my favorite one...

This was very intructive and to the point. At the same time, it was vivid and descripive without any graphical animation tools - respect! The only thing I'd like to recommend to get an even better presentation, is to improve your sound recording system ...

LINGUISTS of MATH! so neat

Excellent explanation 👌

Amazing video!

Great video. Impatient for the Godel follow-up. Any chance that such a categorical explanation could be given for the forcing argument?

That was so satisfying!

Take all my money this is KZfaq gold

This is fantastic

Good work!

Wow. A new math channel. Interesting.

you were mentioned .. caught my interest .. will watch but not on a saturday night.

Its a really nice video!

This is a very strong video

Excellent video, really like it. Would really love to hear your ideas about what the pattern itself "means" :) And looking forward for the Godel theorem video.

Well done

4:37 it's cool to see how the diagonalization argument subtley uses the axiom of choice, which we just take for granted.

Waiting for the second part

Excellent video! Hopefully #SoME2 will give it the exposure it deserves. It almost makes category theory seem useful. The question remains however, has Lawvere's theorem ever been used to prove things (outside Category Theory itself), or has it only ever been used to show _a posteriori_ that the proofs were similar? That is, has it been useful in mathematics, or is it just clever hindsight?

Small point: to translate from a sequence of 0s and 1s to a number, you should place a 1 in front of it so that leading zeros don't get deleted. Every (nonzero) binary number begins with 1, so this is bijective onto those.

Amazing vid man! +1 sub :)

Infinite was not defined. Assume there are countably infinite digits in a sequence. Then all the sequences are listable and the diagonal argument fails. If there are n digits in a sequence, there are 2^n sequences, for all n. Example: two digits in a sequence 1) 00 2) 01 3) 10 4) 11 The diagonal number is 10, which is in the list. A real number in [0,1) can be represented by a sequence of digits, finite for a rational number and countably infinite for an irrational number. Hence the real numbers are countable.

brilliant video, may I ask how this is related to the Y combinator?

Lawvere’s theorem helps explain why character theory with the trace (diagonal) function is important with representation theory.

Very excellent video! Great presentation with clear and concise examples that intuitively correlate to the concept being explained! Please invest in a pop filter and highpass your narration at ~150Hz.

Damn man really good stuff, we were recently doing a real ana;ysis course and it always bugged me why we had to formalize a function for cantor diagonalization as i thought of it to be of little importance.

This video was so good, even though I was familiar with the different examples for diagonal argument the generalization gave it all a new perspective and looking at the argument as function composition is really cool. I had a thought after watching it, is there a famous diagonal proof where the set of values has more than two values?

5:06 "Why? Why do this?" me rn

This is Artificial Intelligence in synthesis, and a conglomeration of symbolic, imagined discrete, temporally displaced if you accept that past-future superposition is distance not centred on the real-time wave-package envelope-shaping time-timing sequence tuning of the Observer's POV. An example of thinking for your self in Self, Theoretically, shape shifting i-reflection actual arrangements of ONE-INFINITY.

Great video, thanks. Please make more content on Gödel's theorem. There is a niche for this type of video on youtube, I think you could be very successful :)

I disagree with the diagonal argument: Register size of 1 bit contains 1,0. Both 1 and it's opposite 0. Register size 2 contains these previous numbers with 0's prepended: 01,00. But also, their diagonal opposite exists within a 2 bit register: 11,10. Register of 3 bits contains all previous numbers with 0's prepended: 000,001,010,011. And when we generate all possible diagonal selections of all combinations of any three of these, we obtain these new 'opposites': 100,101,110,111 Register of size N contains all binary combinations of numbers of bit size N and ALL combinations of diagonals of that size of register. If the register leads off to infinity, as do the integers, then the register fits all numbers and their opposites by any diagonal that can be created within it.

Very interesting video, thank you ; awaiting the upcoming ones ! Is it possible to use bolder pen for drawings ? Sometimes they are not very legible on a mobile phone (depends also on color).

Why do you need to specify that countability means the ability to enumerate a set's members one at a time? Are there uncountable sets that can be exhaustively represented if their members are enumerated all at once? Looking forward to the Godel video!

A small note on the proof of the uncountability of infinite binary sequences: You don't actually need a proof by contradiction here. Here's how I'd write the proof (without making any assumptions on the cardinality of *B* ). [Since it's not easy to type a script-B in the comments, I'll just denote the set of infinite binary sequences by *B* .] *Theorem.* The set of infinite binary sequences is uncountable. *Proof.* Let f: ℕ -> *B* be a function. Now, define an infinite binary sequence b by b(n) = 1-f(n) (where, here, b(n) denotes the nth term in the sequence). Then, for all n in ℕ, b(n) is not equal to f(n), so it is not in the image of f. Since f was arbitrary, no such function will ever be a bijection, and so *B* cannot be countable. *QED* The proof, itself, is mostly identical, but I feel like the framing makes things a little bit more awesome. Rather than getting some sequence b as an artifact of a faulty assumption, what we've actually shown is an explicit construction of a "new" sequence from an old one. In a sense, this feels like two different results, so I would actually write this a little bit differently: *Lemma.* Given any countable subset A of *B* , we can construct an element b of *B* that is not in A. [The construction given above -- just define any function f: ℕ -> *B* which has A as its image.] *Theorem.* The set of infinite binary sequences is uncountable. [Follows by noting that there's always a missed element for any f: ℕ -> *B* , hence such a function is never onto/surjective.] Whenever I call something a proof by contradiction, I always like to make sure it actually needs to be framed that way. There are certainly theorems for which a proof by contradiction is needed (or proofs that are by contradiction that require less knowledge than their direct counterparts), but I find that I can usually save on writing by removing the lines at the beginning and end of "Suppose [theorem] is false. . . . [proof] . . . This contradicts our assumption" whenever "[proof]" is actually all we needed. Here's another theorem that's often framed as a proof by contradiction, but is actually the same "given x, construct y, therefore z" paradigm: *Theorem.* There are infinitely many prime numbers. I like to break the proof up into two pieces: *Lemma.* Given any finite set of primes, we can construct a new prime not in that set. *Proof.* Let p(1),..., p(k) be primes. Consider n = p(1)...p(k) + 1. Since none of the primes we're considering can divide n, there must be a prime factor of n that is not among p(1),...,p(k). *QED* *Theorem.* There are infinitely many prime numbers. *Proof.* By the lemma above, given any finite set {p(1),..., p(k)} of prime numbers, there is a prime number that isn't included. Therefore, there are infinitely many prime numbers. *QED* Note: You could write the lemma's proof with the theorem's proof together for a single proof, but I like having them separated, because we can rewrite the proof of the theorem in a more "computational" way. *Alternative Proof.* By the lemma above, starting from a set {p(1),..., p(k)} of prime numbers, we can iteratively build larger sets by adding in the new prime constructed at each step. Since this iterative process will never stop, this will give an infinite subset of all primes. Therefore, there are infinitely many prime numbers. *QED* I actually prefer this way of framing the proof. It's like we've built an abstract computer that we've programmed using mathematics. In fact, you could even say that Euclid programmed the first published algorithm for computing an infinite set of prime numbers!

I feel so guilty being alive at a time when information like this is just freely available. People in the past would've killed for an education like this, and I'm just getting it for free.

Very enjoyable video. But, if you find working at this abstraction level, do some programming and formal verification in Haskell. This level of abstraction will start feel natural after a while.

Normally I have to speed up videos to not get bored/distracted. This one I had to slow down...

27:30 Doesn't the k used as input into k, also need an input? And so on?

I have a question. Our function L somehow acknowledges that there in fact is a listing of all posible 0 and 1 lists, because there they are, just input a certain k and you get the list b_k(-)=L(k,-). However, we prove that there is some list b that is not listed by any k, so doesn't this prove that L cannot exist as a function such that L(k,m) gives the mth element of the kth list of infinite sequences in the first place?