FYI there's a small problem with the rule of adding 1 to the digits along the diagonal: It allows for the possibility of both the first row and the raw diagonal being 0.999999... and the diagonal with +1 applied to each digit being therefore 1.000000... In that case, yes the shifted diagonal number does exist in the list after all, just "spelled" differently! When I first learned about Cantor's diagonalization proof, I learned using the rule: Map all digits along the diagonal to 7, except for 7 itself, which you then map to 0. Avoids the possibility, so ultimately the logic still holds. I guess you could also try to argue, in that particular case, that if the diagonal is exactly 1.00000... then you can't find 0.22222.... anywhere on the list, but that complicates the argument. (And I believe that when Cantor did the original proof, he actually worked in base 3, for similar reasons.)
I'm watching your addendum at the end about suffixes with infinitely many 1's in the binary case. My point above is basically the decimal version of that. Glad you at least mentioned it!
There's a dude with a channel called "combo class" which has been really fun and he makes new stuff weekly. It's maybe a little more designed for math amateurs (like myself) but still gets at some really fun and spooky topics
This proof gave me an "Eureka" moment! It was stunning to link all of these concepts in a beautiful, simple and Imho elegant proof about the "simple", discrete natural numbers and the dense, "un-peerable" real numbers! Thanks, thank you SO much!
I've learned of this equality from my teacher making a throwaway remark with no context, and it stuck with me as one of the most beautiful equalities in math; glad to have finally watched a video that explains why it's true. Thanks!
With an exaggerated acceptance that our choice of writing the Power Set's cardinality as an exponent, and assuming exponent rules apply. Almost like having an operation (dy/dx) and then being perfectly OK with the idea of "×dx on both sides"... The greatest triumph of Math is Notation!
Since Cantor's time many mathematicians expressed doubt about counting infinite elements, until Hilbert declared that Cantor saved us. Hilbert didn't say what Cantor saved us from, but mathematical convention continues to believe Hilbert, so Cantor was accepted by default.
I remember independently noticing this, since any ℝeal number can be formed from a countably infinite list of digits, and the number of possible ways to select b elements n times is b^n. Insert b = 2 for simplicity and n = |ℝ| and you get 2^|ℕ| = |ℝ|. It's definitely less rigorous than presented here, but it's a cool thing to notice. It also suggests that the number of p-adic integers for any given p is also the same cardinality as the ℝeals, since it's just a countably infinite number of digits to the left rather than the right. I've also encountered a construction to take any N-dimensional inner product space and turn it into a 2^N-dimensional vector space with the new basis being able to be described as the power set of the initial basis, and a particular instance starts with a countably-infinite-dimensional initial vector space, so the full result actually becomes uncountably infinite.
@@BurningShipFractal They're no more real than imaginary numbers, nor any less complex than ℂomplex numbers (except in the very literal sense of a ℂomplex number being a "complex of numbers," aka a "compound"). So I don't like calling them "real numbers," but that is their name, so I just make it extra clear that it's a proper noun rather than an adjective. Plus this way is more fun than just "Real number" and "Complex number." Really when you look into it, ℝeal numbers are actually way _more_ complex to understand than ℂomplex numbers. It really is a larger leap to go from the algebraic numbers (an actually descriptive adjective for once) to the ℝeal numbers, than to go from the algebraic numbers to the ℂomplex numbers. For the ℂomplex numbers, one requires accepting a number "i" such that i² = -1 (which also makes it go spinny), meanwhile defining the ℝeals requires things like "Dedekind cuts" and "Cauchy sequences." There is a layer in-between for the computable numbers (exactly what it says on the tin amazingly), which is every ℝeal number that can actually be defined. The quaternion's symbol is ℍ for "Hamilton," so the same system doesn't apply, but it's also not mistakable for an adjective, so it's not as necessary.
@@calvindang7291 The surjective mapping being described is from N to N^2, both of which are infinite. The illustration shows a finite subset of 16 points. Sure, you'll reach all of those points in finite time. But that's not the point.
Very interesting. I knew about the strict inequality between the cardinalities of a set and its power set (including the special case of |P(N)|=|R|) but I wasn't familiar with its proof. Turns out it's fairly simple - and very, very similar to Russel's paradox. I wonder if there are any other neat proofs by constructing a particular class symbol with a self-referential defining condition.
You may want to look into Gödel's incompleteness theorem, as well as into the halting problem - past the technical details, the form of the argument is essentially the same.
the proof of the undecidability of the halting problem is actually a diagonalization proof in disguise! imagine a table where in the ith row jth column we put 1 if the ith Turing machine halts on the jth Turing machine. the machine we create during the proof is basically the invert of the diagonal.
@@wqferrI made a SoME3 video that's just under 50min about Gödel, if you are talking about mine, I hope you liked it even with the rush to finish it for the deadline
The part of the proof S and power set of S is kinda fast... I think it could be explained more clealy, at each step explain more of everything. After my first watches, i didnt understand why we can jump from something to do with T to the proof.
That's the section I'm least happy about. I never found any proof of Cantor's theorem on UA-cam intuitive, and I guess I failed to make one too. What made it click for me was watching many videos on the topic and seeing reworded proofs. One of the watching list videos I put in the description is a video from PBS IS on the topic, I hope it helps you grasp it better. Essentially, the mere existence of T, a set that is never mapped to by f, proves no f can be surjective.
The sets part at 5:24, bro this so good thinking of it in binary it better than doing sigma(Cn,k; k goes from 0 to n) where 2 to the power of n recovers it all loll
This video was really interesting but now I'm wondering whether this result can be used in any meaningful proof? Or is it just a nice coincidental fact to notice?
Sadly I couldn't find any direct application of this result. Related terms if you want to research more are aleph numbers (other infinite cardinalities), beth numbers (of which aleph_0 is first and c is second), and the Gimel function
@@wqferr I guess one could go on to derive an arithmetic of set cardinalities from there and maybe use it to predict properties of some exotic uncountably infinite sets beyond the reals and stuff if that makes any sense, but I'd be willing to know more…
In principle, the cardinal numbers are at the base of what you're looking for. They are the numbers that represent sizes of sets, so if you want different relations between them, cardinal arithmetic could be a starting point. Wikipedia has an article on it, but as always with wiki math articles, it's very dense and hard to parse.
OK , so the argument of why the power set of a set has higher cardinality than the set is the same argument that proves that the set of all sets does not exist? Both these arguments are bogus, relying upon a heavily disguised axiom of choice.
I wonder if this has a continuation among other infinities, like if every next infinity is the cardinality of the powerset of the previous one.. Wouldn't it be nice if |P(R)|= |C|? C as in complex numbers
actually, the cardinality of the complex numbers is the same as the cardinality of the real numbers. its easy to show that the all of the real numbers can be mapped to a unique complex number since real numbers are a subset of complex numbers. So from this we already know that |R| ≤ |C| It is also possible to create a surjection from the complex numbers to real numbers. The example I know of is as follows: take a complex number a + bi. take the decimal expansion of a and b and "interweave" them together. For example, if I had 1.243 + 0.632i, then it would be mapped to 1.0264332. This shows that |C| ≤ |R|. combining that with the previous inequality, we know that |R| = |C|
C has the same cardinality as R. In fact, same goes for n-dimensional euclidean space R^n. Space-filling curves is one of simplest demonstrations of this. Additionally, one can prove that for any two infinite cardinalities |A| and |B|, |A×B|=max(|A|,|B|).
What the others have said is true, but your comment reminded me of the generalized continuum hypothesis. It states that all aleph numbers (infinite cardinalities of which aleph_0 is first) are the consecutive application of the power set operator. You can read more about it on Wikipedia, though it's unnecessarily obtuse as is usual for Wikipedia math articles.
@@potaatobaked7013 I think you made a typo here - if a surjection exists from C onto R, then |C| >= |R|. I think you want an injection instead (or a surjection from R onto C). A surjection from C to R is also quite trivial as the mapping that takes a complex number and maps it to its real part will do that.
@@stevenfallinge7149 But of course, this is only true under the assumption of axiom of choice. In fact, the proposition that for every infinite set A it's true that A×A can be mapped one-to-one with A implies the axiom of choice.
This is one of the results that's incredibly obvious, but looks deep if you disguise it in a bunch of abstract language. The statement "the power set of the natural numbers has the same cardinality as the reals" is really just saying "all collections of finite/infinite lists of natural numbers correspond to some real number" or even simpler "you can write any real number as an infinite decimal" So much of set theory is just putting simple ideas into a highly structured, prosaic language.
That's not the point though. The point was that the cardinality of the natural numbers and the cardinality of the real numbers *literally* define each other.
I'm not sure to have fully understood, but if I did, you enumerated all the real numbers between 0 and 1 by constructing them in binary, and you did it by enumerating all the binary numbers right ? But can't the set of all binary numbers be mapped to the set a natural numbers ? Thanks for this very cool video and yeah, PBS infinite series miss me too....
To be clearer, if you construct numbers between 0 and 1 in binary by putting all possible binary numbers after the point (0.000000 then 0.100000 then 0.010000 then 0.110000 then 0.001000 then 0.101000 then 0.011000 then 0.111000 ...), don't you end up with all real numbers between 0 and 1 and can't you count them ?
@@mehdimabed4125 this only gives you the binary numbers with finite representations, a set that is indeed countable, but it misses all the real numbers with infinite binary representations (such as pi or 1/3).
@@mehdimabed4125 If you try to do that you'll only count all the binary numbers with a finite number of 1s, you'll never get to the ones with an infinite number of 1s at the end.
@@BenAlternate-zf9nr I don't get why it would generate numbers with only finite representations, the set of natural numbers is countably infinite and contains numbers with infinite representation isn't it ? But thanks for the answer :)
@@Reddles37 As for the previous comment, I don't get why it would generate numbers with only finite number of 1s, the set of natural numbers is countably infinite and contains numbers with an infinite of numbers ? Thanks for the answer :)
@@wqferr Thank you. Unfortunately, Discord isn't a possible option for me. I'll need some type of online tutorial. Is the program free, or does it cost money?
@@one_logic Yes there is! I followed this guy's tutorial mostly: ua-cam.com/video/rUsUrbWb2D4/v-deo.html but there are others. You can also find a mostly complete (with examples) documentation here: docs.manim.community/en/stable/index.html . There is also a subreddit at /r/manim . Manim is free and open source, meaning if you want you can create your own manim completely independent from the community edition. That is how CE was born, after all.
I skipped ahead a bit, because I was already familiar with cardinalities of infinity, but it seems like you didn't mention Beth numbers. Apparently, the relationship highlighted in this video was so important that a whole other symbol was appropriated for representing the cardinalities of power sets. I may or may not have been using Aleph and Beth as names for characters I create in video games, or use in creative writing exercises, for the past 13 or so years...
Well not so surprising: after all, real numbers are just an arrangement of natural numbers, where the decimal point is is of little meaning. You have well ordered infinite arrangements of infinite natural digits
FYI there's a small problem with the rule of adding 1 to the digits along the diagonal: It allows for the possibility of both the first row and the raw diagonal being 0.999999... and the diagonal with +1 applied to each digit being therefore 1.000000... In that case, yes the shifted diagonal number does exist in the list after all, just "spelled" differently!
When I first learned about Cantor's diagonalization proof, I learned using the rule: Map all digits along the diagonal to 7, except for 7 itself, which you then map to 0. Avoids the possibility, so ultimately the logic still holds.
I guess you could also try to argue, in that particular case, that if the diagonal is exactly 1.00000... then you can't find 0.22222.... anywhere on the list, but that complicates the argument.
(And I believe that when Cantor did the original proof, he actually worked in base 3, for similar reasons.)
I'm watching your addendum at the end about suffixes with infinitely many 1's in the binary case. My point above is basically the decimal version of that. Glad you at least mentioned it!
Thank you for looking out though, that one wasn't a flaw I knew about. I've made an edit to the description with your fix, hopefully people read it.
But if you try multiple times eventually you will hit an infinite set that works with the proof
0.(9) is not equal to 1.(0)
@@blango-sanThe different between 1.(0) and 0.(9) is 0.(0) Wouldn’t that make them the same?
The tribute to PBS Infinite Series was heartwarming. That made me smile :)
Same. I still miss it, and continue to mention that on the yearly PBS survey.
What a beautiful hommage to the Infinite Series 🤗
That was the *best* show 😃
I miss PBS IS too 😢
There's a dude with a channel called "combo class" which has been really fun and he makes new stuff weekly. It's maybe a little more designed for math amateurs (like myself) but still gets at some really fun and spooky topics
P.s... he has a shorts channel which is good too, but the main longer vid channel is what I'm referring to
That’s a finite series😢
@@borkalinka1186 lol
This proof gave me an "Eureka" moment! It was stunning to link all of these concepts in a beautiful, simple and Imho elegant proof about the "simple", discrete natural numbers and the dense, "un-peerable" real numbers!
Thanks, thank you SO much!
I've learned of this equality from my teacher making a throwaway remark with no context, and it stuck with me as one of the most beautiful equalities in math; glad to have finally watched a video that explains why it's true. Thanks!
PBS infinite series was great!
It sure was. I miss it sooo much
This was beautiful. And clearly shows why 2 is the second best number: 2 = c^(1/ℵ₀).
With an exaggerated acceptance that our choice of writing the Power Set's cardinality as an exponent, and assuming exponent rules apply.
Almost like having an operation (dy/dx) and then being perfectly OK with the idea of "×dx on both sides"...
The greatest triumph of Math is Notation!
Oh my God, this video is a masterpiece, what a beauty!! What genius!!! Thank you from the heart
Since Cantor's time many mathematicians expressed doubt about counting infinite elements, until Hilbert declared that Cantor saved us. Hilbert didn't say what Cantor saved us from, but mathematical convention continues to believe Hilbert, so Cantor was accepted by default.
Your mic has too much noise, good video nevertheless
Yeah, I know. I asked a friend how to fix it and now I know for the next videos
Wow the connection was so mindblowing and your explanation was so intuitive!!!
I remember independently noticing this, since any ℝeal number can be formed from a countably infinite list of digits, and the number of possible ways to select b elements n times is b^n. Insert b = 2 for simplicity and n = |ℝ| and you get 2^|ℕ| = |ℝ|. It's definitely less rigorous than presented here, but it's a cool thing to notice. It also suggests that the number of p-adic integers for any given p is also the same cardinality as the ℝeals, since it's just a countably infinite number of digits to the left rather than the right. I've also encountered a construction to take any N-dimensional inner product space and turn it into a 2^N-dimensional vector space with the new basis being able to be described as the power set of the initial basis, and a particular instance starts with a countably-infinite-dimensional initial vector space, so the full result actually becomes uncountably infinite.
ℝeal number
@@BurningShipFractal They're no more real than imaginary numbers, nor any less complex than ℂomplex numbers (except in the very literal sense of a ℂomplex number being a "complex of numbers," aka a "compound"). So I don't like calling them "real numbers," but that is their name, so I just make it extra clear that it's a proper noun rather than an adjective. Plus this way is more fun than just "Real number" and "Complex number."
Really when you look into it, ℝeal numbers are actually way _more_ complex to understand than ℂomplex numbers. It really is a larger leap to go from the algebraic numbers (an actually descriptive adjective for once) to the ℝeal numbers, than to go from the algebraic numbers to the ℂomplex numbers. For the ℂomplex numbers, one requires accepting a number "i" such that i² = -1 (which also makes it go spinny), meanwhile defining the ℝeals requires things like "Dedekind cuts" and "Cauchy sequences." There is a layer in-between for the computable numbers (exactly what it says on the tin amazingly), which is every ℝeal number that can actually be defined.
The quaternion's symbol is ℍ for "Hamilton," so the same system doesn't apply, but it's also not mistakable for an adjective, so it's not as necessary.
"It also suggests that the number of p-adic integers for any given p is also the same cardinality as the ℝeals ..."
- This is indeed correct.
®eal number
Amazing video! This is incredibly underrated... So interesting
This was a good video, thanks for making something entertaining and informative for #SoME3
great video
At 4:09, "Since all elements are reached in finite time ..." but they're not reached in *finite time*, it's that all pairs are reached *eventually"
It is finite number of steps always. And saying all reached in finite time or all reached eventually have the same meaning
Each particular element can be reached in finite time, which is the proper way to think of eventually reaching all of them.
@@calvindang7291 The surjective mapping being described is from N to N^2, both of which are infinite. The illustration shows a finite subset of 16 points. Sure, you'll reach all of those points in finite time. But that's not the point.
This topic is suspicious. One could accapt this reasoning as mathematics, or they could simply reject it.
I didn't realise you have this little subscribers. I was expecting at least a few thousand.
Great content, keep up the good work!
Very interesting. I knew about the strict inequality between the cardinalities of a set and its power set (including the special case of |P(N)|=|R|) but I wasn't familiar with its proof. Turns out it's fairly simple - and very, very similar to Russel's paradox. I wonder if there are any other neat proofs by constructing a particular class symbol with a self-referential defining condition.
You may want to look into Gödel's incompleteness theorem, as well as into the halting problem - past the technical details, the form of the argument is essentially the same.
the proof of the undecidability of the halting problem is actually a diagonalization proof in disguise!
imagine a table where in the ith row jth column we put 1 if the ith Turing machine halts on the jth Turing machine.
the machine we create during the proof is basically the invert of the diagonal.
Regarding Gödel's incompleteness theorems, I believe another SoME3 entry goes into quite a lot of detail on them (about a 50min long video)
@@wqferrI made a SoME3 video that's just under 50min about Gödel, if you are talking about mine, I hope you liked it even with the rush to finish it for the deadline
Really enjoyed this one btw, never seen this part even though I have seen the diagonal arguments all over
The part of the proof S and power set of S is kinda fast... I think it could be explained more clealy, at each step explain more of everything. After my first watches, i didnt understand why we can jump from something to do with T to the proof.
That's the section I'm least happy about. I never found any proof of Cantor's theorem on UA-cam intuitive, and I guess I failed to make one too.
What made it click for me was watching many videos on the topic and seeing reworded proofs. One of the watching list videos I put in the description is a video from PBS IS on the topic, I hope it helps you grasp it better.
Essentially, the mere existence of T, a set that is never mapped to by f, proves no f can be surjective.
rip pbs infinite series.
all my homies miss pbs infinite series
I guess I’m just drunk enough for this
The sets part at 5:24, bro this so good thinking of it in binary it better than doing sigma(Cn,k; k goes from 0 to n) where 2 to the power of n recovers it all loll
This video was really interesting but now I'm wondering whether this result can be used in any meaningful proof? Or is it just a nice coincidental fact to notice?
Sadly I couldn't find any direct application of this result. Related terms if you want to research more are aleph numbers (other infinite cardinalities), beth numbers (of which aleph_0 is first and c is second), and the Gimel function
@@wqferr I guess one could go on to derive an arithmetic of set cardinalities from there and maybe use it to predict properties of some exotic uncountably infinite sets beyond the reals and stuff if that makes any sense, but I'd be willing to know more…
In principle, the cardinal numbers are at the base of what you're looking for. They are the numbers that represent sizes of sets, so if you want different relations between them, cardinal arithmetic could be a starting point. Wikipedia has an article on it, but as always with wiki math articles, it's very dense and hard to parse.
@@wqferr I exists! That's application enough for me 😆
OK , so the argument of why the power set of a set has higher cardinality than the set is the same argument that proves that the set of all sets does not exist? Both these arguments are bogus, relying upon a heavily disguised axiom of choice.
I wonder if this has a continuation among other infinities, like if every next infinity is the cardinality of the powerset of the previous one.. Wouldn't it be nice if |P(R)|= |C|? C as in complex numbers
actually, the cardinality of the complex numbers is the same as the cardinality of the real numbers.
its easy to show that the all of the real numbers can be mapped to a unique complex number since real numbers are a subset of complex numbers. So from this we already know that |R| ≤ |C|
It is also possible to create a surjection from the complex numbers to real numbers. The example I know of is as follows:
take a complex number a + bi. take the decimal expansion of a and b and "interweave" them together. For example, if I had 1.243 + 0.632i, then it would be mapped to 1.0264332.
This shows that |C| ≤ |R|. combining that with the previous inequality, we know that |R| = |C|
C has the same cardinality as R. In fact, same goes for n-dimensional euclidean space R^n. Space-filling curves is one of simplest demonstrations of this. Additionally, one can prove that for any two infinite cardinalities |A| and |B|, |A×B|=max(|A|,|B|).
What the others have said is true, but your comment reminded me of the generalized continuum hypothesis. It states that all aleph numbers (infinite cardinalities of which aleph_0 is first) are the consecutive application of the power set operator. You can read more about it on Wikipedia, though it's unnecessarily obtuse as is usual for Wikipedia math articles.
@@potaatobaked7013 I think you made a typo here - if a surjection exists from C onto R, then |C| >= |R|. I think you want an injection instead (or a surjection from R onto C). A surjection from C to R is also quite trivial as the mapping that takes a complex number and maps it to its real part will do that.
@@stevenfallinge7149 But of course, this is only true under the assumption of axiom of choice. In fact, the proposition that for every infinite set A it's true that A×A can be mapped one-to-one with A implies the axiom of choice.
This is one of the results that's incredibly obvious, but looks deep if you disguise it in a bunch of abstract language.
The statement "the power set of the natural numbers has the same cardinality as the reals" is really just saying "all collections of finite/infinite lists of natural numbers correspond to some real number" or even simpler "you can write any real number as an infinite decimal"
So much of set theory is just putting simple ideas into a highly structured, prosaic language.
That's not the point though. The point was that the cardinality of the natural numbers and the cardinality of the real numbers *literally* define each other.
Very good video !!
I'm not sure to have fully understood, but if I did, you enumerated all the real numbers between 0 and 1 by constructing them in binary, and you did it by enumerating all the binary numbers right ? But can't the set of all binary numbers be mapped to the set a natural numbers ?
Thanks for this very cool video and yeah, PBS infinite series miss me too....
To be clearer, if you construct numbers between 0 and 1 in binary by putting all possible binary numbers after the point (0.000000 then 0.100000 then 0.010000 then 0.110000 then 0.001000 then 0.101000 then 0.011000 then 0.111000 ...), don't you end up with all real numbers between 0 and 1 and can't you count them ?
@@mehdimabed4125 this only gives you the binary numbers with finite representations, a set that is indeed countable, but it misses all the real numbers with infinite binary representations (such as pi or 1/3).
@@mehdimabed4125 If you try to do that you'll only count all the binary numbers with a finite number of 1s, you'll never get to the ones with an infinite number of 1s at the end.
@@BenAlternate-zf9nr I don't get why it would generate numbers with only finite representations, the set of natural numbers is countably infinite and contains numbers with infinite representation isn't it ? But thanks for the answer :)
@@Reddles37 As for the previous comment, I don't get why it would generate numbers with only finite number of 1s, the set of natural numbers is countably infinite and contains numbers with an infinite of numbers ? Thanks for the answer :)
Very nice!
Hey. What animation program do you use?
@yarno8086 Yes, but I forgot the name
It's called Manim, specifically the community edition. For support on installation and use, check their official disicord: discord.gg/f6wJtGFZ
@@wqferr Thank you. Unfortunately, Discord isn't a possible option for me. I'll need some type of online tutorial. Is the program free, or does it cost money?
@@one_logic Yes there is! I followed this guy's tutorial mostly: ua-cam.com/video/rUsUrbWb2D4/v-deo.html but there are others. You can also find a mostly complete (with examples) documentation here: docs.manim.community/en/stable/index.html . There is also a subreddit at /r/manim . Manim is free and open source, meaning if you want you can create your own manim completely independent from the community edition. That is how CE was born, after all.
I skipped ahead a bit, because I was already familiar with cardinalities of infinity, but it seems like you didn't mention Beth numbers. Apparently, the relationship highlighted in this video was so important that a whole other symbol was appropriated for representing the cardinalities of power sets.
I may or may not have been using Aleph and Beth as names for characters I create in video games, or use in creative writing exercises, for the past 13 or so years...
What happened to PBS infinite series
It got cancelled about 5 years ago
😢@@wqferr
Infinity is a mathematical fiction
2 tetrated to ∞=∞
Well not so surprising: after all, real numbers are just an arrangement of natural numbers, where the decimal point is is of little meaning. You have well ordered infinite arrangements of infinite natural digits
Nice video. Now on to aleph_1…