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.
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.
@@DrTrefor thanks for the reply. Why wouldn't it be adequate to say that the set of all integers is a portion of the continuum and therefore must be smaller? I guess the same could be said for the set of all squares relative to the set of integers, and they are considered to be the same size. Oh, I see now, the difference is you cannot continually create new squares between the squares, but the continuum will always create a new number between the last two. Is that right?
exactly. why are we allowed to "create"a number by diagonalization but not allowed to "summon" another integer? frankly i am in awe that this is taken as an important part of mathematics, this is as mathematically rigorous as taking a rabbit out of a magical hat. at first i felt stupid for not "getting" it but it really is just a stupid argument that we are forced to accept in order to be not being marked as "mathematic illiterate".
@@jgmartinezmd6867 I agree with you completely. For one, the list of real numbers between 1 and 0 is infinite, so you wouldn't actually be able to finish creating a number using a diagonal.
@@jgmartinezmd6867 Because every integer is finite and therefore has finitely many digits. If you try to apply the diagonal procedure to a sequence of integers, you'll get a sequence with infinitely many non-zero digits, and this doesn't represent any natural number. (Likewise, if you apply the diagonal procedure to a sequence containing all rational numbers - and such a sequence exists - then the resulting number must be irrational.) And it's not enough that natural numbers (or rational numbers) are a subset of real numbers. Both natural numbers and real numbers have a property that the set can be mapped one-to-one with its strict superset or subset. (Infinite sets - to be precise, any set with a countably infinite subset - in general have this property.) Likewise, it's not enough that the set is dense (such that for any two different elements x and y there exists another strictly between them). Rationals have the same property, but are countably infinite. (A set being dense is a property of an order on that set, not of the set per se.)
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!
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.
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.
Here's a simple algorithm to count every number from 0 to 1 without missing a single one (in base 10): Count from 0 to infinity the same way you're counting natural numbers, but keep the decimal period in front. .0 .1 .2 ... .10 .11 .12 ... .787435 .787436 ... If there's 1 digit after the period, it will appear in the first 10^1 entries. If there's 2 digits after the period, it will appear in the first 10^2 entries, if there are K digits after the period, it will appear in the first 10^K entries. There's no number K big enough that this list wont cover, and by contruction of the list, you don't miss a single number. It must be pointed out that by contruction, this dosen't miss a single number, no matter with one you change in the diagonal argument. If you changed up to K digits, your new number will be already on the list, before the 10^Kth entry. There's no K that won't be covered, and by induction this applies to infinity.
Honestly I'm shocked this is even remotely an acceptable proof.... I mean it's simple to debunk the method. Take a 3x3 matrix. 187 256 921 I promise if you were to say 151 is not on the list of all possible 3 digit sequences you would be laughed at by the mathematical community in a very big way. The reals are absolutely the same size as the integers. Even pi has a corespondent integer, you just don't know which value corresponds until you stop computing. All this means is numbers like pi have variable correspondence determined by arbitrary degrees of precision.
@@Adventures_of_MarshmallowI think you missed the whole point of the demonstration that works only when talking about infinity. The idea is that you are creating a new number that by definition is different from every other number on the list. You do so by making sure that at least 1 of its figures is different from an already existing number. This is why you change the figures diagonally, because you want to hit all the possible numbers already associated with a natural number and make a small change. What you created is a new number that by definition is different from every possible number already associated with a natural number. Because of that it can’t be on the list, even if it is infinite.
Yeah the "proof" is faulty. You can't find a new real number to add to the list of all real numbers no matter what you do, it's already on the list. People just don't think about that part and confusing themselves
@@prophetrob It's called a proof by contradiction. We have found a real number which is both on the list (by assumption) and provably not on the list (by construction). This implies that our original assumption is wrong (that all real numbers can be placed on a list). But, it also doesn't have to be a proof by contradiction. One could simply state that no function from the natural numbers to the interval (0,1) is surjective/onto. Then, you can start with an arbitrary list of real numbers and use the diagonal argument to show that every list of real numbers is incomplete. We can construct a real number not on the list. It's the exact same argument, but without the assumption that the list is complete.
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?
If you took the exact same argumnt for the rationals, it wouldn't work because the new number you constructed, different along the diagonal, has no guarantee of being rational again.
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.
I am so curious about how this misconception became so widespread? Do you have any idea why _so many_ mathematicians confuse the aleph and beth numbers?
@@MuffinsAPlenty I wasn't aware they did. Perhaps, they forget about the continuum hypothesis and as 2^aleph0 is the next infinity we all know about, it gets called aleph1.
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)?
If you believe that the diagonal number could be in the sequence, at which position is it? It can't be the first, because it differs from the first number by the first digit after the decimal point. It can't be the second, because it differs from the second number by the second digit after the decimal point. And so on - for any natural number n does the n-th number differ from the diagonal number in the n-th digit, and the two numbers can't be the same.
@Alejo Sanchez Sure, but if you are careful in constructing he diagonal number, you can ensure that the numbers are not equal. For example, make the n-th digit after the decimal point equal to n-th digit of the n-th number in the sequence, increased by 5 and wrapping around zero if necessary.
@Alejo Sanchez This works, too. It also shows that there are uncountably many numbers which the sequence does not cover: for every position there are at least 7 different digits to choose from (for n-th digit you can't choose the digit that n-th number has at the same position, and you may want to avoid using the digits 0 and 9 - or, alternately, the digit one higher and one lower - in order to avoid getting into problems with numbers which have two different decimal expansions).
@@MikeRosoftJH I got it now: no matter on which line of which number we look, our decimal is 'constructed' in order to be different from that listed decimal, because we change it -so to speak- the very moment we individuate it.
@@MikeRosoftJH But I have a second question now: why does it have to be a diagonal? Can't this method work even if we construct our decimal vertically on the first column? Thank you for explaining.
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....
@@Chris_5318 That's my whole point.... Infinities as objects rather than processes make them 'numbers' which are not so very different than variables....
@@Adventures_of_Marshmallow A limit is NOT a process. It is a number that satisfies a criteria. An infinite series (or product) does not have an end. Here is the definition for a series: Definition of [convergence to a] limit: Let S_n be a sequence of real numbers and let S be a real number. Then S = lim n->oo S_n means that for every real ε > 0 there is a natural N such that for every natural n > N that |S_n - S| < ε. There is no process in that whatsoever.
@@Adventures_of_Marshmallow You, "Infinities as objects rather than processes make them 'numbers' which are not so very different than variables...." You are completely wrong. No processes are involved and "infinity" is simply "that which has no end". "Infinity" is not a number, a process or a variable. There are so-called infinite (or transfinite) numbers. They are constants, not variables. They are not relevant to the topic of 1^oo.
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.
@Picky, you can show that there are as many reals in (0,1) as in (-oo,oo). Let x be in (0,1) then tan((x - 1/2)Pi) maps to (-oo, oo) and that is obviously bijective and so by definition the two sets have the same cardinality.
I'm seeing two comments in reply to your comment, neither of which address your comment. I don't know if this is a TH-cam glitch or what. But what you say is a very good and valid question, and I think I can address it: The key to why the diagonalization argument is effective in showing that the reals aren't countable, is that the decimal expansions of reals are allowed to be infinitely long; the argument describes a method by which you can invent a real number _having a chosen infinitely-long decimal expansion_ which yet must be different from all the other numbers in any given countably-infinite list: That method being, you construct your number by doing the "digit change trick", digit by digit, _forever,_ to methodically avoid all numbers which could be in any conceivable countably-infinite list, forever. And this construction then corresponds to a totally valid real number. - _But for the argument to work, you must be able to keep doing this method forever - to keep avoiding the other numbers in the countably-infinite list forever_ - which you can do _only because your own invented number is allowed to be infinitely many "choosable digits" long._ However, if you are talking about integers or anything in a so-called "integer matrix", then their "choosability" has to end at some point; the decimal expansion of an integer _must_ terminate after some digit and henceforth become blank, or all zeros, or some repetition, or some non-repeating pattern, or whatever other invariable "terminating notation" you choose to use to write it with - It doesn't matter what the "termination" looks like, it only matters that you cannot continue freely varying its digits after that point. (If its variability does not "terminate" like that then it is not an integer or anything integer-like, but rather something endlessly variable very much like a real number!) - Bottom line, if it's an integer or anything integer-like, then you cannot continue to _choose_ its digits continually forever; after it arrives at that necessary point of termination then you have to stop freely choosing its digits. And so it follows that, past that point, you can no longer continue to construct it to be unique versus all the others in the list. Once its last "choosable" digit has been written - and every integer's last "choosable" digit has to be written at some point - after that point, you can no longer continue "diagonalizing" and avoiding all the other numbers on the list. For all you know, your "terminated number" now matches another number on the list. You cannot prove it doesn't. So, this type of proof doesn't hold for integers or anything integer-like.
@@AV_TH-cam_202X "But for the argument to work, you must be able to keep doing this method forever" No. You only have to do it once. The list is supposed to have contained all the reals in (0,1). CDA then shows that there is a number in (0,1) that isn't in the list. Therefore you cannot have such a list. The end. Thanks to you I realise that I had badly misread Picky's query. I can't see what Picky was thinking of doing. None of the integers has an infinitely long representation so CDA cannot be applied. OTOH we can map the naturals bijectively to the integers. e.g. N Z 1 0 2 -1 3 1 4 -2 5 2 6 -3 7 3 ...
Picky, the wannabe diagonal "integer" would have infinitely many digits and so would not be an integer. Of course that does mean that it isn't in the list. That doesn't contradict the assertion that the list contains all the integers.
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
The new number is different from the first number on the list (because their first digits after the decimal point are different). It's different from the second number on the list (because the digits at the second position are different). It's different from the third number on the list because the third digits are different. This continues on for all natural numbers. So the new number isn't equal to any number on the list.
@MartinPoulter But you're making the assumption that, repeated infinitely many times, it'd still hold up. This goes against the idea of infinity: if a set contains all the numbers between 0 and 1, then it must contain ALL the numbers between 0 and 1...
@@hashtags_YT yes exactly this. Diagonalization of an infinite set is a broken concept. It's similarly broken if you diagonalize the set of all naturals
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?
Well. That does get me thinking. There might be a bijection between integers and reals, but is there an equal number of functions from the integers to the reals, compared to the reals to the integers? Probably not.
This seems obvious to me because decimals can expand in both directions, you can count upwards such as .1, .2, .3, .4, .5 and so on and you can count backwards such as .1, .01, .001, .0001, where that is not possible with integers.
That doesn't prove anything. By doing that you'll only cover real numbers with a finite decimal expansion, and there are countably many such numbers - all such numbers are rational, and that there are countably many rational numbers was proven by Georg Cantor.
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?
It's just a faulty assumption. You can't find a real number that isn't already a member of the real numbers. Trying to diagonalize an infinite is simply a broken concept. It's undefined You get the same thing if you try to diagonalize all the natural numbers. A lot of people are bad at thinking things like this through.
By construction, it is different from every number in the list. For each positive integer n, the diagonal number differs from the nth number on the list because it is different in the nth decimal place.
@@MuffinsAPlenty the important thing to remember is that it's not a different number that wasn't already part of the reals so this process means nothing in terms of countability of the set. It's a red herring, the set in question isn't any bigger than it ever was.
@@prophetrob No one's saying that it wasn't part of the reals. The entire point is that it _is_ a real number which is _not on the list,_ showing the list is incomplete. But this same reasoning applies to any arbitrary list of real numbers, showing no list of real numbers is complete. This proves that the set of real numbers is uncountable. "the set in question isn't any bigger than it ever was." We're not comparing the size of R to the size of R. We're comparing the size of N to the size of R.
@@MuffinsAPlenty the list is incomplete because it's not trying to make a list of all the real numbers in the first place, it's just trying to come up with a number that isn't on the finite list and people are misled into thinking about the wrong process because they imagine they can take a limit of it when really the process can't be done at all
ya know... the writing it in any order is what the issue is. write it in order and then when you start at 111111111.... by the time you get to a number starting with 3 and you went diagonal ending at the last number starting with 1 the numbers on the list. writing it down random makes the illusion its not on the list. however if you diagonally get into the 2s it will not appear "yet"
Because the argument uses the fact that the constructed number will be different in at least one digit. For the first decimal place, we choose a number that’s different than the one for the first number on the list, for the second decimal place we do the same and so on infinitely. For any nth number on the infinite list, we know it’s guaranteed to be different in the nth decimal place so it cannot be anywhere. So the new number’s 50th decimal would be different from the 50th on the list, same for the 100th and so on. So despite listing infinite numbers, we can still construct infinitely many more numbers not on the list through this
This only works when the list isn't made by reflecting counting integers in any base, across the decimal to get a bijection from natural integers to the unit interval (0,1). when this is done the diagonal is all 0's so the slash in binary is all 1's. This occurs in the limit of taking the last row of any block of 2^n numbers of n digits, then taking that limit to get .1111 repeating or for any base we get all strings of any digit across all n entries. We get .111... , .222... , .333... , .444 etc. repeating and more, we get any string of digits we like so long as it isn't matching that in the unaltered diagonal. By counting all natural numbers in this way we must be able to find all values in (0,1) from that similar fractional counting method that are missed by it. I have doubt any can be found as the method is also by combinatorics exhaustive and identical to that for exhaustive counting combinatorics applied to natural integers.
"This only works when the list isn't made by reflecting counting integers in any base, across the decimal to get a bijection from natural integers to the unit interval (0,1)." Reflecting over the decimal place is not a bijection between integers/natural numbers and (0,1). The main issue is that each natural number has only finitely many (nonzero) digits (to the left of the decimal point), whereas real numbers can have infinitely many digits (to the right of the decimal point). So something like pi-3 has an infinite decimal expansion, and reflecting that over the decimal point does _not_ give an integer.
Question: how does this work for numbers that go past the square? The shape formed by all the numbers between 0 and 1 would be a non-regular rectangle as when you list numbers of a certain distance past the decimal point the amount of numbers follows the formula 10^d=n with d being the distance past the decimal point and n being the amount of numbers.
@@gabeclements2501 You cannot list more than aleph-0 items on each side. There is one row for each natural number and one digit column for each natural number.
@@karenhartl2115 That's right and that's why I never said it was. OTOH aleph-0 is is a size. More formally it is the cardinality of the set of all the natural numbers.
If the new real number R were on the list, then there is some natural number N such R is the N'th number on the list, but then because of how R is defined, the N'th digit of the N'th number on the list is not the same as R's N'th digit, and thus we would find that R's N'th digit is not the same as R's N'th digit, which is contradictory. Thus, R can not be on the list.
I really dont understand, can someone please explain? Suppose that, to simplify things, we actually order the real numbers in such the following way: Item # | Real number 123 | 0,321... 837 | 0,738... 623 | 0,326.... Then suppose we do the diagonal trick and come up with 0,447... According to Cantor this number isnt on the list. Oh but wait, it is, it corresponds to item number 744! Even with reals that are infinitely large in the amount of digits, we will always find an integer that also has an infinite number of digits. How can we just accept that Cantors diagonal makes a new number that wasnt on the list before when, very clearly, it already was there, along with the integer that goes with it?
I disagree with their reasoning but mathematicians would say that only works for rational numbers, not for the irrational numbers with the digits that go on forever! They would say that there are no natural numbers of infinite length.
@jorge, you list is hopelss. Stick to the one in the video. No division stuff. You'll typically make many duplicates of the same number because you migh have 123/0.321... and 246/0.642... In fact you are unknowingly making a straw man argument by changing the details of what was actually said to something that was not said. The original argument is also very simple.
@@JJP-lb3ek Ooops, I had a brain fart and so hadn't noticed what you had done, my bad. However, that leaves you with several problems. Firstly, your list only contains finite length decimals. It contains no irrationals at all and it doesn't even contain 1/3 = 0.333... Aside: Your notation is appalling. I hope you meant 123 | 0.321000... 837 | 0.738000... 723 | 0.327000... Secondly, your list will actually be 1 | 0.1000... 2 | 0.2000... 3 | 0.3000... ... 9 | 0.9000... 10 | 0.01000... 11 | 0.11000... 12 | 0.21000... ... 19 | 0.91000... 20 | 0.02000... ... *NB except for the first number, the nth digit of the nth number is a 0* It will never get you an infinite decimal (i.e. one that doesn't finish with 000...) because no natural number is infinitely large. I'll ignore that for now. I'll use the replacement rules that 1,2,3,4,5,6,7 are replaced with 8 and 8,9,0 are replaced with 1. Now I apply CDA using that and I generate 0.8111... (aside: that's an infinite decimal that cannot map to ...1118 because there is no such natural number). If there was such a number, then the digit at position ...1118 of that number would be a 0 and not the 1 that you require it to be. That contradiction that it should be a 0 and a 1 is entirely down to playing fast and loose with infinity (albeit unwittingly). So your scheme failed (miserably) as would have been obvious if you only realised that CDA doesn't give a tinkers cuss about how you generated the list.
My favorite way of diagonalization is: increase the digit by 5, wrapping around by zero if necessary (d'=d+5 mod 10). That guarantees not just that the diagonal number differs from n-th number in the sequence (for all natural numbers), but also by how much (by at least 3*10^-n).
I see that you subscribe to the continuum hypothesis. Sure, of course there's no cardinality between aleph-0 and aleph-1; that's by definition - aleph-1 is the next well-ordered cardinality after aleph-0 (the smallest uncountable well-ordered cardinality). But set theory without additional axioms can't determine if the cardinality of the continuum is aleph-1, aleph-2, or something else. Worse: in absence of axiom of choice, it's consistent that real numbers can't be well-ordered, in which case cardinality of the continuum is not an aleph number at all.
@@MikeRosoftJH The cardinality of the floats and integers is identical. However, there are an infinite number of boneheaded (yes, I have a better word but let's keep it civil ) match-ups which will drive the cardinality of one or the other set to an extreme. It has been also proved that a vanishingly small subset of positive integers can count every discrete entity in the universe and beyond.
@@aligator7181 You are saying nothing but: "I am right because I say so". What you *incorrectly* call "floats" are numbers with a finite decimal expansion. Of course there are countably many your numbers; all such numbers are rational. Nobody disputes that. But Cantor's theorem is *not* a theorem about your structure; it's a theorem about real numbers as conventionally defined in mathematics. As a matter of fact your structure is *not* how real numbers are defined. (Mathematical terminology exists for a reason - so that there's no ambiguity about what you mean.) Got it already?
@@MikeRosoftJH I must ask you never to send anything to me. Expressing an opinion once, no matter how idiotic is I guess your right, but pummelling somebody relentlessly is a crime. I will report you.
@@aligator7181 It's you who is spamming your misconceptions about "floats" at any remotely related video or comment. So don't be surprised when I or somebody else responds. (And claiming that what I am saying is just an opinion - and an "idiotic" one at that - is like claiming that 2+2=4 is just an opinion.)
I can’t get how a method than never ends can be a proof. Diagonalization works with any finite list of numbers and it’s fine: it finds a new number not in list. But, since we need to use the method for a infinite list of numbers, the generation of the new number just doesn’t end.
The diagonalization argument can be done without this 'infinite' procedure, since all it is showing is that no surjective function exists from the naturals to the reals. Once can prove there is a bijection between the real numbers and the the power set of the natural numbers, so it suffices to show that there is no bijection between the natural numbers and its own power set, but you can demonstrate that is true for any set A, that there is no bijection between A and its power set, regardless if A is infinite or not. To do so, suppose such a bijection did exist, say f: A to P(A). Then the set B of all elements of A that don't get mapped to a set containing it, so all x in A such that x is not in f(x), is itself a set and a subset of A, and thus a member of P(A). Thus some member y in A must map to B since f is a bijection with f(y) = B. However, this is impossible, as such a y means that if y is in B then y is not in f(y) and thus y is not in B, and if y is not in B, then y is not in f(y) and thus since y is in A we have y is in B. Thus y is in B if and only y is not in B, a contradiction. The infinite procedure works via using real analysis to demonstrate that the constructed number at the end exists, and the real numbers are defined by the very same procedure, so you can't deny the existence of the constructed number without also denying the real numbers existing as well.
I don’t understand how this will give you a new number. I mean I get the methodology. But you would need to change infinitely many cells in order to ensure that a number further down the list is not identical to the constructed number. For this method to work you would need a complete list which isn’t possible. So maybe the argument is dual edged, because a complete list can have a new number, but an incomplete list is uncountably infinite?
i think some of you might find these observations interesting. I would greatly welcome comments on what i have suggested here......................The means which Cantor employed in his proposition of diagnalization, i.e., about the infinite string of real numbers being larger than that of natural numbers is discussed and considered in a context in which it is ignored that there is no such thing as infinity in material reality for it defies the means and manner of existence which is that anything that does exist must be distinct, delineable and quantifiable. This understanding includes the products of the realm of the abstract as well in that there is none which is not ultimately the product of the material, contextual referents in reality, that context from which they arise. For example, the abstraction of a pink flying elephant is one formed of the fusion of the material colour pink, the material phenomenon flying and the material entity, elephant. What mathematicians such as Cantor have done is employ the most general understanding of infinity as a concept but ignore the inevitable contradictions which arise, muddying the waters of the context in which their propositions are formulated and presented. 1. Consider that the infinite string of natural numbers is a progression, that which extends outward (forever). Each unit member is a value, the progression advancing by that value plus 1 each time. However, that to which it is being compared, i.e., the infinite set of real numbers is structurally the opposite within the boundaries of the proposition. • In the infinite string or natural numbers, the span between any two unit members is ignored and the line proceeds from each value to the next, extending out forever. • In the proposed infinite string of real numbers, the list of unit members from the first unit member designated to the next, any other which might be identified (e.g., 1 to 2 or perhaps 1 to 1.00000001, etc.) is itself infinite. For this reason, the string cannot exist beyond its consideration as a line segment which is still problematic for reasons I point out below, its overall length a value arbitrarily assigned but finite. So, in the case of the real numbers, the infinite line of unit members would be contained within two designated units with infinite points between and could extend beyond that. The string of numbers does NOT extend outward but rather within itself. This is comparing apples to oranges. - There could be no list of real numbers for the designation of the very first in the list would never be completed or would just be impossible for it would have infinite digits. None of the real numbers could be designated and thus, nor could the list. This is not unlike the problems that arise with line segments in which it is claimed that they are composed of infinite points, yet they cannot be because if of finite length, each end would have to be designated by a point beyond which there was no other which by definition would mean that those points would have to have scope and dimension which would mean that there could not be infinite points composing the line segment. However, if these end points had scope and dimension, what would that be? If 10x, why not 5x then why not 1x, ad infinitum. Thus, the line segment could NOT be composed of infinite points but at the same time would have to be, demonstrating that infinity cannot be paired with material concepts due to such inevitable contradictions. • What then would be the measure by which the string of real numbers was determined to be larger than that of natural numbers? Here we see that the string of natural numbers was being considered by Cantor as such per its unending length, that length forced by the denial of consideration of the span between specified unit members, e.g., 1 to 2 to 3, etc. However the string of real numbers could not be judged in its size in comparison to the string of natural numbers because it would have infinite members within the span of the first two unit members specified. What this means is that both must be considered in terms of unit members only and not by the abstractions of their lengths, as if each at any specified length would have different quantities of unit members. Instead, the string of natural numbers could not be considered in terms of the span between two designated members and the string of real numbers must be considered in and only in that manner. Since length of the string then is not a consideration, we are left to consider only and compare the number of unit members in which case they are equal, their “quantity” being infinite. I would say this is a bad analogy to make a mathematical point. This proposition of Cantor’s seems to be very sloppy in its disregard for the true nature of these concepts of infinity he employs.
Can't you do the same "Cantor Diagonlization" with the integer numbers too? Just make every number start with an infinite trail of 0s. E.i: ...0000001, ...000000002. And then do the Diagonalization technique to this set to get a new number?
If you do that, you will get something like ...111111111112. And it's true that ...111111111112 is not on the list of natural numbers! But ...111111111112 is not, itself, a natural number. Each individual natural number has finitely many nonzero digits. (This does not mean there is a global cap to how many digits a natural number can have; natural numbers can get arbitrarily long, but they can't get _infinitely_ long.) So although we have found something which isn't on the list, it also _shouldn't_ be on the list, so we can't conclude the list is incomplete. When it comes to real numbers, however, you _can_ have infinitely many digits extending to the right of the decimal point. So the newly constructed diagonal number _is actually a legitimate real number._ So we have found something which _should_ be on the list, but isn't. That's why we can conclude the list is incomplete.
Still I can not understand this argument. Maybe because I consider that we have already listed all the real numbers from 0 to 1, so the diagonal "procedure" creates a number which already has been mapped to an integer.
The argument shows that it is impossible to list all the real numbers. The diagonal argument guarantees that the new number is not in the list. The diagonal number can't be the nth number in the list because it's nth digit is different to the nth digit of the nth number that is in the list. That is true for every natural number.
There are a few different constructions of the real numbers, and each of them defines what it means in that construction to add and multiply. But this video presupposes all of that.
@@DrTrefor Cuts as defined by Rudin are real numbers (addition, multiplication, etc) and decimals are cuts. But this defines any cut, and decimals in particular, up to a countable number of digits because a cut at most exhausts the rational numbers, which are countable. And then addition and multiplication of any two reals can be defined by induction. Also, since any real number on your list contains a countable number of digits, and thus is a natural number for any number of digits, the list is countable. Thanks for taking the time to answer my comment.
@@DrTrefor One might say that the real number is the lub of the digital sequence, ie, distinct from the sequence. In that case, if you added lub to each countably infinite sequence of digits, you would at most double the number of real numbers in your list, which would still make the reals countably infinite.
@@wernerhartl2069 You are weasel wording. The number of digits is countably INFINITE, not countably FINITE as you are trying to trick people into believing. The number of digits is NOT a natural number. It is the smallest infinite cardinal (aleph-0). You also know that is the case, so your weasel wording is actually deliberate deceit. Your initial question has nothing to do with the topic of the video. Most of what you said in your last conet is wrong too. I strongly suspect that you know that you embellished something that you read. You are definitely conflating numbers with numerals. In mitigation, in this case it might be your stupidity rather than your dishonesty that led to it.
If you add 1 to the first digit, Why can't it (the number 2 ) exist lower on the lis as a first digitt? There can and must exist a many numbers lower in the list that is also 2 as the first digit. And sane for the second digit being 4. The explanation seems to not make sense.
The proof ensures that the number created differs from every other number by at least one decimal place. It is a fool proof way to create a number not on the list.
Because that wouldn't guarantee that the resulting number is different from all numbers in the sequence. Take for example the sequence 0, 0.1, 0.11, 0.111, ... . If we take a real number which for n-th position after the decimal points takes the n-th digit of the n-th number in the sequence, we get the number 0.000...=0, which is in the sequence (at the first position). The point of the diagonal proof is to generate a number which differs from every number in the sequence; and it does so by taking the n-th digit of the n-th number and changing it, so that the n-th number differs from the diagonal number precisely at the n-th decimal position. (Observe that the number 0.111...=1/9 doesn't appear in the above sequence, at any position n for n being a natural number.)
The problem that I have with the diagonal create new numbers method and the claim that "we can always construct a NEW number that is different from on the list....." is that, how is this any different from integers for example....u can physically list out all the integers you want...... and no matter what, there will always be infinite others not on the list....... you can list-out a chart with 1 to a googol and that still represents exactly 0% of infinite integers ..... so how would this be any different the perceivable "infinity inside infinity" ideas.... I understand for example there is infinite numbers between 0 to 1, 1 to 2 etc etc...... but how is this additional breakdown/dissection any different from infinite integers.... They both go on forever.... its simply "that which has no end no matter how u look at it
I completely agree with you! However, I spoke to a set theorist and he said that you can't have an infinite sequence of digits that is a natural number and I believe that's the main difference. What makes Cantor's argument is that decimals seem to go on forever. I don't actually think they do go on forever but that's what most mathematicians think. Even a decimal like .1 supposedly goes on forever because it can be written as such .10000... with an infinite amount of zeros after the 1. Cantor's argument wouldn't work on natural numbers because the list apparently wouldn't be horizontally infinite. So, for example, you couldn't have the natural number 100...000 where the digits go on forever. What this means is that you couldn't take a diagonal of every digit place. This all seems very counterintuitive to me and that's why I personally don't accept this argument. I think that regardless of what number you have you can always add more digits to it. These numbers don't actually exist. They are abstract concepts in our minds that are in some sense created only when we write them down.
@@michaelsayad5085 The set theorist is correct. So what. It has nothing to do with the topic in the video. BTW you asked the wrong question. You should have asked him if infinite decimals are OK and he would have said "of course they are". It's infinitely large natural numbers that don't exist. The proof starts by assuming that we have a COMPLETE list of ALL of the reals. It then shows have to construct a new number that is not on the list and this proves that the original assumption was wrong. There is no possible infinite list of infinite decimals that you cannot construct a new number from. What beats me is how so many people don't get this extremely simple logic.
@@michaelsayad5085 "These numbers don't actually exist. They are abstract concepts in our minds ..." That's right. They only have a pure abstract existence. They are not part of physical reality. "...that are in some sense created only when we write them down." Are you suggesting that the number 42 didn't exist until someone wrote e.g. XXXXII? How would that make it come into existence?
Isn’t the procedure for determining the digits of the diagonal number of exactly the same form as that for determining the digits of a computable number?
A computable number is one where, for any integer n, there exists an algorithm for computing the nth digit of the number. Note that “algorithm” necessarily means the computation must terminate in a finite number of steps. Do you think the Cantor diagonal construction fits this definition?
@@lawrencedoliveiro9104 So how do you propose to write a finite program that includes infinitely many infinite length decimals that are in no particular order. Whatever, this has absolutely nothing to do with the topic of the video.
Suppose you rearranged your infinite list. You would then get a different diagonal number not on your list. If you did this an infinite number of times you would come up with an infinite number of diagonal numbers, all different, not on the list.
Indeed! Although what is more interesting is whether you have created a countable number of new numbers this way or an uncountable number, what do you think?
@@DrTrefor Thanks for the reply. Of course I deny that the diagonal number exists in the first place (last element argument) but for the sake of argument the only way to answer your question would be to check whether each diagonal number exists in any of the other lists, which is impossible. You should check out th-cam.com/video/K9gRZO96YRc/w-d-xo.html And the replies to the comment that begins with .33333 Actually, in principle you could do the following: At the nth step in the creation of the diagonal number you could check whether your n diagonal elements are on any other list. There is no way to prove that eventually it would or wouldn’t be. The replies to my two comments in th-cam.com/video/XlKeEzYwtxw/w-d-xo.html are also interesting.
@@wernerhartl2069 Of course the diagonal numbers exist. Maybe you are a finitist, in which case the whole thing is a non-starter for you because, for you, infinite decimals don't exist and infinite lists don't exist. What is the last element argument? No entry in the list has a last digit and the list doesn't have a last element. Each constructed number could be inserted into the list. It would only be the last item chronologically. It could be the first element, but not the last because there is no such thing. The new list would be a different list. At no step would the list become larger (i.e. the cardinality of the set it corresponds to would always be aleph-0). For the current list, you construct a new number in such a way that it is guaranteed to not be in the list. Including it into the list makes a new list. You are now back to square one. Because the next constructed number cannot be in the list, it cannot have been in the previous list. It won't have spontaneously spawned. There is no magic going on.
No he hasn't. He constructed a number that isn't in the list at all. It can't be the last number (by position) because there is no end. It could be included in the list. It would only be the last one chronologically. I watched this video because you had told me that Prof. Bazett (as he now is) said that 0.999 .. . < 1 in it. He did not say any such thing. I think he must have misunderstood you when he gave you some love. He didn't realise that you were a crackpot that thinks that Cantor was wrong.
@@Chris-5318 Chris, this is a really aggressive, unhelpful comment that repeatedly mobilizes the language of authority and status instead of explaining clearly how Werner might understand it better, which may indeed be why Prof Bazett has “liked” the comment above and not yours. Tip from a math educator, calling people crazy is not a good way to teach.
Like, come on man. This isn’t politics. It’s math. When you see someone express some doubt about a complicated idea, you should not feel whatever rage you seem to be feeling. Try thinking of it as an opportunity to teach instead :)
@@griffinbur1118 Werner and I have some history. If he was mathematically competent, I'd call him a crank. But he isn't - he is a dishonest idi0t that intentionally spreads misinformation. Several mathematicians, including professors have tried to explain things to him (as have I). He just makes up math and tries to fob it off as if it was standard math. He "quotes" sources, but actually lies about what they say.
@SubZee An infinite list can be complete. The list of the natural numbers is 1, 2, 3, . . . is complete even though it is infinite. Identify at least one natural number that is missing from the list. Similarly, you can have a list of all the rationals. What the argument proves is that you can never complete a list of the real numbers - they are unlistable. What you can't do is actually write every term of an infinite list - I suspect that is where you are getting confused. There is no such thing as an incomplete real number. The idea is nonsensical. What is the first decimal place that you think has been missed when constructing the new number?
Well you can use the cantor-schroder-bernstein theorem and find an injection from rationals to naturals(the snake but skip the repeated elements) and an injection from naturals to rationals rationals(obvious) and then the CSB theorem tells you that there must be a bijection between the two! There are cleaner arguments for this, but this can work and if you havent yet seen the theorem look it up and try to learn and understand the proof
LOL you are getting desperate you crumbly old git. Let's play the game of infinite descent with the deinitions of words. First you had better define "Before", "listing", "the" "reals", "you", ...
Here you go: A set is infinite, if its number of elements is not equal to any natural number. (It's not an empty set, it doesn't have exactly one element, it doesn't have exactly two elements, it doesn't have exactly three elements, and so on. Of course, the "and so on" part is a bit involved; you can't have a formula of an infinite length.)
If you believe that the sequence contains its diagonal number, then at which position is it? No matter what index n you choose, I can say: no, that's not it: the n-th number in the sequence differs from the diagonal number in precisely the n-th digit, and the two numbers can't be the same. Sure, you can add the diagonal number to the sequence. You can't add it to the end, because there is no end; but you can add it to the beginning (or, if you want to, to the millionth position), shifting all numbers after it one position forward. But that yields a different sequence, for which the diagonal proof still applies - it has its own diagonal number different from the first, which the sequence doesn't contain.
Here's your construction, Cantor's Zeno paradoxes be damned: 0.0,...,9.9,00.00,...,99.99,...,oo Done. If you want finite expressions for irrational numbers, go for it. It's the same set, assume "..." At the end of each number. Then interleave with the original set. This is superfluous though.
@@GaryLuKOTH perhaps you have seen the Infinite Hotel video? If for some reason a number comes off the bus calling itself pi, you keep advancing it up the room number as that passenger reveals digits to you, ad infinitum. If it really bothers you, give rooms 1 and 2 to pi and e and be done with it.
@@jok2000 You're acting like pi and e are the only transcendental numbers that are not included in your set when in reality, all of them are not included (In fact, can you give me a single irrational number that is encoded in your construction?). There are uncountably many transcendentals, so you do not have enough rooms for all of them.
@@GaryLuKOTH you don't seem to recognize the construction is infinite, that's what the ... Is for. So I'm going to stop going around in circles right about here then.
I need help understanding this proof. Doesn't it implicitly assume there is a finite amount of numbers between 0 and 1? Obviously, the diagonal method would work given a finite amount of numbers and you'd be left with a new one. But given an infinite amount of digits, you can't say for certain that if you repeated this process infinitely many times, that you'd get a different number; that goes against the whole concept of infinity, doesn't it? You're basically assuming your infinite amount of numbers doesn't contain a certain number...
No, it doesn't assume anything like that. Obviously, there are infinitely many real numbers in an interval from 0 to 1. The proof essentially goes as follows: let a be any arbitrary function from natural numbers to real numbers (=infinite sequence). Then there exists a real number which is different from a(n) for all natural numbers n (from any number in the sequence). Therefore, no function from natural numbers to real numbers covers all reals. Sure, you can add the diagonal number to the sequence. You can't add it to the end, because there is no end, but you can add it to the beginning (or, if you want, to the millionth position), shifting all numbers after it one position forward. But that will yield a new sequence (function from natural numbers to real numbers) which has its own diagonal number. You can even perform the operation infinitely many times (by interspersing the two sequences); but you'll still get nothing else than an infinite sequence, to which the theorem still applies. In addition, by a slight extension of the proof it can be shown that for any infinite sequence of real numbers there are uncountably many real numbers which all differ from every number in the sequence.
If you believe that the diagonal number appears in the sequence, then at what position is it? No matter what position n you choose, I can say: no, that's not it; that number differs from the diagonal number by precisely the n-th digit after the decimal point, and the two numbers can't be the same. Sure, you can add the diagonal number to the sequence. You can't add it to the end, because there is no end; but you can add it to the beginning (or, if you want to, to the millionth position), shifting all numbers after it one position forward. But that yields a different sequence, for which the diagonal proof still applies - it has its own diagonal number different from the first, which the sequence doesn't contain. In addition, by a slight extension of the proof, it can be shown that there are uncountably many real numbers which the sequence doesn't contain - the set of uncovered real numbers can be mapped one-to-one with real numbers as a whole.
How are you changing every digit of the diagonal when there are an infinite amount of them? It seems to me that at every point you change a digit of the diagonal that segment can exist as part of some real number in the infinite list. It's only when you change all of them, which seems to be an impossible task since there's no point at which all of them are changed. It's like adding all of the digits of the natural numbers. We get 1, 3, 6, 10, 15... but there's no point at which you've added them all since it's impossible to add an infinite amount of numbers. Likewise, we can change ten digits, a hundred digits, or a billion digits of the diagonal but unless they are all changed it seems to me that a new real number is never formed.
This is exactly what I was thinking, I have no clue surely an infinite number of real numbers means we would eventually come across the diagonal number
What beats me is that you seem to have accepted that infinite decimals are OK. Why aren't you saying they are not possible because you can't finish the infinite task (of "adding" all the digits or whatever)? (Fortunately, there is no task).
@@Chris_5318 I never accepted that they are okay. With you in the other conversation, I accepted that rational numbers and prime numbers can be set up in a bijection with the natural numbers. I still don't think 1 = .99999... but I was working off your premise that it does and trying to see the consistency of your view. I still don't think real numbers have an infinite number of digits. However, I see your point. In this comment, I tried to simplify my view. I don't only think the diagonal is impossible, I also think the infinite expansion of the real numbers is impossible. You are correct!
@@michaelsayad5085 Sorry, I had replaced my comment before seeing you had responded. The "new" decimal just satisfies a rule. The nth digit is not the same as the nth digit of the nth entry in the list. For e.g. Pi all the digits of the decimal representation exist even if you haven't computed any, yet alone all, of them. Similarly, the natural numbers are a complete infinite set: {1, 2, 3, . . . } There is no process generating them. There aren't going to be more tomorrow than there are today.
Since we may define an infinite number as something being not a finite number, like we define irrational numbers as numbers that are not rational, it follows that all infninite numbers are the same: infinite, with the same size: bigger than the real numbers. Then we can extend the real numbers with these infinities (let's make a negative infinity as well) to get the extended reals!
@@Chris_5318 I can give you for every list of non-repeating real numbers a list of integers counting through them. Therefore, I claim, the sets of real numbers and integers have the same cardinality. Disprove it!
@@Chris_5318It maybe only proves that Cantor's method of assigning an integer to every real number does not work. Give me real numbers in any order and I will count them. Doesn't that prove that there are equal numbers of real numbers and integers?
@@Lauschangreifer Cantor proved that you cannot assign an integer (actually a natural number) to every real number. He didn't prove the opposite. You cannot list all the real numbers, regardless of the order that you try. You cannot even think up a *valid* scheme to attempt such a thing. Like many of the people that have commented here, you simply haven't understood the video.
I can't wrap my head around this, could it not be that it's simply sitting in a higher dimension? Just like comparing a line and a plane is unfair, because a plane is an infinite set of lines but you can line it up with x and y(both integer lines) and you get a plane of rationals. When using the reals you would need a third z line so when you add the 1 during diagonalization, you are moving up in the z line, the third dimension, which will be an infinite set of 2d planes. Is it fair to compare the area of a plane with the volume of a cube?
I don't know what you mean by 'unfair', but in both cases we're just considering sets with objects in them. There's no 'higher dimension'. However, (filling in your idea somewhat) you can for example view the set of rationals as a 2D version of the natural numbers N, since each fraction p/q is basically a pair (p,q) of natural numbers (disregarding the fact that some fractions are the same). Another dimension wouldn't add anything, since if you consider the set of all triples (p,q,r) with p, q and r natural numbers, then you wouldn't end up with a larger set
The cardinality of the set of points in a line is the same as the cardinality of set of points in every n-dimensional space (where n is a natural number). Cantor proved that too.
Am i just being stupid here? lets repeat the same argument for "is integers (0, inf) the same size as integers (0, inf)" by lining them up and doing the diagonal?
There are infinitely many natural numbers; but every natural number is finite in magnitude (and that's by definition: a set is finite, if its number of elements is equal to some natural number). So the decimal expansion of any natural number has finitely many digits. If you apply the decimal procedure to a sequence of all natural numbers, you get a sequence with infinitely many non-zero digits, which doesn't represent any natural number.
if the list is infinite then ofcourse it has all decimal numbers between 0 and 1 so why would adding a diagonal one add a new number, if every number already is there
@@jusu8961 LOL it proves that there are more real numbers than natural numbers and so it is impossible to list all the reals. In turn, that's because each line in a list corresponds to a natural number.
the only problem is if you were to actually create the list and rearrange the list after creating the diagonal , the problem magically disapoears. or if you rearrage the list you get a different diagonal snd a different number that fails...to say the nimber is not in the list is partially true
You have it backwards. Because both sequences contain the same elements, it follows that neither sequence contains either the first or the second diagonal number.
@@MikeRosoftJH there is no such thing as different number of infinite numbers in two sets of infinite numbers. since infinite is un countable. The natural numbers also can be diagnolized and the inverse diagonal line cannot be found in the list...but it doesnt matter. This is simply a faulty construction.
@@farmerjohn6526 No, there indeed are different sets of natural numbers: natural numbers can't be mapped one-to-one with real numbers, and no set can be mapped one-to-one with the set of all its subsets. Conversely, it's your construction which is faulty: diagonal proof cannot be applied to a sequence of natural numbers. There are infinitely many natural numbers; but every natural number is finite in magnitude. And that's by definition: a set is finite if its number of elements (or cardinality) is equal to some natural number - it is an empty set, or it has exactly one element, or it has exactly two elements, or it has three, four, and so on. (Of course, the "and so on" part is a bit involved; you can't have a formula of an infinite length.) So every natural number has finitely many digits. If you apply the diagonal procedure to the sequence of all natural numbers, you get a sequence with infinitely many non-zero digits, which doesn't represent any natural number.
@@MikeRosoftJH infinity is not countable. While it might seem one set is bigger, that is an illusion. Think of negative number vs positive numbers ...so if you combine the set it seems the combined set is bigger. But that is wrong. An infinite number of things has no size. Two Infinite sets also have no size. Its not like you have 2xinfinity... or Infinite plus Infinite.. an infinite number of integers can map to an infinite number of reals... The diagonal problem is complicated. For example if ypu assume the set of numbers is complete, then the inverse diagonal must exist..but it can't exist....the contradiction is confusing. Basically it implies you cannot create a complete set of real numbers....which suggests to me something else is wrong..
@@farmerjohn6526 A set is countably infinite, if it can be mapped one-to-one with natural numbers; in other words, if there exists an infinite sequence of elements of that set, such that every element appears at some finite position. (An infinite sequence is no more and no less than a function whose domain are natural numbers.) So integers are countably infinity, because they can be enumerated by the following sequence: 0, -1, 1, -2, 2, -3, 3, ... - any integer n appears at a position no greater than 2*|n|+1. It certainly is possible to define size (cardinality) of infinite sets. Set A has the same cardinality as set B, if sets A and B can be mapped one-to-one. Set A has no greater cardinality as set B, if A can be mapped one-to-one with a subset of B. (It can be shown that if set A can be injected into set B, and B can be injected into set A, then there exists a one-to-one mapping between the two sets; so the two definitions agree with each other.) And this is precisely the same definition as in case of finite sets: imagine that you are in a cinema, and see that all seats are occupied - nobody is standing, nobody is sitting on two seats, no seat is empty, and no seat has two people in it. Then - without needing to count them - you can tell that there's the same number of seats as people. Conversely, the result that natural numbers can't be mapped one-to-one with real numbers means the same (just for different sets) as that you can't put ten guests in nine rooms, such that no two guests share a room. Just because cardinality of infinite sets doesn't work the same as finite sets, that doesn't make cardinality of infinite sets somehow ill-defined. (For example, it can be the case that an infinite set can be mapped one-to-one with its strict superset or subset; here's a one-to-one function between natural numbers and a strict subset thereof: n -> 2*n.) It's perfectly well-defined: for any two sets it either is, or isn't the case that set A can be injected into set B (i.e. mapped one-to-one with a subset of the other set). (But that every two sets are comparable in this sense - that either A can be injected into B, or B can be injected into A, or both is the case in which case the two sets can be mapped one-to-one - is a consequence of the axiom of choice.) You are confused about the fact that you can't have a reverse diagonal in the infinite table of the diagonal proof. Sure, you can't; but that only says that natural numbers do not have a maximum under the usual order. (You sure can define a different order, for example one under which 0 is the minimum, 1 is the maximum, 0..., and any even number is less than any odd number. That's not a very useful order - in particular, it isn't consistent with the usual mathematical operations + and * on natural numbers - but it's a perfectly well-defined ordering relation.) Besides, the infinite table and its diagonal is just a visualization of the proof; it's not the proof itself. Let me present a proof of the related theorem that no set can be mapped one-to-one (or onto) the set of all its subsets: * Let A be any set. P(A) is the set of all subsets of A. (That this set exists is a consequence of the axiom of powerset.) * Let f be any function from A to P(A). (That is: for any x∈A, f(x) is some subset of A.) * Let D={x: x∈A and x∉f(x)}. (For any x∈A, f(x) is a subset of A. There are exactly two possibilities: either x∈f(x), or x∉f(x). D is the set of all such elements, for which x∉f(x); that this set exists is a consequence of the axiom of separation.) * By construction, D is not equal to f(y) for any y∈A. Let y be any element of A; there are exactly two possibilities: ** 1) y∈f(y); then by construction of set D, y∉D. ** 2) y∉f(y); then by construction of set D, y∈D. ** In either case, f(y) differs from D by the inclusion of y. * Therefore, the function does not cover all elements of P(A) (all subsets of A); in particular, it does not cover the set D. * Therefore (because I have assumed nothing about the function f, or about the original set A), the same is true for every function from A to f(A), for any arbitrary set A. QED The proof that natural numbers can't be mapped one-to-one with real numbers is similar.
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.
@@shivpatel3311 It'd have an infinite number of positions with a decimal? Each number along your diagonal would be a 0 since it's after the decimal point, and thus your constructed number would have every position filled with a non-zero value. Unless you're instead going the other way, instead looking at the ones place, the tens place, the hundreds place, in which case the object you construct would not be an integer, and we can demonstrate this since it must be arbitrarily larger than any other integer if it were one, contradicting properties of the integers. For any integer x, there's a natural number n such that n > x, and since 10^n > n, 10^n > x. Since your sequence is a bijection, there must exists a point past the 10^n position where we encounter a 0 digit, since if we never did, then we'd have only n positions to list 2* 10^n + 1 numbers, an impossibility, thus our constructed object has a non-zero entry in the 10^n position and thus the constructed object, if it were an integer, is greater than x. Since x is arbitrary, this means if our constructed object were an integer, it is larger than all other integers. However, this means this constructed object is also larger than itself, and thus by the addition rules of the integers, we also have that 0 > 0, a contradiction. As well, you say you're mapping the real numbers onto the integers: I assume you mean the natural numbers onto the integers, since Cantor's Diagonalization explicitly is built on utilizing the countable infinity of the natural numbers. If you really mean the real numbers, then you haven't defined this 'diagonal' you're referring to.
@@DrTrefor Induction only works with a single countable infinity. Your list has two independent infinities. For example, I could have three sequences consisting of infinitely many digits. You have to relate the infinities.
No. You are still missing the point. You don't construct the diagonal number in steps (with the diagonal number of the whole sequence being the "infinity-th" step); you define it as a whole. And for your final argument - as I constantly tell you - you are making an invalid proof by "magical induction". It's the same nonsense as claiming: "The empty set is finite; the set {0} is finite; the set {0,1} is finite, the set {0,1,2} is finite, and so on - for any natural number n, if the set {0,1,...,n} is finite, then so is {0,1,...,n,n+1} - adding a single element to a finite set can't yield an infinite set. Therefore by induction, the set {0,1,...,n} is finite for every natural number n [this is correct]. Therefore by 'magical induction', the set of all natural numbers is finite [this is of course incorrect]." What you have really proven is that there are countably many numbers with a finite decimal expansion; and that's not a new result: all such numbers are rational. Let's do the diagonal proof once again: * Let a(n) be any function from natural numbers to real numbers (in other words, any infinite sequence of real numbers). * Let d(n) be the following sequence of digits: d(n) is the n-th digit after the decimal point of a(n) (the n-th number in the sequence). (For lack of ambiguity: if the number a(n) has two different decimal expansions, like 0.1000...=0.0999..., then use the expansion ending with infinitely many digits 0 rather than 9.) * Let d'(n)=d(n)+5 mod 10. (In other words, d'(n), for all natural numbers, is the n-th digit of n-th number of the sequence, increased by 5 and wrapped around zero if necessary.) * Let D be the real number whose decimal expansion is d'(n). (The integer part is 0.) * For any natural number n, a(n) has - by construction - a different decimal expansion than D, and the two numbers can't be equal. (It can also be shown that the two numbers differ from each other by at least 3*10^-n.) * Therefore, the sequence a(n) does not cover all real numbers; for no natural number n is a(n)=D. * Therefore - because I have made no assumptions about the sequence a(n) - the same is true for all sequences (all functions from natural numbers to real numbers). If you believe that the diagonal number could appear in the sequence, at which position is it? It can't be the first, because the two numbers differ from each other by the first digit after the decimal point. It can't be the second, because the two numbers differ from each other by the second digit after the decimal point. And so on; for any natural number n a(n) differs from n by the n-th digit, and the two numbers can't be the same.
The diagonal proof doesn't make sense. If you truly had an *infinite* list of real numbers then every number would already be on the list. There would be no space to make a new one so adding one or not wouldn't matter.
Why would an infinite list automatically be complete? For example if you look at the following subset of natural numbers {2, 3, 4, 5, ...}, it is obivously infinite, and you can list its elements (i.e. there's a bijection between it and the set of natural numbers). However, it is obviously not complete, because 1 is missing (and 0 depending on what definition of the natural numbers you prefer, but that is not the point)
@@paketbaand1523 Exactly. Any list consists of individual items. Thus lists are countable. Real numbers are measures. There is no method of counting them.
Yeah but you can't encompass all of the integers either. For every real number you can assign an integer. If you have a new real number just add 1 to the integer set. They're both infinite so you never run out.
The crux of the proof is that there is no final list (or function), because the assumption of its existence leads to the contradiction that it is in fact not complete.
You cannot assign an integer for every real number. There are too many real numbers That what the video proved. You need to watch the video again. Remember, the starting assumption is that you supposedly have a list of all the real numbers, not just some real numbers. Maybe try some Google searches.
The word countable actually means listable. In other words we can assign every element in the set a unique numeric identifier (typically done as a natural number). Thus for the set {a,b,c} we could give a 1, b 2 and c 3. Thus if I gave you a number say 3, you could tell that I am referring to c. Countable is a highly deceiving word and most likely why I see so many rejectors of the theory in the comments. Thus for a countably infinite set, there MUST EXIST a bijective function from the natural numbers to the set, but what cantor showed is that whilst we can create an injection, we can never make it a surjection and hence why the set is not countable (but remember this means listable). And this is because no matter how small or big the interval is we will always be missing a number from the set.
@@Chris_5318 Actually I don't think it proved anything. Even if you start with a list of all real numbers, you can still make a list of integers that are the same length, simply by counting them. And whenever you find a new real number that is not on the list, you add the next integer to the list of integers. Just as you can always find a new real number that is not on the list, you can always add 1 to the highest integer to get the next one, which also was not on the list.
@@grantofat6438 You haven't understood the proof at all. You cannot actually start with the list of all the real numbers. That is what was being proven. The list of all the integers can be made, and you will cannot find an integer that is not in that list. Such a list starts 0, 1, -1, 2, -2, 3, -3, .... You cannot write aby such list that in such a way that you can use the diagonal argument to find a missing integer.
i really dont get it. why cant we just pair it like that: 0 - 1 0.1 -2 0.01 - 3 0.0001 -4 and so on and it will continue till infinity and it will never reach 0.2 but why does it have to? we said if we can pair them than they have the same size.
@@NuNiia95 Your original comment has nothing whatsoever to do with the topic of the video. I cannot imagine why you think it might. You have simply given a sequence whose nth term is 1/10^n and whose limit is 0. I didn't try to explain anything to you because I had hoped that you might realise that what you had said has nothing to do with the topic. Silly me.
@@Chris_5318 if you thought with just writing "what are you on about" i would understand it then you are really silly. but after reading ur explanation and watching these 2 videos again i understood it.
Just put 0.0-0.9 in 10 dimensions. Each extra digit creates another 10 branching dimensions. Do this infinitely, then just draw a simple infinite dimensional spiral through all of them. Boom. Counted that shit.
Your procedure appears like nothing but handwaving. No matter what sequence you have come up with, it doesn't contain all real numbers - given any function from natural numbers to real numbers, there is some real number which the sequence does not cover. (By extension of the diagonal proof, there are uncountably many uncovered real numbers - the set of uncovered numbers can be mapped one-to-one with real numbers as a whole.)
I don't fully understand. Okay, you can always find "another" real number, but then I can always find "another" natural number to pair up with that real number. Like I have 0,001? Ok, I will take "1" from N. I have 0,0001? Ok, I take "2" from N. Like I can always find some brand new N number to pair up with some number from R.
PinkySuavo think about this way, assume you right and you can pair the real number Y from the diagonal with a natural number X, then you would have the pair (X,Y) written down in the table. However, This method proves that your number cannot be found in the table at all, therefore the assumption must be wrong.
You can find a brand new natural number, but as the diagonal line goes on and on, the "new number" that is made won't ever be in the list. Your new natural number also has to be paired with a real number, and that real number will have at least a single digit not matching with the new number, since 1 was added to one of the digits of the real number(which is paired with your brand new natural number).
Not sure I really understand, but here's how I think about it. Lets take 4 numbers (pretend these are in rows like the video): [1,2,3,4], [2,3,4,5], [3,4,5,6] and I make the 4th the same as the diagonal (to be sneaky) [1,3,5,6]. The last number is the same as the diagonal of the four numbers. OK, but now I have to add 1 to each diagonal digit to make a new number. This number, [2,4,6,7], isn't in the set, but - no problems - I just make it the 5th number. But, the problem is this 5th number isn't part of the diagonal. So, I need to add an extra digit to each number so my diagonal includes all 5 numbers. OK, I do that - eg. [1,2,3,4,0], [2,3,4,5,0], [3,4,5,6,0], [1,3,5,6,0] and [2,4,6,7,0]. But, now, my fifth number no long matches the +1 diagonal (which should be 2,4,6,7,1). It doesn't matter what you make that last digit of the 5th number - it never matches the +1 diagonal rule. You can keep adding numbers, but then you always need to add an extra column, which then makes your extra number not match the diagonal +1 rule. However, I don't really understand how this shows there are more of these than integers - just seems to indicate that because columns must equal rows, an infinite number of columns are needed, and so an infinite number of integers to match. So, maybe I haven't understood it correctly..
@@austenganley8220 You need to pick the function from natural numbers to real numbers as a whole. * Let a(n) be any function from natural numbers to real numbers (in other words, any infinite sequence of real numbers). * Let d(n) be, for all natural numbers, the n-th decimal digit of a(n). (If a(n) is a number with two different decimal expansion, like 0.1000...=0.0999..., use the expansion ending with infinitely many digits 0 rather than digits 9.) * Let d'(n)=d(n)+5 mod 10. (That is: d'(n) is the n-th digit of a(n), increased by 5 and wrapped around zero if necessary.) * Let D be the real number whose decimal expansion is d'(n). * It can be seen that given any natural number n, D is a different number from a(n): n-th digit of D and of a(n) are different (and it can't be the case that d'(n) is an alternate decimal expansion of that number, either). It can also be seen that the two numbers differ from each other - no matter what the remaining digits are - by at least 3*10^-n. * Therefore, D is not equal to a(n) for any natural number n; in other words, the function a(n) does not cover all real numbers (in particular, it doesn't cover the number D). * Because I have made no assumption about the function a, the same holds for all functions from natural numbers to real numbers - given any function from natural numbers to real numbers, there is some real number which the function does not cover. QED.
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.
dd
Cantor's stuff is wrong
my brain.... I thought hearing this in English would make it easier...
Nah it's pretty easy to understand
@@Sir_Isaac_Newton_ What a helpful comment Sir Newton! Surely this fixed the other person's problem!
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.
I've read this proof a number of times and now it makes sense. Thank you.
Question: How is creating a new diagonalization different than adding another integer to the end of the countables?
Well, how do you know adding an in tiger to the end isn’t already on the list somewhere? The number I constructed is probably not on the list.
@@DrTrefor thanks for the reply. Why wouldn't it be adequate to say that the set of all integers is a portion of the continuum and therefore must be smaller? I guess the same could be said for the set of all squares relative to the set of integers, and they are considered to be the same size. Oh, I see now, the difference is you cannot continually create new squares between the squares, but the continuum will always create a new number between the last two. Is that right?
exactly. why are we allowed to "create"a number by diagonalization but not allowed to "summon" another integer?
frankly i am in awe that this is taken as an important part of mathematics, this is as mathematically rigorous as taking a rabbit out of a magical hat.
at first i felt stupid for not "getting" it but it really is just a stupid argument that we are forced to accept in order to be not being marked as "mathematic illiterate".
@@jgmartinezmd6867 I agree with you completely. For one, the list of real numbers between 1 and 0 is infinite, so you wouldn't actually be able to finish creating a number using a diagonal.
@@jgmartinezmd6867 Because every integer is finite and therefore has finitely many digits. If you try to apply the diagonal procedure to a sequence of integers, you'll get a sequence with infinitely many non-zero digits, and this doesn't represent any natural number. (Likewise, if you apply the diagonal procedure to a sequence containing all rational numbers - and such a sequence exists - then the resulting number must be irrational.)
And it's not enough that natural numbers (or rational numbers) are a subset of real numbers. Both natural numbers and real numbers have a property that the set can be mapped one-to-one with its strict superset or subset. (Infinite sets - to be precise, any set with a countably infinite subset - in general have this property.) Likewise, it's not enough that the set is dense (such that for any two different elements x and y there exists another strictly between them). Rationals have the same property, but are countably infinite. (A set being dense is a property of an order on that set, not of the set per se.)
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!
Glad it helped!
Easiest no bs explanation of the concept I have ever seen. Superb Trevor. Love you man
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.
Well spotted.
dude. You just saved my math test. Respect and subbing
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.
Great explanation! My textbook was way too wordy, just making the concept confusing ... you were brilliant!
Here's a simple algorithm to count every number from 0 to 1 without missing a single one (in base 10): Count from 0 to infinity the same way you're counting natural numbers, but keep the decimal period in front.
.0
.1
.2
...
.10
.11
.12
...
.787435
.787436
...
If there's 1 digit after the period, it will appear in the first 10^1 entries. If there's 2 digits after the period, it will appear in the first 10^2 entries, if there are K digits after the period, it will appear in the first 10^K entries. There's no number K big enough that this list wont cover, and by contruction of the list, you don't miss a single number.
It must be pointed out that by contruction, this dosen't miss a single number, no matter with one you change in the diagonal argument. If you changed up to K digits, your new number will be already on the list, before the 10^Kth entry. There's no K that won't be covered, and by induction this applies to infinity.
Honestly I'm shocked this is even remotely an acceptable proof....
I mean it's simple to debunk the method.
Take a 3x3 matrix.
187
256
921
I promise if you were to say 151 is not on the list of all possible 3 digit sequences you would be laughed at by the mathematical community in a very big way.
The reals are absolutely the same size as the integers. Even pi has a corespondent integer, you just don't know which value corresponds until you stop computing. All this means is numbers like pi have variable correspondence determined by arbitrary degrees of precision.
@@Adventures_of_MarshmallowI think you missed the whole point of the demonstration that works only when talking about infinity.
The idea is that you are creating a new number that by definition is different from every other number on the list. You do so by making sure that at least 1 of its figures is different from an already existing number. This is why you change the figures diagonally, because you want to hit all the possible numbers already associated with a natural number and make a small change.
What you created is a new number that by definition is different from every possible number already associated with a natural number. Because of that it can’t be on the list, even if it is infinite.
Bro you are missing even basic numbers like 0.01
Yeah the "proof" is faulty.
You can't find a new real number to add to the list of all real numbers no matter what you do, it's already on the list.
People just don't think about that part and confusing themselves
@@prophetrob It's called a proof by contradiction. We have found a real number which is both on the list (by assumption) and provably not on the list (by construction). This implies that our original assumption is wrong (that all real numbers can be placed on a list).
But, it also doesn't have to be a proof by contradiction. One could simply state that no function from the natural numbers to the interval (0,1) is surjective/onto. Then, you can start with an arbitrary list of real numbers and use the diagonal argument to show that every list of real numbers is incomplete. We can construct a real number not on the list. It's the exact same argument, but without the assumption that the list is complete.
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?
Thinking about it a bit more ... you can't list the reals in order so it's impossible to have a one to one correspondence with integers?
If you took the exact same argumnt for the rationals, it wouldn't work because the new number you constructed, different along the diagonal, has no guarantee of being rational again.
@@bash2357 But in the video he has
1)
2)
3)
.
.
()()
Each row (natural number) has a one to one relation to a real number??
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.
I am so curious about how this misconception became so widespread? Do you have any idea why _so many_ mathematicians confuse the aleph and beth numbers?
@@MuffinsAPlenty I wasn't aware they did.
Perhaps, they forget about the continuum hypothesis and as 2^aleph0 is the next infinity we all know about, it gets called aleph1.
I can literally feel my brain melting
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)?
If you believe that the diagonal number could be in the sequence, at which position is it? It can't be the first, because it differs from the first number by the first digit after the decimal point. It can't be the second, because it differs from the second number by the second digit after the decimal point. And so on - for any natural number n does the n-th number differ from the diagonal number in the n-th digit, and the two numbers can't be the same.
@Alejo Sanchez Sure, but if you are careful in constructing he diagonal number, you can ensure that the numbers are not equal. For example, make the n-th digit after the decimal point equal to n-th digit of the n-th number in the sequence, increased by 5 and wrapping around zero if necessary.
@Alejo Sanchez This works, too. It also shows that there are uncountably many numbers which the sequence does not cover: for every position there are at least 7 different digits to choose from (for n-th digit you can't choose the digit that n-th number has at the same position, and you may want to avoid using the digits 0 and 9 - or, alternately, the digit one higher and one lower - in order to avoid getting into problems with numbers which have two different decimal expansions).
@@MikeRosoftJH I got it now: no matter on which line of which number we look, our decimal is 'constructed' in order to be different from that listed decimal, because we change it -so to speak- the very moment we individuate it.
@@MikeRosoftJH But I have a second question now: why does it have to be a diagonal? Can't this method work even if we construct our decimal vertically on the first column? Thank you for explaining.
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....
oo i not a number. By convention, 10^oo = oo simply means lim n->oo 10^n = lim n->oo n.
@@Chris_5318 That's my whole point.... Infinities as objects rather than processes make them 'numbers' which are not so very different than variables....
A limit is a process where an approximation of it's 'end' is taken.
@@Adventures_of_Marshmallow A limit is NOT a process. It is a number that satisfies a criteria. An infinite series (or product) does not have an end.
Here is the definition for a series:
Definition of [convergence to a] limit:
Let S_n be a sequence of real numbers and let S be a real number.
Then S = lim n->oo S_n means that for every real ε > 0 there is a natural N such that for every natural n > N that |S_n - S| < ε.
There is no process in that whatsoever.
@@Adventures_of_Marshmallow You, "Infinities as objects rather than processes make them 'numbers' which are not so very different than variables...."
You are completely wrong. No processes are involved and "infinity" is simply "that which has no end". "Infinity" is not a number, a process or a variable.
There are so-called infinite (or transfinite) numbers. They are constants, not variables. They are not relevant to the topic of 1^oo.
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.
Works beyond zero to one as well, however that isn't needed to show they are different types of infinity.
@Picky, you can show that there are as many reals in (0,1) as in (-oo,oo). Let x be in (0,1) then tan((x - 1/2)Pi) maps to (-oo, oo) and that is obviously bijective and so by definition the two sets have the same cardinality.
I'm seeing two comments in reply to your comment, neither of which address your comment. I don't know if this is a TH-cam glitch or what. But what you say is a very good and valid question, and I think I can address it:
The key to why the diagonalization argument is effective in showing that the reals aren't countable, is that the decimal expansions of reals are allowed to be infinitely long; the argument describes a method by which you can invent a real number _having a chosen infinitely-long decimal expansion_ which yet must be different from all the other numbers in any given countably-infinite list: That method being, you construct your number by doing the "digit change trick", digit by digit, _forever,_ to methodically avoid all numbers which could be in any conceivable countably-infinite list, forever. And this construction then corresponds to a totally valid real number. - _But for the argument to work, you must be able to keep doing this method forever - to keep avoiding the other numbers in the countably-infinite list forever_ - which you can do _only because your own invented number is allowed to be infinitely many "choosable digits" long._
However, if you are talking about integers or anything in a so-called "integer matrix", then their "choosability" has to end at some point; the decimal expansion of an integer _must_ terminate after some digit and henceforth become blank, or all zeros, or some repetition, or some non-repeating pattern, or whatever other invariable "terminating notation" you choose to use to write it with - It doesn't matter what the "termination" looks like, it only matters that you cannot continue freely varying its digits after that point. (If its variability does not "terminate" like that then it is not an integer or anything integer-like, but rather something endlessly variable very much like a real number!) - Bottom line, if it's an integer or anything integer-like, then you cannot continue to _choose_ its digits continually forever; after it arrives at that necessary point of termination then you have to stop freely choosing its digits. And so it follows that, past that point, you can no longer continue to construct it to be unique versus all the others in the list. Once its last "choosable" digit has been written - and every integer's last "choosable" digit has to be written at some point - after that point, you can no longer continue "diagonalizing" and avoiding all the other numbers on the list. For all you know, your "terminated number" now matches another number on the list. You cannot prove it doesn't. So, this type of proof doesn't hold for integers or anything integer-like.
@@AV_TH-cam_202X "But for the argument to work, you must be able to keep doing this method forever"
No. You only have to do it once. The list is supposed to have contained all the reals in (0,1). CDA then shows that there is a number in (0,1) that isn't in the list. Therefore you cannot have such a list. The end.
Thanks to you I realise that I had badly misread Picky's query. I can't see what Picky was thinking of doing. None of the integers has an infinitely long representation so CDA cannot be applied.
OTOH we can map the naturals bijectively to the integers.
e.g.
N Z
1 0
2 -1
3 1
4 -2
5 2
6 -3
7 3
...
Picky, the wannabe diagonal "integer" would have infinitely many digits and so would not be an integer. Of course that does mean that it isn't in the list. That doesn't contradict the assertion that the list contains all the integers.
What is the proof that the diagonal set is not on the list of the natural set?
The new number constructed differs from all the numbers in the set , by 1 position , which means the new number is different from all the numbers.
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
The new number is different from the first number on the list (because their first digits after the decimal point are different). It's different from the second number on the list (because the digits at the second position are different). It's different from the third number on the list because the third digits are different. This continues on for all natural numbers. So the new number isn't equal to any number on the list.
@@MartinPoulter Ahh that makes sense - thankyou!
@MartinPoulter But you're making the assumption that, repeated infinitely many times, it'd still hold up. This goes against the idea of infinity: if a set contains all the numbers between 0 and 1, then it must contain ALL the numbers between 0 and 1...
@@hashtags_YT yes exactly this. Diagonalization of an infinite set is a broken concept.
It's similarly broken if you diagonalize the set of all naturals
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?
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 ??!!
Because it’s different in one digit to every number by construction
Can you tell why the diagnol of rectenagle is equal with proof and base quantity
It's useful for the theory of computation.
came here after Veritasium's Math has Fatal Flaw to understand Cantor Diag. Still couldnt
CDA is very simple. Just watch again or find another source.
Well. That does get me thinking.
There might be a bijection between integers and reals, but is there an equal number of functions from the integers to the reals, compared to the reals to the integers?
Probably not.
This seems obvious to me because decimals can expand in both directions, you can count upwards such as .1, .2, .3, .4, .5 and so on and you can count backwards such as .1, .01, .001, .0001, where that is not possible with integers.
That doesn't prove anything. By doing that you'll only cover real numbers with a finite decimal expansion, and there are countably many such numbers - all such numbers are rational, and that there are countably many rational numbers was proven by Georg Cantor.
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?
It's just a faulty assumption. You can't find a real number that isn't already a member of the real numbers.
Trying to diagonalize an infinite is simply a broken concept. It's undefined
You get the same thing if you try to diagonalize all the natural numbers. A lot of people are bad at thinking things like this through.
By construction, it is different from every number in the list. For each positive integer n, the diagonal number differs from the nth number on the list because it is different in the nth decimal place.
@@MuffinsAPlenty the important thing to remember is that it's not a different number that wasn't already part of the reals so this process means nothing in terms of countability of the set. It's a red herring, the set in question isn't any bigger than it ever was.
@@prophetrob No one's saying that it wasn't part of the reals. The entire point is that it _is_ a real number which is _not on the list,_ showing the list is incomplete. But this same reasoning applies to any arbitrary list of real numbers, showing no list of real numbers is complete. This proves that the set of real numbers is uncountable.
"the set in question isn't any bigger than it ever was."
We're not comparing the size of R to the size of R. We're comparing the size of N to the size of R.
@@MuffinsAPlenty the list is incomplete because it's not trying to make a list of all the real numbers in the first place, it's just trying to come up with a number that isn't on the finite list and people are misled into thinking about the wrong process because they imagine they can take a limit of it when really the process can't be done at all
I like this guy's videos, but topics like this are why so many people dislike math.
On the other hand, topics like this are precisely why some people _love_ math.
ya know... the writing it in any order is what the issue is. write it in order and then when you start at 111111111.... by the time you get to a number starting with 3 and you went diagonal ending at the last number starting with 1 the numbers on the list. writing it down random makes the illusion its not on the list. however if you diagonally get into the 2s it will not appear "yet"
Very well explained sir.. Thanks a lot.
You are most welcome!
Really very awesome explanation........
You are the real MVP!
Thanks for the great tutorial!
Finally got it... I think. Thank you
4:11 why the new number is not on the list? Maybe the 0.2000... is somewhere on the list but just not being showed on the screen yet..
Because the argument uses the fact that the constructed number will be different in at least one digit. For the first decimal place, we choose a number that’s different than the one for the first number on the list, for the second decimal place we do the same and so on infinitely. For any nth number on the infinite list, we know it’s guaranteed to be different in the nth decimal place so it cannot be anywhere. So the new number’s 50th decimal would be different from the 50th on the list, same for the 100th and so on. So despite listing infinite numbers, we can still construct infinitely many more numbers not on the list through this
This only works when the list isn't made by reflecting counting integers in any base, across the decimal to get a bijection from natural integers to the unit interval (0,1). when this is done the diagonal is all 0's so the slash in binary is all 1's. This occurs in the limit of taking the last row of any block of 2^n numbers of n digits, then taking that limit to get .1111 repeating or for any base we get all strings of any digit across all n entries. We get .111... , .222... , .333... , .444 etc. repeating and more, we get any string of digits we like so long as it isn't matching that in the unaltered diagonal. By counting all natural numbers in this way we must be able to find all values in (0,1) from that similar fractional counting method that are missed by it. I have doubt any can be found as the method is also by combinatorics exhaustive and identical to that for exhaustive counting combinatorics applied to natural integers.
"This only works when the list isn't made by reflecting counting integers in any base, across the decimal to get a bijection from natural integers to the unit interval (0,1)."
Reflecting over the decimal place is not a bijection between integers/natural numbers and (0,1).
The main issue is that each natural number has only finitely many (nonzero) digits (to the left of the decimal point), whereas real numbers can have infinitely many digits (to the right of the decimal point).
So something like pi-3 has an infinite decimal expansion, and reflecting that over the decimal point does _not_ give an integer.
I think he means if you can map real numbers to natural numbers, then they are countable (rather than integers).
Both definitions are equivalent!
Question: how does this work for numbers that go past the square? The shape formed by all the numbers between 0 and 1 would be a non-regular rectangle as when you list numbers of a certain distance past the decimal point the amount of numbers follows the formula 10^d=n with d being the distance past the decimal point and n being the amount of numbers.
The "square" is infinitely wide and infinitely deep. 0 and 1 are single digit numerals.
@@Chris-5318 I’m aware of that, but there are more after the square as the square can’t contain all the numbers, even for whole numbers.
@@gabeclements2501 You cannot list more than aleph-0 items on each side. There is one row for each natural number and one digit column for each natural number.
@@Chris-5318 Infinity is not a size.
@@karenhartl2115 That's right and that's why I never said it was. OTOH aleph-0 is is a size. More formally it is the cardinality of the set of all the natural numbers.
How do we know that the new real number we generate isn't anywhere else on the list?
If the new real number R were on the list, then there is some natural number N such R is the N'th number on the list, but then because of how R is defined, the N'th digit of the N'th number on the list is not the same as R's N'th digit, and thus we would find that R's N'th digit is not the same as R's N'th digit, which is contradictory. Thus, R can not be on the list.
I really dont understand, can someone please explain?
Suppose that, to simplify things, we actually order the real numbers in such the following way:
Item # | Real number
123 | 0,321...
837 | 0,738...
623 | 0,326....
Then suppose we do the diagonal trick and come up with 0,447... According to Cantor this number isnt on the list.
Oh but wait, it is, it corresponds to item number 744!
Even with reals that are infinitely large in the amount of digits, we will always find an integer that also has an infinite number of digits.
How can we just accept that Cantors diagonal makes a new number that wasnt on the list before when, very clearly, it already was there, along with the integer that goes with it?
I disagree with their reasoning but mathematicians would say that only works for rational numbers, not for the irrational numbers with the digits that go on forever! They would say that there are no natural numbers of infinite length.
@jorge, you list is hopelss. Stick to the one in the video. No division stuff. You'll typically make many duplicates of the same number because you migh have 123/0.321... and 246/0.642... In fact you are unknowingly making a straw man argument by changing the details of what was actually said to something that was not said. The original argument is also very simple.
@@Chris_5318 Those wernt divisions. I modified the message to express myself better.
@@JJP-lb3ek Ooops, I had a brain fart and so hadn't noticed what you had done, my bad. However, that leaves you with several problems. Firstly, your list only contains finite length decimals. It contains no irrationals at all and it doesn't even contain 1/3 = 0.333...
Aside: Your notation is appalling. I hope you meant
123 | 0.321000...
837 | 0.738000...
723 | 0.327000...
Secondly, your list will actually be
1 | 0.1000...
2 | 0.2000...
3 | 0.3000...
...
9 | 0.9000...
10 | 0.01000...
11 | 0.11000...
12 | 0.21000...
...
19 | 0.91000...
20 | 0.02000...
...
*NB except for the first number, the nth digit of the nth number is a 0*
It will never get you an infinite decimal (i.e. one that doesn't finish with 000...) because no natural number is infinitely large. I'll ignore that for now. I'll use the replacement rules that 1,2,3,4,5,6,7 are replaced with 8 and 8,9,0 are replaced with 1. Now I apply CDA using that and I generate 0.8111... (aside: that's an infinite decimal that cannot map to ...1118 because there is no such natural number). If there was such a number, then the digit at position ...1118 of that number would be a 0 and not the 1 that you require it to be. That contradiction that it should be a 0 and a 1 is entirely down to playing fast and loose with infinity (albeit unwittingly). So your scheme failed (miserably) as would have been obvious if you only realised that CDA doesn't give a tinkers cuss about how you generated the list.
It's important to note that for example 0.899999999... and 0.90000000000... are actually the same value, which this method doesn't take into account.
My favorite way of diagonalization is: increase the digit by 5, wrapping around by zero if necessary (d'=d+5 mod 10). That guarantees not just that the diagonal number differs from n-th number in the sequence (for all natural numbers), but also by how much (by at least 3*10^-n).
THIS! is a great proof!Answer:
There exist no number between aleph-0 and aleph-1.
I see that you subscribe to the continuum hypothesis. Sure, of course there's no cardinality between aleph-0 and aleph-1; that's by definition - aleph-1 is the next well-ordered cardinality after aleph-0 (the smallest uncountable well-ordered cardinality). But set theory without additional axioms can't determine if the cardinality of the continuum is aleph-1, aleph-2, or something else. Worse: in absence of axiom of choice, it's consistent that real numbers can't be well-ordered, in which case cardinality of the continuum is not an aleph number at all.
@@MikeRosoftJH The cardinality of the floats and integers is identical. However, there are an infinite number of boneheaded (yes, I have a better word but let's keep it civil ) match-ups which will drive the cardinality of one or the other set to an extreme. It has been also proved that a vanishingly small subset of positive integers can count every discrete entity in the universe and beyond.
@@aligator7181 You are saying nothing but: "I am right because I say so". What you *incorrectly* call "floats" are numbers with a finite decimal expansion. Of course there are countably many your numbers; all such numbers are rational. Nobody disputes that. But Cantor's theorem is *not* a theorem about your structure; it's a theorem about real numbers as conventionally defined in mathematics. As a matter of fact your structure is *not* how real numbers are defined. (Mathematical terminology exists for a reason - so that there's no ambiguity about what you mean.) Got it already?
@@MikeRosoftJH I must ask you never to send anything to me. Expressing an opinion once, no matter how idiotic is I guess your right, but pummelling somebody relentlessly is a crime. I will report you.
@@aligator7181 It's you who is spamming your misconceptions about "floats" at any remotely related video or comment. So don't be surprised when I or somebody else responds. (And claiming that what I am saying is just an opinion - and an "idiotic" one at that - is like claiming that 2+2=4 is just an opinion.)
thank you sir, really nice explanation.
I can’t get how a method than never ends can be a proof.
Diagonalization works with any finite list of numbers and it’s fine: it finds a new number not in list.
But, since we need to use the method for a infinite list of numbers, the generation of the new number just doesn’t end.
The diagonalization argument can be done without this 'infinite' procedure, since all it is showing is that no surjective function exists from the naturals to the reals. Once can prove there is a bijection between the real numbers and the the power set of the natural numbers, so it suffices to show that there is no bijection between the natural numbers and its own power set, but you can demonstrate that is true for any set A, that there is no bijection between A and its power set, regardless if A is infinite or not.
To do so, suppose such a bijection did exist, say f: A to P(A). Then the set B of all elements of A that don't get mapped to a set containing it, so all x in A such that x is not in f(x), is itself a set and a subset of A, and thus a member of P(A). Thus some member y in A must map to B since f is a bijection with f(y) = B. However, this is impossible, as such a y means that if y is in B then y is not in f(y) and thus y is not in B, and if y is not in B, then y is not in f(y) and thus since y is in A we have y is in B. Thus y is in B if and only y is not in B, a contradiction.
The infinite procedure works via using real analysis to demonstrate that the constructed number at the end exists, and the real numbers are defined by the very same procedure, so you can't deny the existence of the constructed number without also denying the real numbers existing as well.
How you know for sure that is not on the list? Maybe it is somewhere down below your list.
Thank you
I don’t understand how this will give you a new number. I mean I get the methodology. But you would need to change infinitely many cells in order to ensure that a number further down the list is not identical to the constructed number. For this method to work you would need a complete list which isn’t possible. So maybe the argument is dual edged, because a complete list can have a new number, but an incomplete list is uncountably infinite?
YOU'RE AWESOME
This was shown in Vsauce's "How to count past infinity".
i think some of you might find these observations interesting. I would greatly welcome comments on what i have suggested here......................The means which Cantor employed in his proposition of diagnalization, i.e., about the infinite string of real numbers being larger than that of natural numbers is discussed and considered in a context in which it is ignored that there is no such thing as infinity in material reality for it defies the means and manner of existence which is that anything that does exist must be distinct, delineable and quantifiable. This understanding includes the products of the realm of the abstract as well in that there is none which is not ultimately the product of the material, contextual referents in reality, that context from which they arise. For example, the abstraction of a pink flying elephant is one formed of the fusion of the material colour pink, the material phenomenon flying and the material entity, elephant. What mathematicians such as Cantor have done is employ the most general understanding of infinity as a concept but ignore the inevitable contradictions which arise, muddying the waters of the context in which their propositions are formulated and presented.
1. Consider that the infinite string of natural numbers is a progression, that which extends outward (forever). Each unit member is a value, the progression advancing by that value plus 1 each time. However, that to which it is being compared, i.e., the infinite set of real numbers is structurally the opposite within the boundaries of the proposition.
• In the infinite string or natural numbers, the span between any two unit members is ignored and the line proceeds from each value to the next, extending out forever.
• In the proposed infinite string of real numbers, the list of unit members from the first unit member designated to the next, any other which might be identified (e.g., 1 to 2 or perhaps 1 to 1.00000001, etc.) is itself infinite. For this reason, the string cannot exist beyond its consideration as a line segment which is still problematic for reasons I point out below, its overall length a value arbitrarily assigned but finite. So, in the case of the real numbers, the infinite line of unit members would be contained within two designated units with infinite points between and could extend beyond that. The string of numbers does NOT extend outward but rather within itself. This is comparing apples to oranges.
- There could be no list of real numbers for the designation of the very first in the list would never be completed or would just be impossible for it would have infinite digits. None of the real numbers could be designated and thus, nor could the list. This is not unlike the problems that arise with line segments in which it is claimed that they are composed of infinite points, yet they cannot be because if of finite length, each end would have to be designated by a point beyond which there was no other which by definition would mean that those points would have to have scope and dimension which would mean that there could not be infinite points composing the line segment. However, if these end points had scope and dimension, what would that be? If 10x, why not 5x then why not 1x, ad infinitum. Thus, the line segment could NOT be composed of infinite points but at the same time would have to be, demonstrating that infinity cannot be paired with material concepts due to such inevitable contradictions.
• What then would be the measure by which the string of real numbers was determined to be larger than that of natural numbers? Here we see that the string of natural numbers was being considered by Cantor as such per its unending length, that length forced by the denial of consideration of the span between specified unit members, e.g., 1 to 2 to 3, etc. However the string of real numbers could not be judged in its size in comparison to the string of natural numbers because it would have infinite members within the span of the first two unit members specified. What this means is that both must be considered in terms of unit members only and not by the abstractions of their lengths, as if each at any specified length would have different quantities of unit members. Instead, the string of natural numbers could not be considered in terms of the span between two designated members and the string of real numbers must be considered in and only in that manner. Since length of the string then is not a consideration, we are left to consider only and compare the number of unit members in which case they are equal, their “quantity” being infinite. I would say this is a bad analogy to make a mathematical point.
This proposition of Cantor’s seems to be very sloppy in its disregard for the true nature of these concepts of infinity he employs.
Getting big VSauce vibes from this video
Can't you do the same "Cantor Diagonlization" with the integer numbers too? Just make every number start with an infinite trail of 0s. E.i: ...0000001, ...000000002. And then do the Diagonalization technique to this set to get a new number?
If you do that, you will get something like ...111111111112.
And it's true that ...111111111112 is not on the list of natural numbers! But ...111111111112 is not, itself, a natural number. Each individual natural number has finitely many nonzero digits. (This does not mean there is a global cap to how many digits a natural number can have; natural numbers can get arbitrarily long, but they can't get _infinitely_ long.)
So although we have found something which isn't on the list, it also _shouldn't_ be on the list, so we can't conclude the list is incomplete.
When it comes to real numbers, however, you _can_ have infinitely many digits extending to the right of the decimal point. So the newly constructed diagonal number _is actually a legitimate real number._ So we have found something which _should_ be on the list, but isn't. That's why we can conclude the list is incomplete.
Great video thank you very much. Will do my assignment now.
Still I can not understand this argument. Maybe because I consider that we have already listed all the real numbers from 0 to 1, so the diagonal "procedure" creates a number which already has been mapped to an integer.
The argument shows that it is impossible to list all the real numbers. The diagonal argument guarantees that the new number is not in the list. The diagonal number can't be the nth number in the list because it's nth digit is different to the nth digit of the nth number that is in the list. That is true for every natural number.
Ok. So the list consists of “real numbers.” How do you add or multiply two of them? (non repeating)
There are a few different constructions of the real numbers, and each of them defines what it means in that construction to add and multiply. But this video presupposes all of that.
@@DrTrefor Cuts as defined by Rudin are real numbers (addition, multiplication, etc) and decimals are cuts. But this defines any cut, and decimals in particular, up to a countable number of digits because a cut at most exhausts the rational numbers, which are countable.
And then addition and multiplication of any two reals can be defined by induction.
Also, since any real number on your list contains a countable number of digits, and thus is a natural number for any number of digits, the list is countable.
Thanks for taking the time to answer my comment.
@@DrTrefor One might say that the real number is the lub of the digital sequence, ie, distinct from the sequence. In that case, if you added lub to each countably infinite sequence of digits, you would at most double the number of real numbers in your list, which would still make the reals countably infinite.
@@wernerhartl2069 You are weasel wording. The number of digits is countably INFINITE, not countably FINITE as you are trying to trick people into believing. The number of digits is NOT a natural number. It is the smallest infinite cardinal (aleph-0). You also know that is the case, so your weasel wording is actually deliberate deceit.
Your initial question has nothing to do with the topic of the video.
Most of what you said in your last conet is wrong too. I strongly suspect that you know that you embellished something that you read. You are definitely conflating numbers with numerals. In mitigation, in this case it might be your stupidity rather than your dishonesty that led to it.
If you add 1 to the first digit, Why can't it (the number 2 ) exist lower on the lis as a first digitt? There can and must exist a many numbers lower in the list that is also 2 as the first digit. And sane for the second digit being 4. The explanation seems to not make sense.
The proof ensures that the number created differs from every other number by at least one decimal place. It is a fool proof way to create a number not on the list.
Why do you add one to each digit and not just take the digit as it is?
Because that wouldn't guarantee that the resulting number is different from all numbers in the sequence. Take for example the sequence 0, 0.1, 0.11, 0.111, ... . If we take a real number which for n-th position after the decimal points takes the n-th digit of the n-th number in the sequence, we get the number 0.000...=0, which is in the sequence (at the first position). The point of the diagonal proof is to generate a number which differs from every number in the sequence; and it does so by taking the n-th digit of the n-th number and changing it, so that the n-th number differs from the diagonal number precisely at the n-th decimal position. (Observe that the number 0.111...=1/9 doesn't appear in the above sequence, at any position n for n being a natural number.)
The problem that I have with the diagonal create new numbers method and the claim that "we can always construct a NEW number that is different from on the list....." is that, how is this any different from integers for example....u can physically list out all the integers you want...... and no matter what, there will always be infinite others not on the list....... you can list-out a chart with 1 to a googol and that still represents exactly 0% of infinite integers ..... so how would this be any different the perceivable "infinity inside infinity" ideas.... I understand for example there is infinite numbers between 0 to 1, 1 to 2 etc etc...... but how is this additional breakdown/dissection any different from infinite integers.... They both go on forever.... its simply "that which has no end no matter how u look at it
I completely agree with you! However, I spoke to a set theorist and he said that you can't have an infinite sequence of digits that is a natural number and I believe that's the main difference. What makes Cantor's argument is that decimals seem to go on forever. I don't actually think they do go on forever but that's what most mathematicians think. Even a decimal like .1 supposedly goes on forever because it can be written as such .10000... with an infinite amount of zeros after the 1. Cantor's argument wouldn't work on natural numbers because the list apparently wouldn't be horizontally infinite. So, for example, you couldn't have the natural number 100...000 where the digits go on forever. What this means is that you couldn't take a diagonal of every digit place. This all seems very counterintuitive to me and that's why I personally don't accept this argument. I think that regardless of what number you have you can always add more digits to it. These numbers don't actually exist. They are abstract concepts in our minds that are in some sense created only when we write them down.
@@michaelsayad5085 The set theorist is correct. So what. It has nothing to do with the topic in the video. BTW you asked the wrong question. You should have asked him if infinite decimals are OK and he would have said "of course they are". It's infinitely large natural numbers that don't exist.
The proof starts by assuming that we have a COMPLETE list of ALL of the reals. It then shows have to construct a new number that is not on the list and this proves that the original assumption was wrong. There is no possible infinite list of infinite decimals that you cannot construct a new number from. What beats me is how so many people don't get this extremely simple logic.
@@michaelsayad5085 "These numbers don't actually exist. They are abstract concepts in our minds ..."
That's right. They only have a pure abstract existence. They are not part of physical reality.
"...that are in some sense created only when we write them down."
Are you suggesting that the number 42 didn't exist until someone wrote e.g. XXXXII? How would that make it come into existence?
wowow thank you so much for this!
Why can't we just add one to the natural number?
What natural number do you want to add 1 to?
Isn’t the procedure for determining the digits of the diagonal number of exactly the same form as that for determining the digits of a computable number?
No. Your question is gobbledygook too.
Do you understand what a computable number is?
@@lawrencedoliveiro9104 Do you? If you did, you wouldn't have posted your *irrelevant* question.
A computable number is one where, for any integer n, there exists an algorithm for computing the nth digit of the number.
Note that “algorithm” necessarily means the computation must terminate in a finite number of steps.
Do you think the Cantor diagonal construction fits this definition?
@@lawrencedoliveiro9104 So how do you propose to write a finite program that includes infinitely many infinite length decimals that are in no particular order.
Whatever, this has absolutely nothing to do with the topic of the video.
why don't we talk Plank's length on this?
cool video ty!
Hey! thanks for the help! Got a new sub here :)
You’re most welcome!
I'd like to see more :)
Suppose you rearranged your infinite list. You would then get a different diagonal number not on your list. If you did this an infinite number of times you would come up with an infinite number of diagonal numbers, all different, not on the list.
Indeed! Although what is more interesting is whether you have created a countable number of new numbers this way or an uncountable number, what do you think?
@@DrTrefor Thanks for the reply. Of course I deny that the diagonal number exists in the first place (last element argument) but for the sake of argument the only way to answer your question would be to check whether each diagonal number exists in any of the other lists, which is impossible.
You should check out
th-cam.com/video/K9gRZO96YRc/w-d-xo.html
And the replies to the comment that begins with .33333
Actually, in principle you could do the following: At the nth step in the creation of the diagonal number you could check whether your n diagonal elements are on any other list. There is no way to prove that eventually it would or wouldn’t be.
The replies to my two comments in
th-cam.com/video/XlKeEzYwtxw/w-d-xo.html
are also interesting.
@@wernerhartl2069 Of course the diagonal numbers exist. Maybe you are a finitist, in which case the whole thing is a non-starter for you because, for you, infinite decimals don't exist and infinite lists don't exist.
What is the last element argument? No entry in the list has a last digit and the list doesn't have a last element. Each constructed number could be inserted into the list. It would only be the last item chronologically. It could be the first element, but not the last because there is no such thing. The new list would be a different list. At no step would the list become larger (i.e. the cardinality of the set it corresponds to would always be aleph-0).
For the current list, you construct a new number in such a way that it is guaranteed to not be in the list. Including it into the list makes a new list. You are now back to square one. Because the next constructed number cannot be in the list, it cannot have been in the previous list. It won't have spontaneously spawned. There is no magic going on.
@@wernerhartl2069 Of course a permutation of the list would give you a different new number.
what a powerfull idea
Where is episode 3?
it,s good. but i have some questions. can i ask?
I have a high probability of being wrong ,But I intuitively find this theory flawed
You have created the last member of a list which doesn’t have a last member, just like the natural numbers don’t have a last member.
No he hasn't. He constructed a number that isn't in the list at all. It can't be the last number (by position) because there is no end. It could be included in the list. It would only be the last one chronologically.
I watched this video because you had told me that Prof. Bazett (as he now is) said that 0.999 .. . < 1 in it. He did not say any such thing.
I think he must have misunderstood you when he gave you some love. He didn't realise that you were a crackpot that thinks that Cantor was wrong.
@@Chris-5318 Chris, this is a really aggressive, unhelpful comment that repeatedly mobilizes the language of authority and status instead of explaining clearly how Werner might understand it better, which may indeed be why Prof Bazett has “liked” the comment above and not yours. Tip from a math educator, calling people crazy is not a good way to teach.
Like, come on man. This isn’t politics. It’s math. When you see someone express some doubt about a complicated idea, you should not feel whatever rage you seem to be feeling. Try thinking of it as an opportunity to teach instead :)
@@griffinbur1118 Werner and I have some history. If he was mathematically competent, I'd call him a crank. But he isn't - he is a dishonest idi0t that intentionally spreads misinformation. Several mathematicians, including professors have tried to explain things to him (as have I). He just makes up math and tries to fob it off as if it was standard math. He "quotes" sources, but actually lies about what they say.
@SubZee An infinite list can be complete. The list of the natural numbers is 1, 2, 3, . . . is complete even though it is infinite. Identify at least one natural number that is missing from the list. Similarly, you can have a list of all the rationals. What the argument proves is that you can never complete a list of the real numbers - they are unlistable. What you can't do is actually write every term of an infinite list - I suspect that is where you are getting confused.
There is no such thing as an incomplete real number. The idea is nonsensical. What is the first decimal place that you think has been missed when constructing the new number?
Isn't what you described at 0:32 a surjection, rather than a bijection?
Well you can use the cantor-schroder-bernstein theorem and find an injection from rationals to naturals(the snake but skip the repeated elements) and an injection from naturals to rationals rationals(obvious) and then the CSB theorem tells you that there must be a bijection between the two!
There are cleaner arguments for this, but this can work and if you havent yet seen the theorem look it up and try to learn and understand the proof
ur mum
@@DrTrefor ur mum
🐐
땡큐 유알 배털 댄 마이 프로패서 마이 500만원 해즈빈 공중분해 바이 유어 라스트 10미닛
Before listing the reals you have to define them. In particular, you have to define “infinite number of digits.”
LOL you are getting desperate you crumbly old git. Let's play the game of infinite descent with the deinitions of words. First you had better define "Before", "listing", "the" "reals", "you", ...
Here you go: A set is infinite, if its number of elements is not equal to any natural number. (It's not an empty set, it doesn't have exactly one element, it doesn't have exactly two elements, it doesn't have exactly three elements, and so on. Of course, the "and so on" part is a bit involved; you can't have a formula of an infinite length.)
Ok you are taking a diagonal and adding a digit. How do you know that number is not on the list. It could be. You are just saying it's not.
If you believe that the sequence contains its diagonal number, then at which position is it? No matter what index n you choose, I can say: no, that's not it: the n-th number in the sequence differs from the diagonal number in precisely the n-th digit, and the two numbers can't be the same. Sure, you can add the diagonal number to the sequence. You can't add it to the end, because there is no end; but you can add it to the beginning (or, if you want to, to the millionth position), shifting all numbers after it one position forward. But that yields a different sequence, for which the diagonal proof still applies - it has its own diagonal number different from the first, which the sequence doesn't contain.
Here's your construction, Cantor's Zeno paradoxes be damned: 0.0,...,9.9,00.00,...,99.99,...,oo Done.
If you want finite expressions for irrational numbers, go for it. It's the same set, assume "..." At the end of each number. Then interleave with the original set. This is superfluous though.
Okay, that construction does not work for irrational. Not all of them end with “...”. Where is pi and e included in your construction?
@@GaryLuKOTH it's infinite, they are there contrary to your statement. Nonetheless why do you think pi is not there?
@@GaryLuKOTH perhaps you have seen the Infinite Hotel video? If for some reason a number comes off the bus calling itself pi, you keep advancing it up the room number as that passenger reveals digits to you, ad infinitum. If it really bothers you, give rooms 1 and 2 to pi and e and be done with it.
@@jok2000 You're acting like pi and e are the only transcendental numbers that are not included in your set when in reality, all of them are not included (In fact, can you give me a single irrational number that is encoded in your construction?). There are uncountably many transcendentals, so you do not have enough rooms for all of them.
@@GaryLuKOTH you don't seem to recognize the construction is infinite, that's what the ... Is for. So I'm going to stop going around in circles right about here then.
I need help understanding this proof.
Doesn't it implicitly assume there is a finite amount of numbers between 0 and 1? Obviously, the diagonal method would work given a finite amount of numbers and you'd be left with a new one. But given an infinite amount of digits, you can't say for certain that if you repeated this process infinitely many times, that you'd get a different number; that goes against the whole concept of infinity, doesn't it? You're basically assuming your infinite amount of numbers doesn't contain a certain number...
No, it doesn't assume anything like that. Obviously, there are infinitely many real numbers in an interval from 0 to 1. The proof essentially goes as follows: let a be any arbitrary function from natural numbers to real numbers (=infinite sequence). Then there exists a real number which is different from a(n) for all natural numbers n (from any number in the sequence). Therefore, no function from natural numbers to real numbers covers all reals.
Sure, you can add the diagonal number to the sequence. You can't add it to the end, because there is no end, but you can add it to the beginning (or, if you want, to the millionth position), shifting all numbers after it one position forward. But that will yield a new sequence (function from natural numbers to real numbers) which has its own diagonal number. You can even perform the operation infinitely many times (by interspersing the two sequences); but you'll still get nothing else than an infinite sequence, to which the theorem still applies. In addition, by a slight extension of the proof it can be shown that for any infinite sequence of real numbers there are uncountably many real numbers which all differ from every number in the sequence.
This is one of those things that makes most people think high level math is just mental masturbation.
Haha fair:D
Why is he so sure that the number on the Diagonal is not on the list?
If you believe that the diagonal number appears in the sequence, then at what position is it? No matter what position n you choose, I can say: no, that's not it; that number differs from the diagonal number by precisely the n-th digit after the decimal point, and the two numbers can't be the same. Sure, you can add the diagonal number to the sequence. You can't add it to the end, because there is no end; but you can add it to the beginning (or, if you want to, to the millionth position), shifting all numbers after it one position forward. But that yields a different sequence, for which the diagonal proof still applies - it has its own diagonal number different from the first, which the sequence doesn't contain.
In addition, by a slight extension of the proof, it can be shown that there are uncountably many real numbers which the sequence doesn't contain - the set of uncovered real numbers can be mapped one-to-one with real numbers as a whole.
@@MikeRosoftJH thanks! mate! I figured this out after some time :)
How are you changing every digit of the diagonal when there are an infinite amount of them? It seems to me that at every point you change a digit of the diagonal that segment can exist as part of some real number in the infinite list. It's only when you change all of them, which seems to be an impossible task since there's no point at which all of them are changed. It's like adding all of the digits of the natural numbers. We get 1, 3, 6, 10, 15... but there's no point at which you've added them all since it's impossible to add an infinite amount of numbers. Likewise, we can change ten digits, a hundred digits, or a billion digits of the diagonal but unless they are all changed it seems to me that a new real number is never formed.
This is exactly what I was thinking, I have no clue surely an infinite number of real numbers means we would eventually come across the diagonal number
@@Chris-5318 So, what is it?
What beats me is that you seem to have accepted that infinite decimals are OK. Why aren't you saying they are not possible because you can't finish the infinite task (of "adding" all the digits or whatever)? (Fortunately, there is no task).
@@Chris_5318 I never accepted that they are okay. With you in the other conversation, I accepted that rational numbers and prime numbers can be set up in a bijection with the natural numbers. I still don't think 1 = .99999... but I was working off your premise that it does and trying to see the consistency of your view. I still don't think real numbers have an infinite number of digits.
However, I see your point. In this comment, I tried to simplify my view. I don't only think the diagonal is impossible, I also think the infinite expansion of the real numbers is impossible. You are correct!
@@michaelsayad5085 Sorry, I had replaced my comment before seeing you had responded. The "new" decimal just satisfies a rule. The nth digit is not the same as the nth digit of the nth entry in the list.
For e.g. Pi all the digits of the decimal representation exist even if you haven't computed any, yet alone all, of them. Similarly, the natural numbers are a complete infinite set: {1, 2, 3, . . . } There is no process generating them. There aren't going to be more tomorrow than there are today.
Since we may define an infinite number as something being not a finite number, like we define irrational numbers as numbers that are not rational, it follows that all infninite numbers are the same: infinite, with the same size: bigger than the real numbers. Then we can extend the real numbers with these infinities (let's make a negative infinity as well) to get the extended reals!
Nice video. Just a courteous FYI: I speak Hebrew - it's "Ah leph" (as in "hah") vs. "Ey leph" (as in "hey") ;)
@@DrTrefor Yep, no prob ;)
Prove it!
He did.
@@Chris_5318 I can give you for every list of non-repeating real numbers a list of integers counting through them. Therefore, I claim, the sets of real numbers and integers have the same cardinality. Disprove it!
@@Lauschangreifer Easy, watch the video.
@@Chris_5318It maybe only proves that Cantor's method of assigning an integer to every real number does not work.
Give me real numbers in any order and I will count them. Doesn't that prove that there are equal numbers of real numbers and integers?
@@Lauschangreifer Cantor proved that you cannot assign an integer (actually a natural number) to every real number. He didn't prove the opposite.
You cannot list all the real numbers, regardless of the order that you try. You cannot even think up a *valid* scheme to attempt such a thing.
Like many of the people that have commented here, you simply haven't understood the video.
God save me from math !
I can't wrap my head around this, could it not be that it's simply sitting in a higher dimension?
Just like comparing a line and a plane is unfair, because a plane is an infinite set of lines
but you can line it up with x and y(both integer lines) and you get a plane of rationals.
When using the reals you would need a third z line
so when you add the 1 during diagonalization, you are moving up in the z line, the third dimension, which will be an infinite set of 2d planes.
Is it fair to compare the area of a plane with the volume of a cube?
I don't know what you mean by 'unfair', but in both cases we're just considering sets with objects in them. There's no 'higher dimension'. However, (filling in your idea somewhat) you can for example view the set of rationals as a 2D version of the natural numbers N, since each fraction p/q is basically a pair (p,q) of natural numbers (disregarding the fact that some fractions are the same). Another dimension wouldn't add anything, since if you consider the set of all triples (p,q,r) with p, q and r natural numbers, then you wouldn't end up with a larger set
Adding more dimensions just means extending the diagonalization process to tuples of higher arity. Countability is not affected.
The cardinality of the set of points in a line is the same as the cardinality of set of points in every n-dimensional space (where n is a natural number). Cantor proved that too.
Surely if we had an infinite number of reals then surely we would eventually find the diagonal number we created
The proof shows that what you claimed is impossible.
5:45 see the numbers on the end of the board to the right.
1 dived by 0 = infinity
0 dived by 1 = 0
Am i just being stupid here? lets repeat the same argument for "is integers (0, inf) the same size as integers (0, inf)" by lining them up and doing the diagonal?
There are infinitely many natural numbers; but every natural number is finite in magnitude (and that's by definition: a set is finite, if its number of elements is equal to some natural number). So the decimal expansion of any natural number has finitely many digits. If you apply the decimal procedure to a sequence of all natural numbers, you get a sequence with infinitely many non-zero digits, which doesn't represent any natural number.
if the list is infinite then ofcourse it has all decimal numbers between 0 and 1 so why would adding a diagonal one add a new number, if every number already is there
The assumption was we can list them. If that isn’t true, then it doesn’t have to hold them all
@@DrTrefor so the list wouldnt be infinite, so what does that prove? then you could always add another integer if the list isnt infinite, right?
idk but i think its because since the real numbers are already infinite in length the number the diagonal lands on will always be +1
@@jusu8961 LOL it proves that there are more real numbers than natural numbers and so it is impossible to list all the reals. In turn, that's because each line in a list corresponds to a natural number.
the only problem is if you were to actually create the list and rearrange the list after creating the diagonal , the problem magically disapoears. or if you rearrage the list you get a different diagonal snd a different number that fails...to say the nimber is not in the list is partially true
You have it backwards. Because both sequences contain the same elements, it follows that neither sequence contains either the first or the second diagonal number.
@@MikeRosoftJH there is no such thing as different number of infinite numbers in two sets of infinite numbers. since infinite is un countable. The natural numbers also can be diagnolized and the inverse diagonal line cannot be found in the list...but it doesnt matter. This is simply a faulty construction.
@@farmerjohn6526 No, there indeed are different sets of natural numbers: natural numbers can't be mapped one-to-one with real numbers, and no set can be mapped one-to-one with the set of all its subsets. Conversely, it's your construction which is faulty: diagonal proof cannot be applied to a sequence of natural numbers. There are infinitely many natural numbers; but every natural number is finite in magnitude. And that's by definition: a set is finite if its number of elements (or cardinality) is equal to some natural number - it is an empty set, or it has exactly one element, or it has exactly two elements, or it has three, four, and so on. (Of course, the "and so on" part is a bit involved; you can't have a formula of an infinite length.) So every natural number has finitely many digits. If you apply the diagonal procedure to the sequence of all natural numbers, you get a sequence with infinitely many non-zero digits, which doesn't represent any natural number.
@@MikeRosoftJH infinity is not countable. While it might seem one set is bigger, that is an illusion. Think of negative number vs positive numbers ...so if you combine the set it seems the combined set is bigger. But that is wrong. An infinite number of things has no size. Two Infinite sets also have no size. Its not like you have 2xinfinity... or Infinite plus Infinite.. an infinite number of integers can map to an infinite number of reals... The diagonal problem is complicated. For example if ypu assume the set of numbers is complete, then the inverse diagonal must exist..but it can't exist....the contradiction is confusing. Basically it implies you cannot create a complete set of real numbers....which suggests to me something else is wrong..
@@farmerjohn6526 A set is countably infinite, if it can be mapped one-to-one with natural numbers; in other words, if there exists an infinite sequence of elements of that set, such that every element appears at some finite position. (An infinite sequence is no more and no less than a function whose domain are natural numbers.) So integers are countably infinity, because they can be enumerated by the following sequence: 0, -1, 1, -2, 2, -3, 3, ... - any integer n appears at a position no greater than 2*|n|+1.
It certainly is possible to define size (cardinality) of infinite sets. Set A has the same cardinality as set B, if sets A and B can be mapped one-to-one. Set A has no greater cardinality as set B, if A can be mapped one-to-one with a subset of B. (It can be shown that if set A can be injected into set B, and B can be injected into set A, then there exists a one-to-one mapping between the two sets; so the two definitions agree with each other.) And this is precisely the same definition as in case of finite sets: imagine that you are in a cinema, and see that all seats are occupied - nobody is standing, nobody is sitting on two seats, no seat is empty, and no seat has two people in it. Then - without needing to count them - you can tell that there's the same number of seats as people. Conversely, the result that natural numbers can't be mapped one-to-one with real numbers means the same (just for different sets) as that you can't put ten guests in nine rooms, such that no two guests share a room.
Just because cardinality of infinite sets doesn't work the same as finite sets, that doesn't make cardinality of infinite sets somehow ill-defined. (For example, it can be the case that an infinite set can be mapped one-to-one with its strict superset or subset; here's a one-to-one function between natural numbers and a strict subset thereof: n -> 2*n.) It's perfectly well-defined: for any two sets it either is, or isn't the case that set A can be injected into set B (i.e. mapped one-to-one with a subset of the other set). (But that every two sets are comparable in this sense - that either A can be injected into B, or B can be injected into A, or both is the case in which case the two sets can be mapped one-to-one - is a consequence of the axiom of choice.)
You are confused about the fact that you can't have a reverse diagonal in the infinite table of the diagonal proof. Sure, you can't; but that only says that natural numbers do not have a maximum under the usual order. (You sure can define a different order, for example one under which 0 is the minimum, 1 is the maximum, 0..., and any even number is less than any odd number. That's not a very useful order - in particular, it isn't consistent with the usual mathematical operations + and * on natural numbers - but it's a perfectly well-defined ordering relation.)
Besides, the infinite table and its diagonal is just a visualization of the proof; it's not the proof itself. Let me present a proof of the related theorem that no set can be mapped one-to-one (or onto) the set of all its subsets:
* Let A be any set. P(A) is the set of all subsets of A. (That this set exists is a consequence of the axiom of powerset.)
* Let f be any function from A to P(A). (That is: for any x∈A, f(x) is some subset of A.)
* Let D={x: x∈A and x∉f(x)}. (For any x∈A, f(x) is a subset of A. There are exactly two possibilities: either x∈f(x), or x∉f(x). D is the set of all such elements, for which x∉f(x); that this set exists is a consequence of the axiom of separation.)
* By construction, D is not equal to f(y) for any y∈A. Let y be any element of A; there are exactly two possibilities:
** 1) y∈f(y); then by construction of set D, y∉D.
** 2) y∉f(y); then by construction of set D, y∈D.
** In either case, f(y) differs from D by the inclusion of y.
* Therefore, the function does not cover all elements of P(A) (all subsets of A); in particular, it does not cover the set D.
* Therefore (because I have assumed nothing about the function f, or about the original set A), the same is true for every function from A to f(A), for any arbitrary set A. QED
The proof that natural numbers can't be mapped one-to-one with real numbers is similar.
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.
What you would construct wouldn't be an integer. You would create a real number, but since it's not an integer, there's no contradiction.
@@brianzucaro6538 how is it not an integer? The number i constructed is a whole number with no decimals
@@shivpatel3311 It'd have an infinite number of positions with a decimal? Each number along your diagonal would be a 0 since it's after the decimal point, and thus your constructed number would have every position filled with a non-zero value.
Unless you're instead going the other way, instead looking at the ones place, the tens place, the hundreds place, in which case the object you construct would not be an integer, and we can demonstrate this since it must be arbitrarily larger than any other integer if it were one, contradicting properties of the integers. For any integer x, there's a natural number n such that n > x, and since 10^n > n, 10^n > x. Since your sequence is a bijection, there must exists a point past the 10^n position where we encounter a 0 digit, since if we never did, then we'd have only n positions to list 2* 10^n + 1 numbers, an impossibility, thus our constructed object has a non-zero entry in the 10^n position and thus the constructed object, if it were an integer, is greater than x. Since x is arbitrary, this means if our constructed object were an integer, it is larger than all other integers. However, this means this constructed object is also larger than itself, and thus by the addition rules of the integers, we also have that 0 > 0, a contradiction.
As well, you say you're mapping the real numbers onto the integers: I assume you mean the natural numbers onto the integers, since Cantor's Diagonalization explicitly is built on utilizing the countable infinity of the natural numbers. If you really mean the real numbers, then you haven't defined this 'diagonal' you're referring to.
so essentially, the reason the real number's infinity larger than integer's infinity because real numbers are already infinite to begin with?
Nope. It's because the reals have a bigger infinite cardinality than the infinite cardinality of the naturals.
You have shown D exists for n digits of n sequences. Why does it exist for an infinite number of sequences which have an infinite number of digits?
This is the same leap of logic as normal counting or induction, namely at any step I know what to do at the next step
@@DrTrefor Induction only works with a single countable infinity. Your list has two independent infinities. For example, I could have three sequences consisting of infinitely many digits. You have to relate the infinities.
@@DrTrefor
n decimal digits give rise to 10^n sequences, no matter how large n is.
NOW you can apply induction. CDA fails for ALL n.
No. You are still missing the point. You don't construct the diagonal number in steps (with the diagonal number of the whole sequence being the "infinity-th" step); you define it as a whole. And for your final argument - as I constantly tell you - you are making an invalid proof by "magical induction". It's the same nonsense as claiming: "The empty set is finite; the set {0} is finite; the set {0,1} is finite, the set {0,1,2} is finite, and so on - for any natural number n, if the set {0,1,...,n} is finite, then so is {0,1,...,n,n+1} - adding a single element to a finite set can't yield an infinite set. Therefore by induction, the set {0,1,...,n} is finite for every natural number n [this is correct]. Therefore by 'magical induction', the set of all natural numbers is finite [this is of course incorrect]." What you have really proven is that there are countably many numbers with a finite decimal expansion; and that's not a new result: all such numbers are rational.
Let's do the diagonal proof once again:
* Let a(n) be any function from natural numbers to real numbers (in other words, any infinite sequence of real numbers).
* Let d(n) be the following sequence of digits: d(n) is the n-th digit after the decimal point of a(n) (the n-th number in the sequence). (For lack of ambiguity: if the number a(n) has two different decimal expansions, like 0.1000...=0.0999..., then use the expansion ending with infinitely many digits 0 rather than 9.)
* Let d'(n)=d(n)+5 mod 10. (In other words, d'(n), for all natural numbers, is the n-th digit of n-th number of the sequence, increased by 5 and wrapped around zero if necessary.)
* Let D be the real number whose decimal expansion is d'(n). (The integer part is 0.)
* For any natural number n, a(n) has - by construction - a different decimal expansion than D, and the two numbers can't be equal. (It can also be shown that the two numbers differ from each other by at least 3*10^-n.)
* Therefore, the sequence a(n) does not cover all real numbers; for no natural number n is a(n)=D.
* Therefore - because I have made no assumptions about the sequence a(n) - the same is true for all sequences (all functions from natural numbers to real numbers).
If you believe that the diagonal number could appear in the sequence, at which position is it? It can't be the first, because the two numbers differ from each other by the first digit after the decimal point. It can't be the second, because the two numbers differ from each other by the second digit after the decimal point. And so on; for any natural number n a(n) differs from n by the n-th digit, and the two numbers can't be the same.
@@MikeRosoftJH Specifying a procedure for calculating D doesn’t prove D exists. Directions to Chicago don’t prove Chicago exists.
The diagonal proof doesn't make sense. If you truly had an *infinite* list of real numbers then every number would already be on the list. There would be no space to make a new one so adding one or not wouldn't matter.
Why would an infinite list automatically be complete? For example if you look at the following subset of natural numbers {2, 3, 4, 5, ...}, it is obivously infinite, and you can list its elements (i.e. there's a bijection between it and the set of natural numbers). However, it is obviously not complete, because 1 is missing (and 0 depending on what definition of the natural numbers you prefer, but that is not the point)
@fiddley The video proves that your guess is wrong.
@@paketbaand1523
Exactly. Any list consists of individual items. Thus lists are countable. Real numbers are measures. There is no method of counting them.
Yeah but you can't encompass all of the integers either. For every real number you can assign an integer. If you have a new real number just add 1 to the integer set. They're both infinite so you never run out.
The crux of the proof is that there is no final list (or function), because the assumption of its existence leads to the contradiction that it is in fact not complete.
You cannot assign an integer for every real number. There are too many real numbers That what the video proved. You need to watch the video again. Remember, the starting assumption is that you supposedly have a list of all the real numbers, not just some real numbers. Maybe try some Google searches.
The word countable actually means listable. In other words we can assign every element in the set a unique numeric identifier (typically done as a natural number). Thus for the set {a,b,c} we could give a 1, b 2 and c 3. Thus if I gave you a number say 3, you could tell that I am referring to c. Countable is a highly deceiving word and most likely why I see so many rejectors of the theory in the comments. Thus for a countably infinite set, there MUST EXIST a bijective function from the natural numbers to the set, but what cantor showed is that whilst we can create an injection, we can never make it a surjection and hence why the set is not countable (but remember this means listable). And this is because no matter how small or big the interval is we will always be missing a number from the set.
@@Chris_5318 Actually I don't think it proved anything. Even if you start with a list of all real numbers, you can still make a list of integers that are the same length, simply by counting them. And whenever you find a new real number that is not on the list, you add the next integer to the list of integers. Just as you can always find a new real number that is not on the list, you can always add 1 to the highest integer to get the next one, which also was not on the list.
@@grantofat6438 You haven't understood the proof at all. You cannot actually start with the list of all the real numbers. That is what was being proven. The list of all the integers can be made, and you will cannot find an integer that is not in that list. Such a list starts 0, 1, -1, 2, -2, 3, -3, .... You cannot write aby such list that in such a way that you can use the diagonal argument to find a missing integer.
i really dont get it. why cant we just pair it like that:
0 - 1
0.1 -2
0.01 - 3
0.0001 -4
and so on and it will continue till infinity and it will never reach 0.2 but why does it have to? we said if we can pair them than they have the same size.
@@Chris_5318 what? i dont understand.
@@NuNiia95 That's pretty obvious.
@@Chris_5318 dont play the clown if ur not gonna explain it to me
@@NuNiia95 Your original comment has nothing whatsoever to do with the topic of the video. I cannot imagine why you think it might. You have simply given a sequence whose nth term is 1/10^n and whose limit is 0.
I didn't try to explain anything to you because I had hoped that you might realise that what you had said has nothing to do with the topic. Silly me.
@@Chris_5318 if you thought with just writing "what are you on about" i would understand it then you are really silly. but after reading ur explanation and watching these 2 videos again i understood it.
Just put 0.0-0.9 in 10 dimensions. Each extra digit creates another 10 branching dimensions. Do this infinitely, then just draw a simple infinite dimensional spiral through all of them. Boom. Counted that shit.
Your procedure appears like nothing but handwaving. No matter what sequence you have come up with, it doesn't contain all real numbers - given any function from natural numbers to real numbers, there is some real number which the sequence does not cover. (By extension of the diagonal proof, there are uncountably many uncovered real numbers - the set of uncovered numbers can be mapped one-to-one with real numbers as a whole.)
I don't fully understand. Okay, you can always find "another" real number, but then I can always find "another" natural number to pair up with that real number. Like I have 0,001? Ok, I will take "1" from N. I have 0,0001? Ok, I take "2" from N. Like I can always find some brand new N number to pair up with some number from R.
PinkySuavo think about this way, assume you right and you can pair the real number Y from the diagonal with a natural number X, then you would have the pair (X,Y) written down in the table. However, This method proves that your number cannot be found in the table at all, therefore the assumption must be wrong.
You can find a brand new natural number, but as the diagonal line goes on and on, the "new number" that is made won't ever be in the list. Your new natural number also has to be paired with a real number, and that real number will have at least a single digit not matching with the new number, since 1 was added to one of the digits of the real number(which is paired with your brand new natural number).
Not sure I really understand, but here's how I think about it. Lets take 4 numbers (pretend these are in rows like the video): [1,2,3,4], [2,3,4,5], [3,4,5,6] and I make the 4th the same as the diagonal (to be sneaky) [1,3,5,6]. The last number is the same as the diagonal of the four numbers. OK, but now I have to add 1 to each diagonal digit to make a new number. This number, [2,4,6,7], isn't in the set, but - no problems - I just make it the 5th number. But, the problem is this 5th number isn't part of the diagonal. So, I need to add an extra digit to each number so my diagonal includes all 5 numbers. OK, I do that - eg. [1,2,3,4,0], [2,3,4,5,0], [3,4,5,6,0], [1,3,5,6,0] and [2,4,6,7,0]. But, now, my fifth number no long matches the +1 diagonal (which should be 2,4,6,7,1). It doesn't matter what you make that last digit of the 5th number - it never matches the +1 diagonal rule. You can keep adding numbers, but then you always need to add an extra column, which then makes your extra number not match the diagonal +1 rule. However, I don't really understand how this shows there are more of these than integers - just seems to indicate that because columns must equal rows, an infinite number of columns are needed, and so an infinite number of integers to match. So, maybe I haven't understood it correctly..
@@austenganley8220 I found this one a little simpler th-cam.com/video/mEEM_dLWY0g/w-d-xo.html
@@austenganley8220 You need to pick the function from natural numbers to real numbers as a whole.
* Let a(n) be any function from natural numbers to real numbers (in other words, any infinite sequence of real numbers).
* Let d(n) be, for all natural numbers, the n-th decimal digit of a(n). (If a(n) is a number with two different decimal expansion, like 0.1000...=0.0999..., use the expansion ending with infinitely many digits 0 rather than digits 9.)
* Let d'(n)=d(n)+5 mod 10. (That is: d'(n) is the n-th digit of a(n), increased by 5 and wrapped around zero if necessary.)
* Let D be the real number whose decimal expansion is d'(n).
* It can be seen that given any natural number n, D is a different number from a(n): n-th digit of D and of a(n) are different (and it can't be the case that d'(n) is an alternate decimal expansion of that number, either). It can also be seen that the two numbers differ from each other - no matter what the remaining digits are - by at least 3*10^-n.
* Therefore, D is not equal to a(n) for any natural number n; in other words, the function a(n) does not cover all real numbers (in particular, it doesn't cover the number D).
* Because I have made no assumption about the function a, the same holds for all functions from natural numbers to real numbers - given any function from natural numbers to real numbers, there is some real number which the function does not cover. QED.