What A General Diagonal Argument Looks Like (Category Theory)

[@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

[@umbraemilitos]

I would love more videos like this if you get the time and interest.

[@venividi2940]

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?

[@Achrononmaster]

Give the dude some money... bruh. If they're not getting paid an academic salary it's up to the rest of us to keep the support up.

[@mscottveach]

@@Achrononmaster give me a way to do it, and I would. but the truth is that there's already an incredibly solid business model built into youtube. make videos this good. build audience. turn ads on. start a patreon. make good solid side-hustle money.

[@kesleta7697]

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.

[@TheDoh007]

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!

[@frantiseknavrkal2958]

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?

[@Thricery]

Thanks for the kind words! I am working on a follow up to this video on Gödel's Incompleteness Theorems (viewed through the same lens). I hope the comparisons to linguistics in that and other future videos would scratch the same itch!

[@ThingsToSay654]

That was actually how I first got started looking into category theory! David Spivak wrote a great article called "Category Theory as Mathematical Models" covering some of that idea, and I would definitely recommend it (as well as the rest of his work on applied category theory)

[@icxcarnie]

I never heard that analogy before, very interesting!

[@umbraemilitos]

@@Thricery I would also love for you to continue this series. Concrete applications of Category Theory really help bridge the gap to the abstraction at a pedagogical level.

[@ismayonnaiseaninstrument8700]

Well, that would explain why it interests me.

[@jacoblojewski8729]

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!

[@luketyler5728]

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

[@onion013]

Yaaay category theory!

[@anhhoanginh4763]

@@onion013 Woops, 1 year later but no new video!

[@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!

[@alejrandom6592]

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

[@johnchessant3012]

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

[@kazedcat]

I know they are related somehow because all of them involve a flipping function. But I did not know that this relatedness is rigorously express in category theory.

[@ajl2346]

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

[@laukei1]

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

[@jacobusburger]

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

[@TheMorMor]

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.

[@ThingsToSay654]

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!

[@jovangerbscheid4619]

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!

[@petervillano3484]

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.

[@kartiksunaad]

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

[@punditgi]

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

[@PanCholec]

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

[@datamoon]

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 KZbin'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!

[@MyAce8]

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

[@jessejordache1869]

I'm busy trying to wrap my puny brain around Y-combinators in a practical way, since in recent years they've gone from a functional language curiosity to a way to wrestle compilers into tail-call optimization-like behavior whether they're spec'ed for it or not (what blew me away was following a tutorial to write factorial in javascript, ending in a Z combinator, the moment when I began typing out the command to give me 25!, as soon as I closed the parentheses the IDE spat the answer out on the next line. I was like "aren't you supposed to wait for me to execute this?" but to increasingly intelligent editors which anticipate your input, they had already stacked 25 copies of my function on top of each other before I formally ran the program). Since I'm not even close to understanding the gestalt of them, I'm scratching my head about questions like "what is the fixed point of merge sort?". So I'd be interested. Unlikely I will understand it though.

[@upublic]

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!! :)

[@TIO540S1]

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.

[@brothberg]

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.

[@chrisg3030]

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.

[@kyay10]

Time doesn't really "exist" in mathematics though. A formal sense of such timing would introduce a lot more complexity. Nevertheless, there is a similar things that mathematicians do where, I think in some typed lambda calculi, they have a time Omega_0 whose elements are all types that aren't itself, and a type Omega_1 whose elements are Omega_0 and the elements of Omega_0, and so on for Omega_N, and hence in each step you can never have a statement about Omega_n inside itself, you can only talk about it within Omega_n+1. A similar thing, as you mention, happens with order of operation, but in this case it's a wildly different thing where it's not the language that is ambiguous, it's the statement itself that is contradictory. What it leads us to do, regardless, is to reconsider the rules of the system and limit it.

[@postmodernist1848]

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)

[@Tbojac]

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.

[@WWLinkMasterX]

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

[@brownnailpolish]

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

[@sigmundwong2489]

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.

[@lawrencewhitfield8155]

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.

[@alvarez110]

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

[@j.r.9966]

Linguistics example really was great

[@thomas-ux8co]

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

[@Jaylooker]

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

[@larianton1008]

Thank you for your efforts. An incredibly enlighting video, even though I didn't understand all of it. I hope your still up to making that second part! 😅 I'm a GEB fan myself.

[@pra.]

This is amazing. Applications of Category Theory are so cool

[@positivearrow]

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

[@ChannelMath]

LINGUISTS of MATH! so neat

[@marwandaar7369]

Thank you for this beautiful, mind expanding presentation!

[@derekh2934]

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

[@TransAlfteraner]

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

[@randywest984]

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

[@dukereg]

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

[@spogel9981]

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

[@brightfuture0959]

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

[@evtectika]

This is a very strong video

[@samueldeandrade8535]

Wow. A new math channel. Interesting.

[@robertpeszek6892]

Excellent video, very well explained. However, the Lawveres' Fix Point Theorem is mentioned with some ambiguity ( 31:13 Lawvere's theorem). It does not require that the "powerful" arrow P: T x T -> V is surjective, it requires that its "curried" version P : T -> (T -> V) is surjective. Otherwise we woud have many more paradoxes😉. Thumbs up anyway.

[@notnilc2107]

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.

[@Teeh0]

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.

[@Thricery]

Thanks for your feedback!

[@jamesjackson5955]

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

[@ZedaZ80]

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).

[@sergey1519]

0100000... ≠ 0011111...

[@drdca8263]

Yes, if one wants to show that the real numbers are uncountable through this kind of thing, one needs to be a little bit careful. Though, one thing that works is to just use any base larger than 2, and when doing the “flip”, never output the largest digit of the base. (So, in decimal, never pick 9)

[@drdca8263]

My other reply seems to have been eaten.. I wanted to edit it, to add that the proof in the video is showing that there’s no surjection from N to (N -> {0,1}) , which is slightly less finicky than showing that there is no surjection from N to R, because of the reason you point out.

[@DynestiGTI]

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

[@MuffinsAPlenty]

How does it use the axiom of choice?

[@drdca8263]

It doesn’t use the axiom of choice.

[@thesmallestatom]

Masterful presentation!!!

[@lajarre1]

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

[@columbus8myhw]

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.

[@accountname1047]

This is fantastic

[@davidwilkie9551]

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.

[@thomasbradley2916]

What are you talking about man

[@efraimcardona8452]

Excellent explanation 👌

[@julianfeldman1603]

Waiting for the second part

[@iamtraditi4075]

This was incredible! Thank you so much :)

[@recorder-works]

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

[@solalbaudoin6406]

Amazing video!

[@alikaperdue]

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.

[@wernerhartl2069]

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.

[@Loots1]

Lol

[@drdca8263]

Cantor’s diagonalization argument doesn’t depend on the set being infinite. As your example shows, 2^2 > 2 . More generally, 2^n > n . There cannot be a surjection from any set A, to the set of functions from A to {0,1} . Given any function from A to functions from A to {0,1} , we can produce a function from A to {0,1} which no element of A is mapped to. E.g: 1 : 0 1 0 2 : 1 1 0 3 : 0 1 1 applying the diagonal+flip process, we get 1 0 0 Which, of course, is not on our list.

[@CrewCNE]

Cool video! Just fyi it's pronounced "Ger-dle" and "Law-veer"

[@Thricery]

Aaah thank you!

[@ianwoodward8324]

Audio tip - a pop-shield would vastly improve your audio for little to no cost. Otherwise thanks for the vid. It is beyond my understanding, but it expresses ideas I had vaguely formulated in thinking about Godel.

[@Thricery]

Thank you, I hope to do this for the next video! :)

[@ianwoodward8324]

@@Thricery An old trick is to get some tights (thin nylon legwear mostly used by women) which are torn and will be thrown away, and attach it to a piece of wire such as a coat-hanger. Add layers until you are satisfied. You could also improve the sound just by pointing your mouth a little to the side of the mic so the big rush of air does not hit it directly when you say 'p' or 'd'.

[@ianwoodward8324]

Why do I ask for this? Well audio that clips is quite bad for speakers and can degrade them.

[@papetoast]

@@Thricery Also, the audio is too low. After turning all the sound settings to maximum, this video is still slightly quieter than other videos under my normal setting.

[@akepamusic]

Incredible! Fantastic job :)

[@joshuaabraham7308]

Its a really nice video!

[@amidsid3482]

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.

[@amidsid3482]

ps i was wondering how the lawrence theorem sort of resembled the hairy ball theorem, turns out that for even dimensional spheres the lawrence theorem is a corollary to the hairy ball theorem.

[@TheFrok]

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?

[@Thricery]

Great question! A silly and unsatisfying answer would be "yes, it works even if we consider infinite trinary sequences for Cantor's diagonal argument", but that feels like cheating because it's not an essentially new idea. That being said, during the construction of the Y Combinator, the "collection" of Values will have more than two things in it, and that will genuinely feel very different. I think my video on the Y Combinator will be part 3 in this series (after the incompleteness theorems) - so stay tuned!

[@TheFrok]

@@Thricery I would love to see the video on Y combinator!

[@AppliedMathematician]

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.

[@alejrandom6592]

Easter egg: BB written at 21:42 which represents Busy Beavers

[@thomasbradley2916]

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 :)

[@apopheniac4231]

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!

[@tomholroyd7519]

In essence the problem is insisting that the representation be binary. Black or white. Reality is not binary, you can't shoehorn it into a binary representation. But consider that there are "valid" sequences such as 0.01001b00101... where b means both 0 and 1. We can validly write down a list that commutes --- the problem is you can't do it if F is binary --- you added a third state implicitly when you had it output infinite loop. It's important to recognize the difference between True and Valid. Valid things might be false but it's still a valid argument!

[@polyrhythmia]

Reminds me of mathematical induction.

[@chetanbhandari1000]

Need godel theorem next

[@egwpoios8782]

Lawvere Rules!

[@strangelaw6384]

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

[@benjaminpedersen9548]

For Cantor's Theorem you actually don't use the assumption of surjectivity, so it does not have to be a proof by contradiction. Not true for the Halting Problem though.

[@MathNerdGamer]

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!

[@jerzyponimirski8541]

I think your proof about primes is more like induction which comes directly from def. of Naturals. You always claim that what is OK for n will be OK for n+1 (of course you need to check any particular n). For diagonal argument you're getting bunch of other numbers out of the blue (not only changed diagonal - which by the way for finite number never exists ; ) )

[@DjSapsan]

Could put a like just for GEB book

[@pahularora9642]

Waiting for Godel's Incompleteness!

[@joefromzohra]

Nice video. Just one quip: Gödel is pronounced as GUR·del.

[@IustinThe_Human]

still waiting for your next video

[@tomholroyd7519]

Using #RM3, a three-valued logic, the idea that a digit is the opposite of itself is expressible and natural; Both is the third truth value, both true and false. Not Both is Both. It's equivalent to neither true nor false, if you want to look at it that way. So you can write down all the reals, just some of the digits aren't knowable.

[@drdca8263]

I doubt that such a logic works very well…

[@awnion]

10:20 I lost you there. I mean even knowing the subject I lost you :D

[@rzeqdw]

Watching this, I have a question the list of all possible infinite binary sequences maps one-to-one with the list of all possible natural numbers. Just interpret the sequences as the digits of the number, written little-endian, and let infinite trailing zeros be the same as missing digits So the binary sequence (b0, b1, b2, b3, b4, b5, b6 .......) becomes the binary representation of the number b6 * 2^6 + b5 * 2^5 + b4 * 2^4 + b3 * 2^3 + b2 * 2^2 + b1 * 2^1 + b0 * 2^0. (1,1,1,1,0,0,1,0,0,0....) (assume it's zeros forever after that) becomes the binary number (...0000)1001111 The list of all natural numbers is _countably_ infinite. And yet you're using diagonalization to prove that the list of all infinite binary sequences is _uncountably_ infinite. How is this possible? (To be clear, I am sure there's something wrong with my logic, I just don't know what it is)

[@Thricery]

It's a bit subtle, but the reason your argument is not a valid mapping from infinite binary sequences to natural numbers is that you haven't said what happens to say the sequence 11111... (and 1 forever). In fact, any sequence that has an infinite number of 1s doesn't get mapped to a natural number using the little-endian idea. You're only defining a natural number for a partial subset of all possible infinite binary sequences - those with finitely many 1s (i.e. those that have infinite trailing 0s). You have however shown that the set of "arbitrarily long" binary sequences (i.e. binary sequences which end at some point with infinite trailing zeros) is countable, which is true. Good question though, this difference between "arbitrarily large" and "truly infinite" is subtle and has tripped me up a few times too!

[@rzeqdw]

@@Thricery thanks for the explanation! I didn't even think of that, but makes total sense

[@TheOneMaddin]

Great video! I really liked it. But please look up the correct pronunciation of Gödel.

[@kartik4792]

What happens if we assume (1 = 0) && (1 != 1)? Does math remain same?

[@makucevich]

Excellent presentation, however you need a pop filter on your mic.

[@localidiot4078]

so what always confuses me about the uncountably infinite proof. It feels like the only reason this is the case is because you arbitrarily decided the order to have no meaning. like what if the mapping rule went as follows. for any decimal, start reading the number left to right, I.E. .987654321... and the whole number place that takes up will be, the ....123456789th whole number in the order. so you can start with .1, which turns into 1. .2 = 2... .01 = 10 .11 = 11 if you just flip the decimal around wouldn't that give you a valid whole number every single time? if we are assuming that decimals can be infinite, why can whole numbers not also be infinite? The flaw in my reasoning here could be, if you had an infinate decimal, it would never terminate? i feel like functions exist that can map any arbitrary decimal to a integer without collisions.

[@danielseda2450]

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

[@chrimony]

Audio is hard to listen to with all the pops and unequal volume levels.

[@B_dev]

perhaps there's something special about iterating diagonally along a 2d array?