S01.9 Proof That a Set of Real Numbers is Uncountable

MIT RES.6-012 Introduction to Probability, Spring 2018
Instructor: John Tsitsiklis

License: Creative Commons BY-NC-SA

[mikevaldez]

I love this proof; well exposited here. Ever since I discovered it in the math section of the Theodore Geisel Library. Cantor was awesome. So brilliant.😊

[Rlay]

Thank you for that great explanation! Only using 3s and 4s and not some letters with two subscrips really helped here!

[jiaminghu]

I am not curious, just need to pass my exam. But the explanation was impressively clear, thnaks.

[LedCepelin]

My book had a more general form of this argument so I got lost. This really clarified the point of the proof. Thanks so much!

[GoogleUser-eero]

it looks to me that the idea behind Cantor's contradictory proof is that no matter what decimal number one constructs between 0 and 1 with digits appearing according to certain rule, one can always find a number within the set which breaks the rule.

[willc]

Help! I am confused here: can't we use the same argument on natural numbers to prove the set N is uncountable (which obviously is wrong): since the natural numbers can increase indefinitely, we have unlimited number of digits to work with (just like in this case), and therefore we can always construct a new number not in the set. As a matter of fact, after the part of 0., the digits of the real numbers would resemble natural numbers right?

[pizzaman]

This makes so much more sense! Beautiful proof!

[mega]

i thought i had understood it before but only now have I really grasped the amazing concept of this; by definition that number is made to not be like any other. amazing ong

[ziad-explains]

How could we know for certain that the new generated x didn't figure in the set? It could coincidentally match an element of the set, couldn't it?

[EhsanAmini]

What if we bake that number into our construction algorithm in the following way: We first enumerate all the numbers with a 1 digit expansion, of which there are two: .3 and .4, we then carry on with the ones with 2, 3, 4, ..., n digit expansions for each of which there would be a finite number of items. And since, for each number of digital expansions, we have exhausted the possibilities, it is no longer possible to construct a number that is not already listed or would not be listed in this manner. Why can't this list be paired off with positive integers? .3, .33, .34, .43, .44, ...

[bholster]

You explain and I now understand the argument. Thank you.

[Awesome]

Decided to see if I would understand this 2 years later. My lecturer sucked, thank you!

[siarez]

I still don't get why you can not make such an argument with rational numbers. It's not like one will run out of rational numbers.

[silviapetrova]

everyone uses this proof but only here did i get it. thank you

[dhananjayjhala]

Made me understand this so easily, thank you so much, short and clear video :)

[SecretEscapist]

Thanks a lot for this amazing lecture ☺

[briancabana]

I find it unconvincing as presented. Why not label the x indecies x10, x20, x30; etc.? That way, any diagonalization could be fit in x2 or x3.
You'd have to demonstrate that there is a 1-1 and onto relation between the counting numbers an your specific set of decimal expansions before presenting this type of argument for a new and as yet unlisted decimal expansion

[swnky]

how could we prove that any non-empty interval (a, b) has 1-1 correspondence with the reals? is it because they are both uncountably infinite?

[TheGamingWattsit]

Why can’t we have long strings of 9s at 3:08

[Zenovarse]

x1:
x2: .43333.... 00001
x3: .34333.... 00010
x4: .44333.... 00011
x5: .33433.... 00100
Diagnolizing the first 5 digits gives
...
x31: .34444... 11110
x32:

So surely I can do this, and the diagonalization of the first n elements to n digits will be part of the set later on?