Integers & Reals have different, infinite sizes! **Cantor Diagonlization**

In the first episode we saw that the integers and rationals (numbers like 3/5) have the same "size" - that is there is a bijective function so that you can line up the integers and rationals even though they are infinite sets and even though the rationals has elements like 3/5 that aren't in the integers.

In this episode, we now compare the integers and the REAL numbers. Using Cantor's Diagonalization Argument, we attempt to list all the real numbers - that is, find a bijection between the integers and the reals. However, we then construct a new real number not on the list, which shows that the reals and the integers can NOT have the same size.

*******************************************************
*******************************************************

Now it's your turn:
1) Summarize the big idea of this video in your own words
2) Write down anything you are unsure about to think about later
3) What questions for the future do you have? Where are we going with this content?
4) Can you come up with your own sample test problem on this material? Solve it!

Learning mathematics is best done by actually DOING mathematics. A video like this can only ever be a starting point. I might show you the basic ideas, definitions, formulas, and examples, but to truly master calculus means that you have to spend time - a lot of time! - sitting down and trying problems yourself, asking questions, and thinking about mathematics. So before you go on to the next video, pause and go THINK.

Hope you enjoyed!

BECOME A MEMBER:

MATH BOOKS & MERCH I LOVE:

[andrewharrison]

There are a few proofs that just stand out for their simplicity and impact. My top 3 would be:
1) There are an infinite number of primes
2) The rationals are countable
3) The real numbers are uncountable - thank you Cantor
Glad to see you have covered all 3.

[nullbrain]

THANK YOU!!! You seriously made this SO much easier for me to understand. The way my book explained it I didn't understand why we cared about the decimal places of randomly chosen numbers but what I can clearly see in your video is that we are using those places to ensure that our number that we are creating is not on our list of "all the real numbers" between 0 and 1 by making sure that our number we create varies at those specific locations.

[Makebuildmodify]

Question: How is creating a new diagonalization different than adding another integer to the end of the countables?

[a.nelprober]

Easiest no bs explanation of the concept I have ever seen. Superb Trevor. Love you man

[morschlesinger]

my brain.... I thought hearing this in English would make it easier...

[cavestoryking]

The end of the video is a bit inaccurate. There is necessarily no number between Aleph Null and Aleph One because we define Aleph One to be the next largest cardinal with nothing in-between. The real question would be whether or not there is anything between Aleph Null and the continuum, or Aleph Null and Beth One.

[chimchady]

I was so confused when watching the lectures from my university. rewinded every minute and still didn't understand anything. found this video and now im so thankful! this is perfect!

[jlgropp]

I've read this proof a number of times and now it makes sense. Thank you.

[patrickwithee]

FYI, that the continuum is of size Aleph 1 is just a statement of the Continuum Hypothesis. The Aleph numbers index sizes of infinity, while the Beth numbers index the climb up the powerset ladder starting at Beth Null, which is equal in cardinality to Aleph Null.

[biopolis]

I followed you well to a certain point. Then I have the question: how do you know 0.24206558 is NOT on the list? The list has been made randomly. So, what does prevent it to actually HAVE that decimal (by chance)?

[bash]

Can you explain a little more as to WHY we can't use the same argument we did to prove the rationals or the even numbers are countably infinite with the reals? Is it because we can't find a one to one correspondence or a rule between the natural numbers and the reals but we can create one with the rationals/evens etc. What happens if you use cantors argument for natural numbers? Can we?

[ABHAY-hukw]

how can we say that no. isn't on the list ?, did we counted to infinity? to ensure about this no. which is not in the list ??!!

[colinjava]

Great, but slightly screwed up at the end.
The reals have size c or beth1, you have to presume the continuum hypothesis is true to say c = aleph1.
If continuum hypothesis was false then c would be aleph_k for k>1 (unless there's an infinite number of infinities between aleph0 and c).
You could just write 2^aleph0, that would be better.

[Moronoxy]

What is the proof that the diagonal set is not on the list of the natural set?

[Winchester_]

Great explanation! My textbook was way too wordy, just making the concept confusing ... you were brilliant!

[pickyphysicsstudent]

I don't get how the diagonal paradox is only applicable to the infinity of real numbers between zero & one but not for the set of integers between zero & infinity? Surely, you can just pull the same trick for the integer matrix by increasing the digit of each value for the numbers, based on their placement in the matrix, just as with the decimal matrix.
That method would also create a new number in the integer matrix which is not the same as any of the other numbers because it shares a different digit with each number already presented in the matrix.

[Adventures_of_Marshmallow]

There's no question that there are different sizes of infinities.... However, I think the part of the trouble in understanding the infinite is treating them with logic that is fundamentally temporal in nature rather than seeing them as complete objects. There is a distinction that can be made between a set that is 'endless' and a set that is 'of infinite size, but complete'. Object based logic casts infinites into quasi-finite territory and 10^oo > oo holds true. This proof is no longer valid in that case. 1: Exploring a small subset and given only 3 digits, the number of possible sequences is 10^3 and is the exact size of our lookup table. The *length* of any sequence any diagonalization can produce is 3. A table with 10^3 unique sequence entries, will indeed contain any possible sequence that is 3 digits long. 2: Given an infinite number of digits the number of possible sequences is 10^oo while the length of any possible diagonalization is oo. A table with 10^oo unique sequence entries will indeed contain any possible sequence any diagonalization of an infinite number of digits can produce. The number of possible sequences of digits is much, much larger than the number of digits.... even at infinity. Treating infinites as 'complete objects' rather then 'endless procedures' fixes the bad logic that a complete table is *somehow* incomplete. But hey, that's just my view....

[notloc]

I’m confused, how do we know if we didn’t expand the list, that the number you made above from the diagonals will not be there? How do we know the function CANNOT produce that sequence?

[kayyumamcaoglu]

But how can we be sure that the new number between [0, 1] we created isn’t equal to any singular one already on the list? The new number is still between 0 and 1 and we already listed all the real numbers between 0 and 1

[darcash]

Are there other ways to do this and still achieve the same result?

Like for instance, wouldn't something like this work?:

Let's say that we say that we can count it. Let us also restrict our counting mechanism such that the numerical value is determined by negativity & positivity and distance from 0. Element 1 = 0. Element 2 = 0+, Element 3 = 0-, ... (Element 4 = 0++, Element 5 = 0--, where more +'s and more -'s suggest further distance, just how close it is to 0.) and it goes on like that infinitely. Well, lets just divide all of that by 2. Then we have a positive element even closer to 0 than the original element 2, element2/2. Therefore, this would be the new element 2. Likewise, we would have also replaced element 3 with its division by 2. In the same way, these were not on the list we had, and needed to be added. So it is not countable.

If this does not work, why not?