Cardinality of the Continuum

What is infinity? Can there be different sizes of infinity? Surprisingly, the answer is yes. In fact, there are many different ways to make bigger infinite sets. In this video, a few different sets of infinities will be explored, including their surprising differences and even more surprising similarities.
0:00 - Euclid's Proof of Infinite Primes
1:55 - Bigger Infinities?
2:27 - Set Theory and Bijections
5:12 - No Countable Difference Principle
6:13 - Power Set of the Naturals
8:12 - Euclid's Proof and the Power Set
9:20 - Cardinality of the Reals
10:57 - Cardinality of Positive Integer Functions
13:29 - Are these Cardinalities the Same?
14:11 - Binary Notation
17:44 - Real Numbers and the Power Set
19:19 - Functions and the Power Set
20:56 - Conclusion
Additional Resources:
Euclid's Proof of Infinite Primes: primes.utm.edu/notes/proofs/i...
Proof that the cardinality of the unit interval is the same as the cardinality of the reals: • The Cardinality of an ...
Roads to Infinity: The Mathematics of Truth and Proof by John C. Stillwell
Wikipedia article about Cantor's Diagonal Argument: en.wikipedia.org/wiki/Cantor%...
How to Count Past Infinity by Vsauce: • How To Count Past Infi...
Image of Euclid: cdn.britannica.com/46/8446-05...
Music: www.purple-planet.com
Bright Ideas by Purple Planet Music
c418.bandcamp.com/album/mixes
Confusion by C418
Kitten by C418
Animations were made by Manim, an open-source python-based animation program by 3Blue1Brown.
github.com/3b1b/manim
This video was submitted to 3Blue1Brown's SoME2 (Summer of Math Exposition 2).
summerofmathexposition.substa...

[@ehxolotl4194]

Small issue at 19:38, 1 should translate to 0, not 00.

[@jHan]

You're right, thanks for pointing that out!

[@Sci0927]

🤔

[@allozovsky]

Was looking for this comment. Nice and easy to grasp presentation of a complex math topic! 👍

[@liijio]

Proving continuum hypothesis , proving inconsistency in ZFC , constructing ZFC from naive set specification , resolving Russell's paradox , constructing infinite number system , construct and ensure overall consistent mathematical universe and developing arithmetic system - edition 8 May 2024 DOI: 10.13140/RG.2.2.21713.75361 LicenseCC BY-NC-ND 4.0

[@scottcampbell2707]

The cardinality of the set of useful KZbin math videos has increased by 1.

[@aiaian_aaa5583]

This video is incredible. Actually it’s THE best video which talk about infinite sets. The pace and music be just perfect and when it comes to the end, it literally teaches us more than just math. Also the words you used are very friendly for a English learner like me. We need more math videos like this!

[@jonahansen]

Dude - please can the music, or at least tone it down. It distracts my right brain. Not to disparage this video, it's fantastic. Thanks! Shoot - I didn't read the comments before I put in mine; someone else also mentioned this.

[@sleepyhaad8328]

please post more frequently, I genuinely loved this video.

[@harrytaylor4360]

I adore the 3B1B-like style used here. The way it was used in the infinite-primes proof was very smooth

[@chasg5648]

Wonderful presentation! A small detail, the background noise is distracting and takes away from the experience. Regardless, please make more!

[@Treebark1313]

It's just badly mixed. If the background music was quieter...

[@pineco74]

So THAT is why I didn't understand half of what he talked about... What a relief, I thought I was just dumb, but no... Distracting background noise it is lol

[@mihailmilev9909]

@@pineco74 lll

[@mihailmilev9909]

@@pineco74 lol

[@mihailmilev9909]

@@pineco74 I think for me it's cuz in watching at 1 am lol

[@kcthomas8392]

I think a much better approach is to point out 0.1000... and 0.0111... (in binary) are in fact equal in value, in the exact same way that 1.000... and 0.999... (in base 10) have equal value (both are equal to 1).

[@OmateYayami]

Was looking for this. This isn't a gimmick related to binary, it exists in every base system and it's a notation issue with fixed point rationals, that base-1 infinitely repeated is 1 at higher magnitude. That notation also represents an infinite polynomial in such case, so you get two infinite polynomials with same value. I guess.

[@jercki72]

I don't see how that's a better approach though

[@OmateYayami]

@@jercki72 If I recall correctly. It's better in the way it shows the relation that two infinite polynomials are not unique in a much more intuivite way. And, again, if I recall correctly, the video said it's an issue with binary representation or related polynomials. It happens with every base and fixed point notation system. I can rewatch the video and refresh memory if you are interested.

[@susmitislam1910]

Very well made! If you can, please continue making similar videos. 💯

[@alegian7934]

For some reason this is the first time Ive come across the double-representation edge case, really interesting 👍

[@allozovsky]

Wait, you never participated in "is zero nine repeating equal to one" debates on youtube???!!! 😱

[@alegian7934]

@@allozovsky nonono of course I have, I mean in the context of cantor's diagonalization. Its a very serious loophole

[@allozovsky]

@@alegian7934 Some college/university level math books simply treat this representation as _not valid:_ *Definition.* Let's call an infinite decimal expansion _valid_ if it does terminate with 999... *Lemma.* There is a one-to-one correspondence between the set of all real numbers and the set of all _valid_ infinite decimal expansions: I do not know how common this approach is, though. I'm still getting used to this new to me "definition", which seems to somehow "deassign" the value of *0.999...,* making a question "what it equals to" sort of pointless.

[@gooball2005]

Awesome video! The pacing felt right and still you managed to delve into some very interesting insights in a short amount of time. Top notch math education!

[@sleepyhaad8328]

I'm so glad I found this channel

[@matt__tab]

literally made my day

[@ouvie]

You explain it well and you're quite underrated. Keep it up!

[@cecil6365]

This video deserves much more views than it has right now.

[@evgenysmirnov4506]

The conclusion part - brilliant execution: the script, the music, the eloquence - this is vsauce quality, good job!

[@ronaldboulder308]

Very well done. Thank You for having me learned something today.

[@beautyofmath6821]

This is a wonderful video about infinite sets, u explained clearly and I learned a lot, thank you for this.

[@stavrosklaoudatos]

Great Video!

[@andresmlinar]

Great video, thanks!

[@davidbellamy1388]

Very nice video, great work

[@jonipaliares5475]

I loved this video! Just subscribed!

[@lazarusunkwon6]

Great work.

[@edwardmorvan5809]

Great video! Thanks 👍

[@leotimm6805]

just amazing!

[@guillaume5313]

This video is absolutely amazing, thanks jHan

[@supergeniodelmale2756]

The binary coding step was simply incredible! Keep it up!

[@edomeindertsma6669]

And the natural number functions were encoded in unary, so genius. Though it's doubtless that he didn't come up with it himself.

[@santip1277]

I need to write a comment to show that I was here this early when this blows up... amazing video, keep up the good work!

[@Tadesan]

No You dont.

[@santip1277]

@@Tadesan thank you so much Tadesan, I wouldn’t have ever realized that I didn’t have a physical necessity of writing if it wasn’t for you

[@angeldude101]

Most of what was said about binary really applies to all bases of standard positional notation. For any natural number b > 1, every positive number can be described as a₁b^n + a₂b^(n-1)+ ... + a₃b^2 + a₄b + a₅ + a₆b^-1 + ... a₇b^-m. Binary is just where b = 2 and a_n can be either 0 or 1. Decimal just the same, except b = 2*5 = 3+7 = 0xA = 10_10_10_10_... (It's surprisingly hard to write bases without defaulting to a privileged base). The part about numbers falling on the line of powers of two is also true in decimal, though instead of having either an infinite string of 0s or 1s, you instead have an infinite string of 0s or 9s, or more generally 0s and (b-1)s. 0.999... = 1 is just the decimal version of 0.1111 =1, which itself is positional notion for 1/2 + 1/4 + 1/8... = 1, which is its own famous proof. Where binary is special is the ability to change the digits into yes's and no's. The elements of the power set can exactly be described with a yes or a no for whether a given element is included. Since yes/no itself is a binary option, any sequence of them corresponds uniquely to a binary number. So the binary Real numbers between 0 and 1 can just be described as the the powerset of all negative integer powers of 2. P.S. Thinking of binary numbers less as numbers and more like a game of 20 questions gives what I think is an interesting way to think about them. An 8-bit number n can be summarized as the following: Is n odd? Is n/2 odd? Is n/4 odd? Is n/8 odd? Is n/16 odd? Is n/32 odd? Is n/64 odd? Is n/128 odd? Every set of answers to these 8 questions uniquely identifies every natural number from 0 to 255, and each question directly corresponds to a particular bit in the binary representation. Technically, you can ask these questions for any integer, though multiple numbers will have the same answers, which is effectively what happens with integer overflow. This game can also be played for other bases, but you'd need to expand your options from just yes and no.

[@mahdiashrafmahir1534]

loved the video.

[@ashleemeow]

For the uncountability of the unit interval proof I would choose a slightly different example of a number not in that set. It's possible that you end up with a number that ends in a string of zeroes using this method and since such numbers don't have unique decimal representations it's also possible this number is already in your set. If you change the numbers you use from 0 to 1 into 1 and 2 in the algorithm you avoid this issue without having to make further assumptions or proofs :)

[@angelmendez-rivera351]

0:29 - 1:38 Interestingly, this proof is applicable not only to the prime numbers, which are the prime elements of the ring of integers, but this proof is applicable to any ring that satisfies the properties of a greatest-common-divisor domain. In such rings, every irreducible element is a prime element, and prime elements are necessarily irreducible anyway, so they are one and the same thing. Thus, you can yet consider again a finite set of prime elements, find their product (which is possible, since these rings are necessarily commutative), add 1, and since in these domains, a prime dividing the product of primes requires being one of the primes, it means the prime must also divide 1, and this is impossible. Euclid's proof is great, because it means that for any ring that is a GCD domain, if there are any prime elements at all (there could be zero, as with the rational numbers, for example), then there are necessarily infinitely many. 5:12 - 5:48 A concise way to put this into a statement is to say that Aleph(0) + Aleph(0) = Aleph(0). This is intriguing, because it means that unlike with the natural numbers, where you can have something like 3 - 3, you cannot have Aleph(0) - Aleph(0): this is nonsense, in the same way that 1/0 is nonsense. This is part of the reason why infinite concepts are so counterintuitive. We come into this discussion with the preconception that we should be able to always subtract mathematical quantities, that q - q should always be 0, regardless of what q is. This preconception, however, is false. Objects operate by their own innate rules, regardless of whether we like those rules or not. Us refusing to accept the rules of infinite objects is the reason why infinity was rejected from mathematics for such a long time. On the note of applications, there actually are many applications of cardinality of sets. In physics, it is very important to distinguish whether we are dealing with a continuum, or a countable set. This is because the predictions of a model will change significantly based on which of the two is being worked with. You can have "sum" of countable many elements that is finite, but this is impossible with uncountable sets (and integrals are not sums of uncountable sets, so this is alright). So, these results can tell us something about the cardinality of the sets of physical objects we are working with. In research for quantum gravity, these calculations are at the forefront of the discussion of spacetime, and determining whether it truly is a continuum, as it is still currently believed by physicists, or whether it actually has some yet undetected discretization that makes spacetime countable.

[@schweinmachtbree1013]

Your first paragraph is incorrect - to be able to carry out Euclid's proof you need to know not only that at least one irreducible element exists (which is a subtle point that I'm impressed you picked up on - another nice example of an integral domain, even a GCD domain, with no irreducible elements is the algebraic integers; every element factors as a = sqrt(a)sqrt(a) so is reducible), but also that any element has an irreducible factor. Given an element _a_ , if it's irreducible then we're done, and if it's not then by definition it factors as _a_ = _bc_ . If either _b_ or _c_ is irreducible then again we're done; if not, _b_ factors as _de_ and _c_ factors as _fg_ so _a_ = _defg_ , but again there is no guarantee that any of _d, e, f,_ or _g_ will be irreducible, or that the process will terminate. Sufficient conditions for the process to terminate -- in the lingo, for the domain to be an "atomic domain" -- are (1) the domain is a principal ideal domain, (2) the domain is a Noetherian domain, or (3) the domain satisfies the ascending chain condition on principal ideals, with each condition being more general than the previous. There are counterexamples to the statement that "every GCD domain with at least one irreducible element is an atomic domain" - if we forget about the caveat that at least one irreducible exists then there are easy counterexamples (e.g. any non-field GCD domain with no irreducible elements, such as the algebraic integers) but with the caveat, the known counterexamples become very exotic and not something that can be explained within a youtube comment. The property of being a GCD domain passes from a ring to its polynomial ring, however this is not true for atomic domains. In particular there are (exotic) atomic GCD domains R such that R[X] is not atomic, so taking the existence of such domains as a given we can give a counterexample to the statement: R[X] is a non-atomic GCD domain and X is an irreducible element.

[@KoolManPhat]

Amazing video

[@KrasBadan]

Nice video!

[@loganm2924]

Ayy a set theory video!

[@XGreenEagleX]

Amazing video, helped me ao much with understanding my courses in physics degree Thank you so much, waiting for more well made vids!

[@SigmaChuck]

Really enjpyed this.

[@Lagartox666]

Amazing content Bro

[@Bunnokazooie]

I immediately hit subscribe after you presented Euclids proof so well.

[@timh2859]

Phenomenal

[@egohicsum]

great video

[@inciaradible7144]

I remember first learning about this in university; it honestly makes infinity feel like something you can grasp. The bijection argument for sets being the same size is just so intuitive.

[@moshecallen]

I gather your channel is just starting. So, I'm sure things like sound quality will improve as you gain experience. The presentation is excellent. I feel like it's stuff I know or thing I know but I'm not sure I've gone through the proofs myself as thoroughly as I should.

[@shreymehta4973]

i love this. professor tao must see this

[@BrunoWiebelt]

mind blowing

[@mehdimabed4125]

Hey ! Really great video, love the musics and the overall tone ! By the way, I was wondering, I read here and there some ways to construct bijection between R ans R^2, so does it mean that |R| =|R^2| ? And if so I suppose we could show by induction that |R^n| = |R| ? Can we go further ? Thanks !

[@relaxnation1773]

any R^n with an nthat is finite will have a bijection to R, using space filling curves

[@pietrocelano23]

Yes, |R| =|R^2|. the most famous proof of this is by showing that there is a bijection from [0,1] to [0,1]^2, meaning the unit segment to the unit square. this bijection takes the form of the Hilbert Curve. Then, you can prove |R|=|R^n| for any R. i think this holds for any infinite set, not just those of cardinality |R|.

[@biblebot3947]

R^inf has the same cardinality as R

[@AbelShields]

@@biblebot3947 are you sure? If something holds true for a sequence, it's not necessarily true in the limit - think of the sequence of sums S(1/n!) as n->inf, that's rational at every finite step but in the limit its equal to e, which is irrational.

[@biblebot3947]

@@AbelShields c=2^aleph_0 |N|=aleph_0 |R^N|= (2^aleph_0)^aleph_0= 2^(aleph_0^2)=2^aleph_0

[@barigamb]

This video is really underrated.

[@dct7b]

The Jain conceptualisation of infinity is far more sophisticated and useful than the countable/uncountable ontology. It would be interesting to see you describing their work many many years before Cantor.

[@cosmicvoidtree]

Here’s an interesting set. Start with a pair of coordinates which can be any natural number. We could say that this is N^2. If we introduce another coordinate so it looks like (a1,a2,a3) for all an contained in N, call it N^3. Continue adding coordinates until we get to N^N. The sizes of the other sets N, N^2, N^3, N^4,… all have cardinality of N (which you can prove for any finite number of coordinates using a recursive sequence of bijections taking the first 2 points and converting them into one point). With this knowledge, what is the cardinality of N^N?

[@MikeRosoftJH]

Careful: what do you mean by N^N? What you have constructed is the set of all finite sequences of natural numbers, which indeed is countably infinite. But I'd argue that N^N is the set of all functions on natural numbers - in other words, the set of all infinite sequences of natural numbers - and that set is uncountably infinite.

[@pierreabbat6157]

What's your take on the continuum hypothesis?

[@nagyabel937]

You can also describe a funcion (N+->N+) in binary like this: Example: 3, 2, 11, 4, 2... -> write 3-1 = 2 zeros, write 2 ones, write 11 zeros, write 4 ones etc. This is an alternative way to describe it without the issues in 19:57

[@jcsahnwaldt]

But you still have the problem that a sequence of zeros and ones that ends with an infinite sequence of zeros or an infinite sequence of ones does not correspond to a function.

[@suseongcho2927]

GO JHANN!! I’m your biggest fan!!! 🎉

[@JojiThomas7431]

Very beautiful

[@shadowcrafter01]

4:55 A bijection is by definition injective and in the example graphic you showed, you have equivalent elements of Q (1/1, 2/2, ...) assigned to different natural numbers. And since a bijection works both ways that would mean that different x map to the same f(x). Thus the function is not injective and the example doesn't show a bijection.

[@ProfeJulianMacias]

Excellent Problem

[@michaelwoodhams7866]

Paraphrasing your closing comment: our curiosity goes ... TO INFINITY AND BEYOND! (The closing comment: "The fact that we can talk and conjecture, prove and study these ideas, these astonishing and intense infinite concepts shows that our curiosity, our logic, its not bound by simply applications in the physical world. It surpasses that. It literally goes beyond what we can count.")

[@dsagman]

Excellent stuff. Would love to see something on fast growing functions and omega, etc. Also please a little less volume on music.

[@lexinwonderland5741]

agreed, i think he would do a fantastic job explaining limit ordinals considering how comfortably he explained infinite cardinals!

[@Wielorybkek]

good content :D

[@TheoriesofEverything]

Great video man. I shared it in a recent video on "math channel recommendations." (albeit only the description) By the way, do consider submitting to the contest on the channel. Email me for details if you're unsure. Continue the enlightening work.

[@jHan]

Thank you! I'll definitely check it out

[@dliessmgg]

I have a question! When you started talking about powers of two, I thought about a function that maps the power set of the naturals to the natural numbers as follows: A is a subset of the natural numbers A -> sum(2^a, for all a that are elements of A) this seems to me to fulfill the properties of a bijection: - different powers of 2 will lead to different sums, therefore different subsets of the natural numbers get mapped to different numbers with this function - any natural number can be described as a sum of different powers of 2, therefore this function reaches all of the natural numbers I'm sure there has to be some kind of error in this thought process, I just can't find where it is.

[@saschabaer3327]

Subsets of the natural numbers can be infinite (e.g. consider the set of all even natural numbers - what does it get mapped to? 1 + 4 + 16 + 64 + … → ∞), in which case the sum does not converge. Your function describes a well-defined bijection between the natural numbers and the set of FINITE subsets of ℕ, which proves that this set is countable, unlike the set of ALL subsets of ℕ.

[@dliessmgg]

@@saschabaer3327 Ah, that makes sense. Thank you!

[@mattkafker8400]

Nice work. Is this for 3Blue1Brown summer of math competition? In either case, looking forward to seeing where this channel goes.

[@jHan]

Yup! Thanks for the kind comments!

[@luismuzquiz]

Beautiful. And a little insane also! hahaha.

[@swaree]

I see some Vsauce inspiration, great work, subbed right away

[@Davidku632]

Nice

[@JamesSpeiser]

Bravo

[@liijio]

Proving continuum hypothesis , proving inconsistency in ZFC , constructing ZFC from naive set specification , resolving Russell's paradox , constructing infinite number system , construct and ensure overall consistent mathematical universe and developing arithmetic system - edition 8 May 2024 DOI: 10.13140/RG.2.2.21713.75361 LicenseCC BY-NC-ND 4.0

[@wandrespupilo8046]

super well made, but i have to point something out For you to assume that it's obvious that N^N is the set of all positive integer functions (not explain why) but then to assume that induction isn't obvious is pretty weird

[@valkopuhelin2581]

I liked the music. :-)

[@llunaecy]

When showing the bijection between the naturals and the rationals around 4:48, wouldn't the mapping you showed not actually be a bijection, since you have multiple different naturals mapping to rationals with the same value? (For example, 1 maps to 1/1 = 1, 5 maps to 2/2 = 1, 13 maps to 3/3 = 1 and so on)

[@johntaylor2683]

they are stll rational numbers, the fact some rationals my reduce to natual numbers is irrelevant.

[@MikeRosoftJH]

@@johntaylor2683 Not quite; 1/1 and 5/5 is the same rational number.

[@shuhulmujoo]

I'm not sure if the bijection in the video is valid or not, but there is a bijection between the natural and rational numbers. Look up the Catkin Wolf tree

[@Treebark1313]

Loved this video, it really exemplifies how a proof can (should) also be a narrative. I'm not sure it's correct to say that there is a bijection f: X -> Y if the function is not invertible for all elements of Y. Wouldn't it be more rigorous to say there is a bijection f: X -> Y - {non-invertibles}, and argue that, because the non-invertibles are countable, Im(f) and Y have the same cardinality? Might be pedantry, but some the beauty of the proof comes from its nuance!

[@dct7b]

Excellent presentation, I hope you keep that enthusiasm for all your work, it will help many people understand diffucult topics. Unfortunately the Cantorian paradigm is fundamentally broken. Thankfully the repair is much more interesting and useful, and remains intuitive. To see what I mean:, the power set of the primes (countably infinite) is again countably infinite (square free numbers). In fact, we require the power set of infinite multiplicity to obtain a bijection with naturals, as per the fundamental theorem of arithmetic. Also, the set of integer functions maps directly to the algebraic numbers which are supposed to be countably infinite. Also, diagonalization only works if there is only one mode for the elements in the set, otherwise, the number created by diagonalization appears after the first level and the diagonalization has stopped. The Natural Numbers are the continuum. Irrational numbers are literally lists of rational numbers, they do not fill between them in quantity, but between successive elements in a list of rational such that we use the one required at the appropriate granularity. We are tossing away information to treat all countables as the same size, when it's easy to see that using a piecewise function to establish a bijection means the one set is made up of that many different copies of the other, one for each piece. Think about it, nothing has changed to prevent pathological bijection in our infinite context in the way we do the bijection compared to a finite context. But this is absurd, as we know finite and infinite sets cannot be counted in the same way. Also the powerset equation 2^n is flawed. For example, the powers set of possible dice rolls on a fair 6 sided die given 5 rolls, is 6^5. I could go on...

[@nin10dorox]

The set of integer functions maps to the algebraic numbers? Do you have any suggestions where I could look to understand that? I just googled it and didn't see anything show up.

[@dct7b]

@@nin10dorox non-rational algebraic numbers are existentially, I. e. by definition, the roots of polynomials of degree at least two. Since we can clear rational denominators, we may consider polynomial functions with integer coefficients and degree at least two, a set more or less isomorphic to the algebraic numbers. All algebraic numbers have such a polynomial associated, and all such polynomials have algebraic roots, unless transcendental.

[@jcsahnwaldt]

The power set of the primes is not countable. The set of square-free numbers is countable, but the power set of the primes contains infinitely large sets, from which you cannot get finite square-free numbers.

[@Channel-dp3wc]

🔥

[@bobh6728]

“alwalys” is that all walleye fish? Great video

[@infty1369]

wow, you actually deleted the discussion great work, that is how spread the light.

[@jcsahnwaldt]

Minor correction: The "if" at 7:37 should be "iff".

[@ilikemitchhedberg]

The uncountable set fanatic 🤓☝ vs the Big Omega Enjoyer 💪😎

[@user-tk2jy8xr8b]

So, R is nothing more than N->N? Can a Cauchy sequence, defining elements of R, be somehow analyzed as N->Q (index to a decimal truncation), and since Q~N, as N-> N?

[@jHan]

That's a real interesting thought, and I think it does really fit nicely together, as Cauchy sequences can be seen as functions N->Q. The set of all functions from naturals to rationals (Q^N) has the cardinality of the continuum (as |Q^N|=|N^N|). Of course, not all functions N->Q can be represented as a Cauchy sequence, but since Cauchy sequences can describe every real number, the cardinality of the set of all Cauchy sequences would be that of the continuum.

[@user-tk2jy8xr8b]

@@jHan more on that: half of a Dedekind cut is R represented by essentially Q->2, which is isomorphic to N->2, which is a powerset

[@Bodyknock]

Great explanation but I was a little surprised there was no mention of the Continuum Hypothesis (that there is no set whose cardinality is strictly between the Naturals and the Reals). Obviously the details of that are beyond the scope of this introductory video but it's a pretty easy to grasp what it's saying once you understand the basics of infinite cardinalities and it's one of the most famous problems in mathematics (it was even the first of Hilbert's 23 major unsolved problems at the turn of the 20th century.) As it turns out you can assume this hypothesis is either true or false in the main branch of set theory that includes the axiom of choice and the results remain logically consistent either way. It's an example of a statement that sounds really simple on the surface but once you try and precisely figure out if it's true or not you run into a mire of questions that really get into the heart of what a set even is in the first place.

[@elizabethharper9081]

AC is not needed to formulate CH.

[@Bodyknock]

@@elizabethharper9081 I didn't say it was.

[@angrymurloc7626]

The end of the video is a bit misleading. You cannot have a bijection that computes a real number from every subset of the naturals by just adding powers. If that were possible you could do the same for the naturals as well, just with positive powers and not negative ones. This procedure fails because there are subsets of infinite size inside P(N), and the function would fail to find their value in finite time because it needs infinite steps to conclude. This is what the continuum hypothesis is all about

[@Mathhead2000]

Maybe I missed it, but did he show why |(0,1)| = |R| ? Amazing video!

[@jHan]

I made a previous video explaining that if you want to check it out: kzbin.info/www/bejne/r2itn5ljh6p1e68 Thank you!

[@Mathhead2000]

@@jHan Thanks!!

[@higumidere7257]

What would the cardinality of all functions be including arbitrary functions?

[@MikeRosoftJH]

I haven't viewed the video, but I understand that what is meant is the set of all functions on reals (R -> R). A function is a set of ordered pairs; if [a,b]∈f, then we by convention say that f(a)=b. (The set of all functions on reals has strictly greater cardinality than the cardinality of the continuum; but it can be shown that the set of all continuous functions on reals has the same cardinality as the continuum.)

[@bjao8619]

For the argument at 7:48 shouldn't you also include a, if n is an element of S_n, n is not an element of S? Or else the set S is just a string of Y's which we can't say does not exist.

[@jHan]

That's a good point, and there would be nothing wrong with including that. However, these sets are not strings of Y and N; I just used them in the table to make visualization easier. In reality, we want S to have the opposite of what the main diagonal of the table has. So since S1 has 1, it won't be in S (and we don't necessarily need a line for that as 1 isn't in S to begin with). Same goes with S2 and 2. Since S3 does not have 3, S will have 3. Continuing this process for every natural number, S will be different from every set on our infinite list. Hope that helped!

[@bjao8619]

@@jHan ah okay, thank you so much!

[@wChris_]

Jhat(double struk H)alphaAleph, what does ℍ mean again?

[@jHan]

It's the set of quaternions

[@dk6024]

Good stuff, ditch the background track.

[@ojas3464]

👍

[@spudhead169]

You don't have to randomly assign a real to natural, you can just reverse the digits of the natural and pop a 0. in front of it. So 1 -> 0.1000..., 10 -> 0.01000..., 4319 -> 0.91340000... etc..

[@pinkraven4402]

One of the easiest bijections between (0, 1) and R is y=tan(pi*x)

[@allozovsky]

*y(x) = tan⁻¹(x)/π + 1/2* looks nicer (though essentially the same, of course)

[@pasc4433l]

At 12:27 I can't understand how we got f(n)≥fi(n) since we proved before that f1(n) + f2(n) + ... + fn(n) is strictly greater than fi(n)

[@allozovsky]

But f(n) *_is_* that sum. It has no subscript.

[@yopenzo]

But if the power set of a set also contains the set itself, it means that there is a subset of N (that is N itself) that it contains all ns. Therefore we always have y in the table. Then?

[@MikeRosoftJH]

I am not sure what you are asking. Here is a function from a set to a set of its subsets: x -> {x}. (Any element is mapped to a one-element set containing that element.) It can be seen that the diagonal set is the empty set; and indeed no element is mapped to the empty set (every element is mapped to a one-element set). We could get a different mapping, and indeed some element can be mapped to the whole set N (no matter what that set is). But either way, there are exactly two options: either the set f(n) doesn't contain the element n, in which case the diagonal set does; or f(n) does contain the element n (which is the case when f(n) is the whole set N), in which case the diagonal set doesn't. Either way, f(n) differs from the diagonal set precisely by the inclusion of n itself.

[@mujtabaalam5907]

Why is the cardinaliry if the set of all integer functions |N^N| and not |N^2|

[@jHan]

The set of all functions from one set (say A) to another set (say B) is denoted B^A. So all positive integer functions (which its domain and codomain is N) can be represented as N^N.

[@usuraiopeppino]

N^2 is the set of all couples (n.m) of integers numbers. You can identify it with the set of all functions from {1,2} to the set of natural numbers with a bijection: the couple (n,m) correspond to the function defined by f(1)=n and f(2)=m. This can be generalized to other common cartesian products, like R^n cen be identified in the same manner with the set of all functions from {1,2,...,n} to the real numbers.

[@angelmendez-rivera351]

@@usuraiopeppino I think you mean the set of all functions from {0, 1} to N, or more succinctly, the set of all functions from the set 2 to the set N.

[@usuraiopeppino]

If you're only interested in the algebraic structure of N^2, then there's no big difference in defyining the set 2 as {1,2} or {0,1} where the elements 0, 1 and 2 are integers. But I guess 2={0,1} is more consistent because every symbol can refer both to a set and an integer number; while saying 2={1,2} is an abuse of notation (first 2 is a subset of N, second 2 is an element of N) but makes clearer we're dealing with a first number and a second one as in a couple.

[@seraphik]

the title of this video sounds like star trek fanfic

[@yogeshkumar778]

A small error at 6:41, the spelling of "always" is wrong. But it's perfectly okay!

[@gigog27]

Can someone explain to me why 1/2 being 0.0111111... and 0.1 at the same time isn't exactly identical to 1/10 being simultaniously 0.1 and 0.0999999....?

[@MikeRosoftJH]

It is precisely the same thing (except in base 2 rather than base 10). It follows: mapping a real number to its base-n expansion is not a one-to-one function. (But real numbers and base-n expansions can be mapped one-to-one, because they only differ by a countably infinite set.)

[@That_Guy_You_Know]

Music is a bit to loud, hard to focus and its hard to hear you through it.

[@rangedfighter]

For 7:49 how do we know that our new set S is not empty? Edit: Ok I got it, it's not a number that isn't in any set. Our set is basically just the union of the complements of each set. But wait, isn't that just our original set. Because our new set contains every number from the original set. For every number in N, there is a subset that doesn't contain the number, so our new set S is just equal to N.

[@MikeRosoftJH]

No; the diagonal set is precisely the set of elements n of the original set N, which our function f maps to a set which doesn't contain n. For any element n there are exactly two possibilities: either f(n) contains n, or f(n) doesn't contain n. The diagonal set is the set of all elements for which the latter is true; and it can be seen that for any n does f(n) differ from the diagonal set precisely in the inclusion of n itself. And indeed the diagonal set could be an empty set. For example, let f be the function n -> {n}. (Every element is mapped to a one-element set containing that element.) Then the diagonal set is empty, and indeed no element is mapped to the empty set (because every element is mapped to a one-element set).

[@jcsahnwaldt]

The "if" at 7:37 should be "iff". Maybe that would fix the problem you describe?

[@General12th]

Mega nifty!

[@scebsy6524]

music is very tense around 8:00, hard to focus

[@barutaji]

One thing about the binary conversion makes me confused. Take the set of real numbers between 0 and 1. Every number can be associated with a binary sequence and vice versa (except for an infinite countable number of exceptions). On the other hand the natural numbers can also be associated with a binary sequence and vice versa, so it would seem to imply that both sets have the same cardinality. The only difference between the two is that we would have to put an infinite sequence of 0s to the left(naturals) or to the right (reals), which does not seem to be that relevant at first glance. So where is the solution for the apparent contradiction?

[@pasc4433l]

I think it's not the same sequences at all because except for the real numbers which have a finite number of digits (which can be mapped one to one with the sequences representing the naturals) there is an uncountably infinite amount of real numbers with countably infinite digits, and this results in the formation of (uncountably infinite) infinite sequences that can't be mapped one to one with the naturals.

[@U20E0]

The difference is that no natural number is ever going to produce an infinitely long binary sequence

[@barutaji]

Yeah, that's a really good point. Thanks

[@TheMarioRD]

A great video to show how large can the infinity be! I think what you are showing is "continuum hypothesis", which is one of the Hilbert's 23 problems. Unfortunately, your argument cannot prove the continuum hypothesis, because using your binary encoding, you can only get a surjection from R to P(N), not a bijection mapping. To show two infinity sets are of the same size, you must show a bijection between two sets exists, i.e. each element in one set must map to another set. But in your argument, you have "taken out" p/2^q in the real number set. This step makes your binary notation not a bijection mapping from R to P(N). Don't be upset! The "continuum hypothesis" is shown to be not provable under set theory, i.e. you cannot show that whether R or P(N) is bigger than another using set theory. So if anyone say that they have a prove on this topic, 99% is wrong. But this video is still enjoyable to watch. Everyone make mistakes, mistakes will make everyone stronger.

[@jHan]

The continuum hypothesis says that there does not exist sets that have the cardinality between the integers and the reals, which means |R| = Aleph_1, the smallest cardinality after Aleph_0. Aleph_1 is defined by ordinal numbers, and is not defined by P(N) or R. While it is true that the continuum hypothesis is independent from the widely accepted Zermelo-Fraenkel set theory (and the axiom of choice), this video does not discuss ordinals nor aleph_1. In fact, the continuum hypothesis is not mentioned nor alluded to in this video. |R| = |P(N)| is NOT the continuum hypothesis, and you can definitely prove |R|=|P(N)|. The reason the binary notation argument works is because of the No Countable Difference Principle (discussed in this video) that proves bijections between infinite sets even with countably infinite sets being added or subtracted.

[@TheMarioRD]

@@jHan My bad 😭. My mistake (Everyone makes mistake anyway) Sorry for my misunderstanding, and thanks for your clear explaining.

[@Lincoln_Bio]

I'm not super convinced on the uncountable infinity of the reals, I don't see how Cantor's diagonal argument holds in such an infinite set as by definition it already contains every digit in every possible combination, and I'm pretty sure I found a bijection between the naturals and the reals of the unit interval that appears to work in any base n algebra. If I ever get round to rigorously defining this thing I could really upset some mathematicians, which would be fun.

[@Shyguy5104]

yeah you'll "upset" mathematicians by doing that in the same way as the troll science comics "upset" scientists

[@Lincoln_Bio]

​@@Shyguy5104 Depends if I can be bothered learning enough maths to prove it tbh, seems unlikely

[@Lincoln_Bio]

Ah wait I think what I've actually stumbled on here is the equal cardinality of the reals and the power set of the naturals, which is cool, but already a thing. You win, Cantor.