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

[@mikevaldez7684]

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

[@jiaminghu349]

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

[@Justokay4525]

Me too. I am from India. And you know our education system is just worst.

[@aliyagzcaniguroglu5851]

​@@Justokay4525yours can not even race with Turkish educaction system hahahahahah

[@patates1165]

@@aliyagzcaniguroglu5851 yok onların ki daha sik gibi aga

[@ybiitbhu]

@@aliyagzcaniguroglu5851 bro be living in delusions whole life

[@R3lay0]

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

[@popadic_backo]

But It's how they want us to know it :D

[@913egok]

The explanation is amazingly good yet concise.

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

[@mattkearns5195]

For those interested, the Aleph numbers are used to denote the cardinality of infinite sets. See en.wikipedia.org/wiki/Aleph_number

[@GoogleUser-ee8ro]

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.

[@tyfoodsforthought]

I had the same conclusion. Therefore? An uncountable set is a set in which it is always possible to find another number not in the set.

[@willc4857]

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?

[@tonyduarte417]

I think the answer is that any natural number has a finite number of digits (unlike the real numbers which can have infinite decimals). Rational numbers can have unlimited number of decimals (like 1/3) but there is a rule there, without that pattern of repetition, rational numbers will also have a finite number of decimals. I hope someone clarifies it more, but I found your question really clever.

[@willc4857]

@@tonyduarte417 Thanks! This makes sense. It indeed seems to come down to the number of digits permitted. Real numbers have the luxury of going infinitely that never end.

[@kirizenkirizeto3492]

same confusion, maybe this proof is not a good example for uncountable sets' definition, just make me puzzled

[@mega3455]

you can't achieve that type of number which by definition acts as uncountable outside the irrational set. We're talking about an infinite number here which works based on how the counting system works - that can obviously not be represented by fractions

[@tobiassugandi]

It is by definition I think that countably infinite set can be mapped one to one with the natural number. So it’s infinite but it’s somehow countable because it’s a natural number

[@99570Awesome]

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

[@pizzaman1015]

This makes so much more sense! Beautiful proof!

[@mega3455]

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

[@bholster8073]

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

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

[@JJ-jc8jd]

I think that's because in this case you will have a set of rational numbers (the number of digits will be finite for each number), but rational numbers are countable. The key point of the proof is that each element has infinite number of digits in the decimal expansion

[@analog_dreamer]

This explanation is just excellent!

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

[@marco-mag-waffeln4804]

I'm a bit late haha but just to clarify a bit: (Correct me if I'm wrong please) In the proof the new number is constructed by going through the set of all possible number with 3 and 4s as decimals. We assume that we have a map from N to the elements of the set and thus assume it is countable. One by one we go through the elements of this set (I will call it S). We try to create a new number that is not in the set. Starting with i=1 and changing the i-th decimal for the new number. So if the 1st element in S had a 3 as 1st decimal, our new number has a 4 as first decimal. Next i gets increased to 2. Now we go to the 2nd element in S and do the same for the second decimal. This can go as long as it takes but since S is assumed to be countable it will end at some point. But the result will be that at the end you will have a new number, since the created number has at least 1 different digit in the decimals from each of the number in S. Thus since wr assumed our set included all numbers with 3/4s as decimals this is a contradiction and the set of all rational numbers with 3/4s didn't include all numbers and thus is uncountable.

[@jdserrato3792]

No because it would be generated by looking at the Si element that contains that x and it changes the ith digit to be opposite of that X which means for any x, you can always generate a new one cause the numbers are also infinetly long as you can add more digits to the end.

[@dhananjayjhala]

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

[@bdjeosjfjdskskkdjdnfbdj]

best explanation ive heard

[@jeffjo8732]

Yes, CDA is one of the most beautiful proofs. And correct, despite how non-intuitive it sounds to many when they first see it. It is often used as the archetypal example of a proof-by-contradiction. I just which it were presented correctly. All of the objections that are made to it, and there are many (including in these comments) are based on either things Cantor didn't do, or that technically incorrect as the proof is commonly presented. You take a clever half-step toward correcting one misrepresentation: Cantor did not use it on real numbers, he used it on infinite-length strings of two characters. He used 'm' and 'w', where you used '3' and '4'. That also gets around one issue with _calling_ it a number (you really deal with only the decimal representations of numbers), where you could get infinite '0's or infinite '9's. But the claimed proof-by-contradiction is invalid. Let me demonstrate symbolically. Say you want to prove that the statement (A and B) cannot be true; or more precisely, that not(A and B) is always true. So you _say_ that you are assuming (A and B). But your derivation only shows that A-->not(B). Since this now contradicts the assumption of (A and B), you claim to have proven that not(A and B) is true by contradiction. The problem is that _saying_ you assume that (A and B) is true does not mean have assumed it in your proof. In this video, the statement A is "we have an infinite list of elements from the subject set" and statement B is "this list exhausts the subject set." You prove, directly, that any such list is not exhaustive. While you have almost proven what you want, it is not by contradiction. Yet. What Cantor argued, was that he had proven that any list x1, x2, x3, ... necessarily omits an element of the set x0. If an exhaustive list could be made, we would have the contradiction that x0 both is (because the list is exhaustive) and is not (by the direct proof) in the set that was listed. The salient point is that Cantor's contradiction is about x0, not a property of the list that you say you assumed but never used.

[@silviapetrova8562]

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

[@ms6237]

Thank you. Now it’s clear to me ❤️❤️.

[@saileshsailesh6979]

Very WELL Explained 😇

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

[@ishitashamdasani6098]

If you attempt to construct a new rational number from the existing ones, it is guaranteed that it will already be present in the set. In the case presented above, he is attempting to make a new real number which is different from all the other real numbers present in the set (since he is considering positions of digits of existing numbers while making this new number).

[@siarez]

@@ishitashamdasani6098 “If you attempt to construct a new rational number from the existing ones, it is guaranteed that it will already be present in the set.” Why?

[@rememberme5784]

@@siarez well the thing is that rational numbers have finite decimal expression or an infinite repeating decimal expression . Irrational numbers have non repeating infinite decimal expressions. So if we want to use cantors argument to prove uncountable property of rationals we have to first show that the numbers we are putting together are making a rational . This thing can not be proved so we can't use cantors technique as a tool to prove uncountable property of rationals.

[@rememberme5784]

@@siarez on the other hand there are irrational numbers in-between [0,1] . When we use cantors argument we don't have to care about the number being rational . Infact the number we are getting is always an irrational number.

[@SecretEscapist]

Thanks a lot for this amazing lecture ☺

[@brunozoller4087]

I don't understand how this proves uncountability. I could make the exact same argument for whole numbers where I just start from the back and do the same thing. Or even easier go through all the numbers, choose the biggest one and add a 0 to the back. Also as I know that even any combination of 2 whole numbers Is countable, that would mean that you could just slap a comma inbetween them (have to account for numbers starting with 0 on the second one, but that is not a big problem) and you would have a way to count all real numbers aswell.

[@jeffjo8732]

Yes, every freshman tries this argument at some point. 90% realize the mistake it makes immediately. 9% recognize it once it is pointed out. 0.9% need it explained once. 0.09% make a naive objection to the explanation, but can be convinced it is naive. (See what I'm doing here? 🤔). A whole number can only be represented by a string of digits of finite length. Try it: pick a whole number, any whole number. Call it N. Let M be LOG10(N), rounded up. You can write N with only M digits. Now, look at the _string_ constructed by this method. What is M? What is N; specifically, is it a "whole number?" Please, be in the 0.99%.

[@brunozoller4087]

@@jeffjo8732 haha I realized the mistake a day after I wrote the comment, the thought of actual infinite numbers just hadn't crossed my mind. Thank you for the explanation tho

[@keerthyr7452]

Wonderfully explained 🙌

[@tyfoodsforthought]

Brilliant! Thank you!

[@michaelmorrison3614]

Excellent and clear explanation.

[@Zenovarse]

x1: .33333.... 00000 x2: .43333.... 00001 x3: .34333.... 00010 x4: .44333.... 00011 x5: .33433.... 00100 Diagnolizing the first 5 digits gives .44444.... 11111 ... x31: .34444... 11110 x32: .44444... 11111 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?

[@webmthread2253]

you construct a new number by changing ALL rows in the table on the diagonal, so you get a new number that differs from every row by construction

[@nguyenjohn1649]

Thank you so much.

[@briancabana6380]

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

[@PP-op1ql]

For me it is also unconvincing. So I have got question. Did you find somewhere better explanation?

[@sw9nky429]

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?

[@Hivlik]

how the fuck did cantor think of that honestly

[@louerleseigneur4532]

Thanks MIT

[@nabilafathima3223]

Thank you so much for such an incredible explanation 🙂🙂

[@ArkadebMisra]

why does this proof not apply to integers. I cant seem to understand it. i can take a subset of consisting integers which have only 3 and 4 in their digits and proceed same as in the video. why is this wrong?

[@nehalreshu5137]

amazing explaination

[@mumtazsancak]

thanks a lot very good explanation

[@Bibi_Mbaape]

Doesn't make sense to me...Why do we care that some number that has ith digit different than x_i means that it doesn't exist on the interval (0,1)? There is no connection here.

[@legacies9041]

In Mathematics countable just means listable. The point is you cannot list all real number without leaving out some numbers.

[@cantorbernoulli4407]

thanks a lot mate

[@wernerhartl2069]

If each sequence goes on “forever,” how do you list them?

[@jeffreysung1794]

As an Engineer not a Mathematician. Not all infinity are equal. That’s my conclusion.

[@davidwilliansmorante9798]

And they said Cantor was crazy. :c

[@silviapetrova8562]

thank you

[@wernerhartl2069]

X doesn’t exist because it is the last element of an endless list.

[@aesophor]

Thanks! I understand it now!

[@andreamengoli4656]

Thank you!!!

[@asilvap]

Thanks!

[@johnrooney3848]

if we used the set of all the positive integers instead of [0,1] in this example, what could prevent me from getting the same result?

[@shivpatel3311]

why can't you just use this same diagonalization technique on the Integers? Instead of mapping natural numbers onto Real numbers like cantour did, let's map the real numbers onto the integers. No matter how many real numbers you map onto the integers I can just construct a new integer that is not on the list by adding 1 to every digit on the diagonal. This new integer will be nowhere on the mapping of real numbers onto integers and I can continue creating new integers that are not on the list using the same diagonalization technique.

[@tonyduarte417]

What´s stops us from saying...Ok so that number wasn't in the list of xi numbers...fine, then add that number to the list and NOW you have a list containing all numbers and so it is countable? (I know this argument is wrong, but where is the logic flaw here?)

[@whitesaladchips]

You have to map a bijective function with a countable set i.e a rational set or an integer, there will be a time when the list of countable set that is mapped to the real numbers get exhausted. Moreover a given countable set no matter how much you diagonalise it, will be finite at one point whereas irrational no's the decimal does not terminate so you have infinite numbers to add to the 'list'

[@tonyduarte417]

@@whitesaladchips Yeah, I don't think you can "exhaust" the real numbers (as there are an infinite number of them). But I got my answer, first, my question is irrelevant, since the proof by contradiction already proved the set is not countable, but even if one insists in formulating my flawed question, if we add that number to the set, then you can just run the same proof again, proving (once again) that the original assumption (that the set is countable now that we included that extra number) is wrong and hence you can continue to infinite proving that you can add as many numbers as you'd like to the original set and still not be countable. But yeah, I don't agree that you can "run out" of rational numbers.

[@legacies9041]

If you were to add the new number to the set, then I could give you another new number which is not in the set using the same method and we could go on forever.

[@mitchelllee7448]

Great video!!

[@amkhrjee]

Loved it ❤️

[@jonassteinberg3779]

fascinating!

[@Jay-ms1dv]

OMG... what a proof...

[@helenren3194]

why we cannot have a long string of nines?

[@R3lay0]

By long he means indefinetly long. 0.9999... = 1 If you had eg 0.81719999... that would be equal to 0.8172

[@ahsjsjsjbss]

You are reading numbers as letters due to which it's not countable

[@TheGamingWattsit]

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

[@jpoezi]

You want to avoid cases like 0.99999999999. Apparently it is understood as 1.

[@2-7_4-bet]

godtier explanation

[@richarddow8967]

We already know the rational numbers are countable, and the decimal expansion of 3 , 4 is a subset of the rational numbers. Therefore this expansion is countable. Similar to the mapping of each rational to the naturals, a mapping can be created for each expansion .3, .4. .33, .34, .334 and so on... identified by unique integer N. Given any decimal expansion of 3,4 given, a unique N can be demonstrated. By contrast I do find compelling the demonstration of numbers that are not rational, and will never be. Notably an infinite number of numbers that are not rational Cantor has demonstrated a number that hasn't been accounted for and therefore there always exists another number not accounted for this infinite set. I am not convinced the number he generates is not a member of the Rational numbers and therefore the decimal expansion of 3,4 is a subset of a countable set. Feels ( yes I said feels) like saying the .99999 expansion isn't equal to 1. Some people say .99999 out to the billionth place isn't 1. but the .9999...expansion is 1. And if we went through 10^100 expansions of 3,4 and all we can say for certain is that there still exists a number not accounted for?!? I am not sure what we have gained.

[@saicharanmarrivada5077]

Wow!!!

[@aligator7181]

to the author of this KZbin video. What you are peddling is wrong. It is possible to pair every real number with an integer .

[@aligator7181]

@Andrew Mugabe I do have multiple proofs. But who are you ? Any relationship to the bloody dictator who ran Zimbabwe to the ground ?

[@davidwilliansmorante9798]

You are saying then that a discrete set is equal to a continuous set

[@aligator7181]

@@davidwilliansmorante9798 What I am saying is that both the reals and the integers are infinite, and such they cannot be sized. However it is possible to pair each real to an integer without fail. I actually have the algorithms. I paired the first float which is 0.1 with the first integer 1. Then I kept going and for each float I found a unique integer. It was getting late so I had to give up, but good progress was made : Any questions, comments, suggestions ? a_big_integer:= 1497448633916616963127181081965896851132517855242988545185175166 30384323064495007739378634299929687242879459403070238694692848 13021029704849381049638290883975959184038281367764972807801753 31980125025425780968938604700982041390343717281517310291594981 15727613993573693478807848384746570630721201745552785696922613 14295626441879690391333180740312672361158960765650986034999147 07666447138921511631949703754201570277088599890724084083445934 01833396763795095830692772478903097054902994381741964765452726 97922103152404449074674842980810451342418313709987184010957810 31998127372521670393394636802208554297136315017131192796363353 85200156751254811011507959320677826006345901269104557962888541 296282316554805373858845922357224340169201; decimal_float_story:= "683181546290773680797897996210761236946428360332060576130574033 760358960550008599309593666588541380977177.1145224874385476090 33566996720548678329314343155288435378203126308499697864463925 77556944726953121877095607788689348781596858683525669906610901 74751266595263260875642759830517451452457797172808729965806812 69951404909774337681479786003474137346210675173899844833323856 40738301543572351466107819491128558634317776563600934260510377 98148852931056620341030805321145522832255493130466275171696966 43578923915604989718609366453449459360203485666524266788420114 66645859694685226593273742246761714412625722412568808848481709 46668408347275677905643992451975844514954458545606199587650458 84758129505339304287606580396915933521334";

[@aligator7181]

​@@davidwilliansmorante9798 Both sets are discrete and they are not equal to each other. Infinite sets have no sizes. However, we can come up with algorithms which match each member of one set with a member of another set without fail. The pairings can be truly esoteric, but as long as we can prove that we have unlimited access to the counter and the counted, we will succeed. Examples are more than stars on the sky : For example I can pair even numbers with the powers of 10 : 2 - 1, 4-10, 6-100... and so on. or match floats to prime numbers : 0.1 - 2, 0.01 - 3, 0.001, 5...and so on. Turns out that there are matching algorithms for all positive floats with any subsets of integers (odd, even, powers of 10, prime numbers etc. I can also match all floats with a single stream of floats themselves : e.g. 0.1 - 0.1. 0.2 - 0.01. 0.3, 0.001 and so on. I managed to write several algorithms from the most trivial (but ugly) , to the most challenging, (but incredibly elegant) Try to publish them, nobody answers my emails or phone calls. That is how I know I nailed it.

[@aligator7181]

@@davidwilliansmorante9798 Hi David, you asked a very good question. On the numberline for any given geometrical distance there are uncountably more floats than integers. (There are 2 integers from 0 to 1, but endless floats in the same range : 0.1, 0.01, 0.0000001 and so on. ) So anybody who observes this is well justified to conclude that the total number of floats simply overwhelms the integers. That is certainly true for the geometric arrangement of the floats as they are for thousands of years now. However, since both sets have discrete components, we can remove ourselves from the geometrical setup of the numberline and ask the following question : "If we pick any float ( of the syntax we specify ) can we associate it with a unique positive integer” ? This question, ( for the past 130 years at least ), when asked, was always answered with a firm NO. Until I got hold of it. Incredibly enough I answered with a resounding YES, not only once but 6 different times, each time with a perfectly working algorithm, which I coded in the Maple computer algebraic language. ========= Thank you for asking, rather than judging and insulting. It gave me a chance to explain where I am coming from in a more persuasive fashion.

[@shirleymoon9934]

the proof is clearly explained and perfectly solved my confusion 🥹🥲 (can’t really undertand the one in textbook

[@ankitsharma1072]

This explanation is just excellent!