This is high-key the only video online that made me understand Cantor's Diagonalization. It wasn't even the Pokemon pictures, it was just the really clear animations that put this together. Thank you so much
Somewhere I don't quite understand how this works... I mean, assuming I have a list of numbers 2234, 7128, 5826 and 1343 (in that order), wouldn't the diagonal proof still just result in 2234, which is a number of my list? What am I missing here?
Add a bunch of zeros to each of your numbers and continue the diagonal pattern. This theorem would not work if we were limited to a set of only 4 numbers. You would run out after 9,999 variations of numbers 0-9 in a set of 4.
Hey great vid but question: the first thing u discuss is how we can have a surjection between rows of Pokémon and numbers and this shows there are at least as many rows as numbers. But isn’t surjection the wrong word? Since we can have a million rows all mapped to one number and it’s still a surjection but it’s not one to one/injective. So I don’t see how simply a surjective shows that the rows are at least as big as the naturals. Can you help me off?
My dog Frances died 6 years ago. If I waited for her to come back to life how long would I wait? That would be an infinity right? So a bigger infinity would mean a longer wait time than infinity? What would that mean in terms of hours and days? And I would suggest the famous Hilbert Hotel paradox about infinity is nonsense. The Hilbert Hotel has an infinite number of rooms and each room has a guest. A new guest arrives and the guest in room 1 moves to room 2, the guest in room 2 moves to room 3 and so on. After that process finishes... um, no that process will continue to the end of time. After it finishes we can see if there's a paradox. The diagonalization proof also assumes that infinity is finite. You will never produce a number using that process since every real decimal number has an infinite number of digits and the process will take an infinite amount of time and never produce a number. All the diagonalization proof proves is that Cantor did not understand infinity.
All I am saying is infinity is not a number, it is a process. If you want to do operations on numbers and get meaningful results, use numbers. You can create a number that is so huge it may as well be infinite. For example, you might compute the practically infinite number Pri by raising a googolplex to the power of a googolplex and take that result and raise it to the power of a googolplex and repeat that process a googolplex number of times. Pri is a natural number and you can perform arithmetic on it while avoiding any paradoxes. If you have a hotel with Pri rooms and guests and add a guest, moving everyone to the next room results in guest number Pri having no room. Want to prove 0.9 followed by Pri 9s equals 1? It won't happen. Multiple 0.9 followed by Pri 9s by 10, subtract 0.9 followed by Pri 9s from it and divide the result by 9 and you get 0.9 followed by Pri 9s once again, and not 1. As for the physical world suppose you have a monkey hitting random keys on a typewriter and each of 100 different characters has an equal chance of being produced. Would the monkey ever type out a perfect copy of Hamlet? Hamlet has 177,000 characters and the first part of the document is DRAMATIS PERSONAE, the cast of characters. If a supercomputer were to produce a random string of characters, with each character having 1 chance in 100 of being the next character in Hamlet, the sun would burn out long before it would correctly produce the DRAMATIS PERSONAE section in the front of the play. That is your physical world. But a string of characters of length Pri would have a practically infinite number of copies of Hamlet in it, a number 99.9 with 9s stretching to the moon percent of Pri as the number of copies of Hamlet. The number of combinations of characters that will contain Hamlet is 100 to the power of 177,000, a miniscule number compared to Pri. Please excuse me for ranting but I get tired of mathematicians trying to do mathematics on something not a number and then marveling at the weird results.
Shouldn't we be able to work out that the number of rows must exceed the number of columns? If so, the resulting matrix isn't a square matrix and the diagonal method doesn't work because it omits rows. Maybe that's the point, but couldn't we just work that out with math on factorials?
If the number of columns is larger than the number of rows then you have already proven that there is an infinity larger than the set of all natural numbers. If the number of rows is larger than the number of columns then your sequence of Pokémon is finite because there is a natural number N that is map to the last Pokémon sequence.
So, you just add 1 to list and go on. Ez. I still can't get, why the size of all natural's is countable? You may as well do the diagnolization. Just put 0's before the num so every number has the same length. Then in your list change the first symbol for the first number, second for second and so on and vuala, you uncountable list of natural's
The point is, no matter how long your list is, your still always missing numbers, you could add an arbitrarily large amount to the list and you would be forever missing infinitely many reals. As for the 'reverse cantor', you do get a number thats not part of the natural set, but it isnt a natural number, it has infinite digits.While naturals do _approach_ infinite digits, they are still extremely finite.
Really dig the video, it’s the best explanation I’ve found. However, I don’t understand why the same diagonalization proof can’t be used on the natural numbers to prove the size of its infinity? Wouldn’t any number in the rational number set map to the natural number set if we lobbed off the “0.” prefix (e.g, 0.284 -> 284)? So whatever the new rational number created via diagonalization would also map to a natural number, meaning their infinites are the same size?
That just maps Natural into Reals but for them to be equal you need to map them both ways. Diagonalization shows that this is not possible. You can always find new Reals that is not included in your mapping. For example in your mapping scheme what natural number represent 0.02, 0.002, 0.0002 all of them will be map into 2 so the mapping is not 1 to 1.
"How can we reconcile the contradiction here? Well, because everything we did was mathematically valid, there must be something wrong with our starting assumption." How do we know everything we did was mathematically valid? Is there really not a way to perform this same trick the other way around, to prove that the set of natural numbers is larger than the set pokemon? My intuition says that such a technique of creating a new element simply breaks down at infinity, or there's some axiom that somehow assumes there are different sizes of infinity that you're sneakily appealing to, making the proof subjective.
This is a great question! Try it out, first we take each digit off the diagonal, string them together...but then what did we actually make? It's something with an infinite list of digits, which isn't a natural number anymore. So this new thing we created doesn't need to be on the list. The reason diagonalization works with real numbers is because when you string together the numbers, it's still another real number due to the infinite nature of decimals.
Actually all natural numbers have an infinite number of digits, but by convention we don't write the infinite list of 0s preceding the significant digits. It's not tidy. If you're truly asserting that a natural number must have a finite number of digits, then how many digits does one need to represent all of the elements of N? I think the contradiction is raised not by invalidating the initial conjecture, but by invalidating the subsequent conjecture that you can create a diagonal across a non-square matrix in which each of the rows is represented in the computed line. So. if we have a set of N-element lists where each element can have one of three values, then there are 3^N lists in the set of all possible lists. So how do you even construct a diagonal of N elements where each of the 3^N lists corresponds to an element in the computed N-element list? Keep in mind that as N approaches infinity, the number of lists grows exponentially faster than does the number of elements per list, so the portion of lists represented by the diagonal rapidly approaches 0% as N approaches infinity.
John Eisenmenger It doesn't matter how much the rows are represented in the finla row, it just needs to differ by at least one digit from each row. As for the natural numbers with an infinite amount of digits, it just doesn't work that way; a number like ...999999 would need to be infinite and thus not a natural number. After the decimal point, however, the values decrease exponentially (is that the right word?) and therefore has a limit, just like no 3-digit number can be bigger than 1000.
Sobez, I realize that the whole "N lists represented on the diagonal versus 3^N lists in the full set" is probably the point of this proof. I'd even considered replying to my own comment saying as much... My issue is that this conjecture breaks down for lists of any length > 0, so proving it is breaks down for lists of infinite length (IMO) doesn't really demonstrate anything new. I'm willing to accept that I'd need to study a lot more to understand why this proof is accepted as such, but I'm just poking at it and not really vested in spending the time to figure it out. I do appreciate your response though!
why do you start the analogy of flying pigs and then instantly drop it before its even served its purpose or intended purpose ? why even make it at all ? its just confusing
Another way i like to think that there are bigger infinities is this Think about an infinity that repeats 1 111111111111.. Then think about an infinity that repeats 2 222222222222.. No matter what, the 2 infinity will always be bigger
None of this makes any sense and that’s not due to your explaining it poorly. The problem is that the assumption set out to be disproven is nonsense. How can there be an amount of the numbers (a number of the numbers)? The numbers are used to count amounts but don’t themselves have an amount. We say they are infinite. But infinity isn’t an amount. When we assume the numbers have an amount we derive absurd conclusions like that there are more numbers between 0 and 1 than natural numbers. Unfortunately people don’t seem to realize how outlandish this is. If infinities were amounts then it would be true, but they aren’t.
3:29 See this is where the problem comes in Lets replace all the dumb pokemans with 123 If the list is complete, we must be able to take a row, lets say row 1 (111...). Because we assumed the list is complete then if we cycle all the digits of row 1 we should get a new row (111.... => 222...) that exist inside the list . The row that we cycled from row 1 should exist just fine For some examples so you dont get confused: 232323... => 121212.., 2222.... => 3333..., 123123 => 231231... You should get what I meant Now we construct a row called _d_ by gathering all the diagonal digits 1: *1* 111111111111... 2: 1 *2* 3123123123123... 3: 12 *3* 3231113142122.... 4:121 *3* 221332213.... 5:1232 *4* 3233121122... Etc So _d_ would look something like this :12334.... _d_ can exist just fine in the list no problem, but that means we can cycle all of its digit to get a row that should also exist inside the list (12334... => 23441...) we call that row _i_ . But wait a minute isn't that the row that exist nowhere in the list? Does that means _i_ can exist inside the list? Well lets say _i_ is the 4th row, _d_ is the 3rd row 1: *1* 111111111111... 2: 1 *2* 3123123123123... _d_ : 12 *3* _?_ 122... _i_ :231 _?_ 233... 5:1232 *4* 3233121122... Why did I hides 2 digits from _d_ and _i_ ? Well because it can't be 0 or 1. Like we said be for _i_ is _d_ cycled which mean those 2 digits must be different (since theyre both 4th digit), but since the 4th digit of _d_ must be the same as the 4th row's 4th digits (which is i's 4th digits) both _d_ and _i_ can't exist. The diagonal row can't exist, the complete list can't exist therefore your argument is invalid even if you came to a valid point (that is no complete list exist). /Taken from "CONTRA CANTOR: HOW TO COUNT THE UNCOUNTABLY INFINITE"/ You should take a look at that because it also tells you how to count them
The whole point is that the complete list cannot exist; given any function from natural numbers to 10^ω (set of all infinite sequences of digits 0..9), there is some element of the latter set which the function does not cover.
This argument is just wrong. If you have an infinite list of every row, then BY DEFINITION you will find said row somewhere on the list. You cannot construct a list that is not on the list that already contains every possible sequence. That is the logical fallacy you are making.
The other thing i would point out is to compose a "new" number, it ONLY works if there is an actual "floor" or END of the sequence. A "new" number will NEVER be created bc the list goes on and on and on forever. It just doesn't seem valid IMO to make assumptions about infinity based on how u can manipulate a finite "sample" list.
@@dom8898 Nope, it still works if the list is infinite. The number created by diagonalisation is new because it doesn't match any of the numbers on the existing infinite list.
@@MartinPoulter but the existing list though is "finite" if you pick any type of an arbitrary stopping point no matter how deep down it is, the so-called existing list represents exactly 0% of infinity [ it would relatively be as if you counted nothing in comparison to what's left to come ]
@@dom8898 Who said anything about a stopping point? There is no stopping point: the premise is that the rows of the list correspond to the natural numbers, which do not end.
@@MartinPoulter This is where it gets a little too weird for me though..... for example if you pause it at 4:04 at look at the highlighted sequence of 7 pokemon.... that is NOT a "complete" diagonal. There is no way he could ever "show us" a "complete diagonal" , it will always have to just be a "sample" which IMO is in fact a stopping point. You are only able to point out its not on the list by having a finite list above to point at to begin with. I understand the concept of what the video is trying to prove but I guess I just can't buy into it, it seems too big a leap of faith to assume it works on an infinite scale..... The other thing is whenever you pause the sequence like at 4:04, there will always be an infinite amount of sequences that can still be counted..... It seems to invalidate the "we made a new sequence that is not on the list" argument when there is simply infinite amount to go anyway, its all the same isn't it? On a side-note even IF we accept the point of the video that new numbers are being made by composing new ones along the diagonal, I guess that would possibly prove real numbers progress quicker in the count vs naturals? But is that what is being debated in the first place? progression is different from total size..... if they are both never-ending whats the difference?
Instead of just labeling the rows...also label the diagonalization with a number and boom... The infinities are equal again... This is so stupid... infinity is infinity... they cannot be less than...
@@bruhbruh1807 anyways this video is an example of potential infinities (growing infinities)… not actual infinity. Potential infinities can be unequal… as they can be “stopped” and examined at any point in time and their finite sets compared. An actual infinity is not comprehensible… but if it were comprehensible… the lists would have to be equal.
How is this possible... cantor's diagonalisation is so bull....how can you possibly take all the diagonals from a infinite sequence....the serial number rows are also never ending ...we are just within the numbers ....you just can't take infinity from infinity and say this shit is bigger than that....there is no scale to measure the infinity...so there is no point taking diagonals and changing them to something else ....that row itself will never end...number of elements that makes sense to our perception which yk like this infinity has this much elements till here so but this infinity has less....which is soo stupid both of them never ends...such a bogus video...ahhhh
@@DataLog Actually sir, YOU are wrong. There is no "growing" at all. The set of all real numbers is not "growing". It IS. It contains all real numbers. If you reference the set of all real numbers you are not referring to a bucket of real numbers that is having more and more real numbers added to it all the time, you are referring to ALL REAL NUMBERS THAT EXIST at once.
@@DataLog Now, given that we know that there is no "growing" involved in infinite sets, we can go on to the next point. If two sets are the same size, we would be able to create a 1 to 1 mapping of elements from one set to the next. If there is not exactly 1 element in Set A to which we can attach to exactly 1 element in Set B, they must not be the same size. If there are 5 boys and 5 girls, we can match one boy for each girl. The set of boys and girls are the same size. If we had 6 boys and 5 girls, the sets would not be the same size and we know this because we cannot create a 1 to 1 mapping from the set of boys to the set of girls; one of the girls would need to be mapped to two boys. Thus, when we show that the set of integers cannot have a 1 to 1 mapping to the set of real numbers, we are demonstrating that they are not the same size. If two sets are not the same size, one of them is larger. If two infinite sets are not the same size, then one of the infinite sets are larger. I.E. one of the infinite sets has a larger quantity of numbers.
@@blackhawk8261 Ok dude, I think you get the point. In some infinities you get to a larger and larger digit faster (and in some slower) by moving from the prevous number to the next. I know it's not the most precise way to explain things, but I assumed that detailed explanation wasn't necessary...
@@blackhawk8261 Yes, I've argued this mapping argument in another comment section. We literally wrote books about it. And in the end, the argument distills to a very simple conclusion. Both sets are infinite. I didn't think that this requires much explanation. It's not like we are talking about rational and irrational numbers, where you lack the description of an irrational number if you keep it in just 1 dimension, we are comparing two rational infinities. Infinity is infinite, and the only difference you can find between these two mentioned infinities would be this "speed" (same explanation as from the previous comment due to simplicity). In which, this diagonal number will most definitely reach over the final number in the infinity that we are observing. And precisely because there are no speeds (now I'm talking literally about the speed of growth as an incorrect concept) between infinities, this rule doesn't really prove anything. I'm not saying that these two infinities are the same, I'm just saying that this "diagonalization" rule is a very flawed explanations and basically it relies on semantics and a limited definition of an integer in order to work. It doesn't intuitivly, nor mathematically prove anything. I will try to link you a comment section where I've discussed this with a mathematician in a great detail. Making too much of these comments is difiicult and useless. + my english vocabulary is somewhat limited, so I am making big mistakes in translation. For example, in my language, we use the word that translates to "faster/slower growth" when we describe infinities of different sized steps between the integers. So this doesn't translate well. I made an effort once, I can't make it twice.
@@ruce9269 This math is wrong, period. There are no bigger and smaller infinities. There are only FASTER and SLOWER growing infinities. Veritasium is now spreading the same misinformation.
Yes especially the example at 3:30 were you could see that the new row almost matches with the fifth row but because the fifth row was on the list it was off by a Pokémon. @DataLog I understand your point of view but do you understand stand what they are trying to say.☝️
When you look at a fraction of a real number, it's like you're zooming-in on one point of the numberline Infinitely. When you look at a never-ending set of integers, it's like you're zooming-out to see the ever-increasing numberline.
Thank you sincerely. I just spent hours watching lectures from other professors on youtube and reading math forum posts to understand this, and you explained it brilliantly in less than 7 minutes. This has been a fantastic help.
Hey man, love the videos! I just have a question about the logic here. How is it ok to just alter a list like that. That list WOULD'VE existed if you didn't pull it out and alter it. The only reason it can't exist now is because of the external parameters you put on it. I feel like it's analogous to questioning where your dinner went after you just ate it. :/
I can see how it feels like we altered the list, but we actually didn't. First, we fix some arbitrary list (which must exist if we have a countably infinite set). We then use the list to define an element and ask where that element lives. This list itself is unchanged, we are just trying to figure out where one of the rows of Pokémon (or numbers) exists. The answer is that it has to be there if the list contains everything, but by the way we created this row, it also cannot be there, a contradiction. In the dinner analogy, it's as if you said you have eaten every possible food, and then I create some weird recipe and ask you at what point in your life you ate this strange food. If the answer is you never did, then you didn't actually eat every food possible.
it's not analogous to questioning where your dinner went after you just ate it because that is finite but this problem is dealing with infinities, that means you can take a list out and alter it because the very act of being able to alter it and create a new list means that it is possible for that list to exist thus it must be part of an infinite set
I first learned about bigger and smaller infinities when I was a junior high school kid and read George Gamow's "One, Two, Three, Infinity." I still haven't recovered from the shock.
I think it has clicked with this video. You're all basically saying because the angular number (that is infinitely long) is derived from the infinite list, for a change in all numbers (whatever the rules you use to change it, the only rule: no number matches the number it originally was), no number in that infinite list could possibly match the new number because it is derived from an angle of all the numbers (hence infinitely long). The list could contain any possible number including the one you made up... including until you form a number from the angle of those numbers. This number would be there, but a change to it would make it not possibly there even in all infinity.
Somebody please explain. consider you assume that you can match up natural and real numbers 1 -> 0.043343... 2 -> 0.34334... 3 -> 0.4333343... etc... we apply diagonal argument to the real number however why could we do this for the real numbers eg take the first number 1, the second number 2 the third 3, change them and end up with a new number - why is this wrong? thank you
There's lots of videos on YT about Georg Cantor's diagonalization proof re. the cardinality of the infinite set of all rational numbers vs the infinite set of all real numbers... but, not gonna lie, I picked this one because it had Pokemon in the thumbnail instead of some old guy in front of a black board. And I actually understood it this time!
Because every natural number is finite in magnitude, and so it has finitely many digits. If you were to try to apply the diagonal procedure to a sequence of all natural numbers, you get a string with infinitely many non-zero digits, and that doesn't represent any natural number. (Conversely, while real numbers are also finite in magnitude, they can have infinitely many non-zero digits after the decimal point.)
4:32 But if I got a natural number with infinite digits and added one to each digit diagonally and if it’s a 9 make it a 0 then it would also be different from every other natural number
@@LC19. That follows from how real numbers are defined. A decimal expansion 0.abcdef... is defined to mean the infinite sum a/10 + b/100 + c/1000 + ... . And an infinite sum is defined to mean the limit of the sequence of partial sums: a/10, ab/100, abc/1000, ... [where by abc etc. I mean the natural number whose decimal expansion is abc, not a*b*c]. And this sequence is a bounded, non-decreasing sequence (for example, no element of the sequence is greater than 1); so by the property of supremum the sequence has a limit. It can also be shown that every real number has a decimal expansion (but some real numbers have two different decimal expansions: 0.1000... = 0.0999...).
Here's an existential crisis inducing thought: The number of characters we use in the union of all human languages is finite (English, Chinese, all natural languages, and all symbols used to make well-formed formulas in formal maths). If we take every possible string of such characters and put them into a set, it would only be countably large (and would include all computable numbers and probably lots of uncomputables like Chaitin). With the reals being uncountable, there must exist an uncountable about of numbers that individually cannot be defined with well-formed formulas. I like to call these numbers "ineffable numbers." The fact that this argument works for any uncountable set also tells us that ineffable numbers are dense within the reals, stretching across the infinite like an eldritch horror, yet seeping their Lovecraftian tentacles into every crevice of the known universe. And somehow, despite all of this, these numbers are practically invisible to the human mind. For anyone wondering if this could be formalized: all you need to do is use a finite set A to represent an alphabet, and, for each natural n, create a map from {1,...,n} to A. Such maps are strings. Take the set of all strings of size n, and pick out the gibberish strings (there are grammars that can be used to keep the sensible strings. These are essentially operations that let one take small wff's and inductively combine them to make each of the bigger ones.), then take each sensible wff with one free variable: P(x), and keep the ones that which are satisfied by exactly one real number. These can be thought of as "definitions" of said reals. Since the set of "definitions" of size ≤ n must be finite, the set of all definitions is countable. Also, If you are thinking you can get around this by formally defining the set of definable real numbers D, and creating its complement R\D, and saying let x be a member of R\D (which you can totally do), note that you haven't really defined an undefinable number. Yes, you can follow each of these steps, but the number you make isn't a specific number, it's a generic number, meaning it isn't truly rooted to an actual value. It's a stand-in, much like letting p be prime creates a stand-in for a prime and doesn't define a particular number like 2. I guess, in a way, these ineffable numbers can be talked about, but they cannot be constructed. An interesting consequence of this fact is that the existence of a number implying its constructability is in direct conflict with the existence of uncountable sets. This would also put such exotic beings in conflict with Cantor's theorem and with the ZFC axioms that allow uncountable sets to exist. I also have to wonder how many of math's "choice functions" (which are used for bizarre things like the well-ordering theorem, the Banach-Tarski Paradox, the construction of sets with undefined Lebesgue Measures, and every other reality-breaking thing mathematicians have built) would no longer work without these ineffable entities? Feeling small yet? Well, with the subsets of the real line, continuous nowhere-differentiable functions (Check out the Baire-Category Theorem for more info on this b.s.), higher cardinal numbers in general, Conway's surreal numbers (They make the proper class of ordinals look like a joke), and inaccessible cardinals (outside the reach of ZFC), we've only just begun. Good luck on being able to sleep ever again, lol.
Awesome video, I really like the style. It was able to explain to my mother why there are different sized infinities :) while still being mathematically accurate.
I still cannot wrap my head around comparing one thing that never ends to another thing that never ends. Even after the video, it just doesn’t make sense to me. There are an infinite amount of both, they are the same infinity. You can’t have more or less infinity ever. It just doesn’t make sense to me. That row that wasn’t on the list.. of course it was, just so long the list is infinite. Infinity holds all possibility, all lists. I don’t know.
Wait, does this mean we can take a finite list and basically create inifnite new information from it? Or does this only work for already infinite lists? 🤔
"Paul Cohen proved that we can't prove the Continuum Hypothesis true or false." Actually *pushes up glasses* Kurt Gödel proved that we can't prove it false (i.e. CH is consistent with ZFC).
Interestingly, Gödel did more than one thing in his career. I'd suggest looking up his book "The Consistency of the Continuum Hypothesis" (1940, Princeton University Press). The better response to my first post would be "Actually, only if ZFC is consistent."
Every "proof" that there are different sizes of infinities is predicated on immediately tossing out the definition of infinity and assuming that you could iterate through an infinite sequence in a long afternoon. You can't just whip through the list and get a new combination BECAUSE THE LIST IS INFINITE. If you could magically take forever changing Pokeymens around, you would still NEVER finish, and every combination that you came up with would already be on the list. Let's disprove this dumb idea by considering another possibility. Imagine we invented some brand new natural numbers and added them to the set of all natural numbers. Now the list of natural numbers is bigger than the list of combinations of Pokeymen. Ha ha!! Proof that you're wrong!! OK, I can't just invent more natural numbers. And you can't find a combination that isn't on a list of every possible combination, either. But, I feel like you need more, so here it is. Imagine the list is not infinitely long, it's only two digits and there are only two Pokeymen. So, there are four possible combinations: [1,1 1,2 2,1 2,2]. Now, find another combination that isn't already on the list. You can't. The list already holds EVERY POSSIBLE COMBINATION. But, what if you spent an infinite amount of time scrambling those digits around. EVENTUALLY you would come up with a new combination, right? No, you wouldn't. Yet, in the other example, we started with an infinite list of EVERY POSSIBLE COMBINATION, yet, somehow, magically, we come up with a new combination. Sleight of hand. The list is far too long to see the whole thing, so the rube will imagine that EVENTUALLY there is a new possible combination to be found. But, there simply isn't. You got to make up the rules and assumptions to your own proof, and yet you almost immediately violate them. But, there's this process . . . Yeah, your process is a joke and it won't work. Like a lame magic trick, this fakie [tired of calling it a "proof"] is based on misdirection. Once the guy in the cheap suit gets you nodding about how this method would lead to a NEW combination, you are stuck. But it won't and it can't and it really has nothing to do with infinity, nor does it have to do with forever. The faker asks you to assume that every combination is taken up, then tells you that there's a new combination. There isn't, is a lie, it's already taken up, there are no new ones to be made, you can't do it, your logic sucks, you have proposed your own demise, no, no, no, no. There is exactly one size of infinity.
You can iterate all the natural numbers in and hour. First count 1 then after 30 minutes you count 2 after 15 minutes you count 3. If you keep halving the time to count the next number. You can count all of then in 1 hour.
Okay. That covers all numbers with finitely many non-zero digits after the decimal point. All such numbers are rational, and that there are countably many rational numbers is not a new result. At what position does 1/3, or √2/2, or pi-3 appear?
i like your idea. however if you read the numbers backward than we can use the same proof to show that there are more integers than integers. for example lets assume we can give every integers an integers hear is an attempt at a mapping however this proof works for any arraignment 148230000000... 574895738000000... 57348920489475839000000... 384934000000... 50493249000000... 00000000000001000000... 1010101010... ... however i can prove that there is a integer we missed by taking each number than taking that number + 1 mod 10 so in this case the missing number would start 2840410... can some one tell me the flaw in this reasoning
@@MikeRosoftJH if you read the numbers backward than we can use the same proof to show that there are more integers than integers. for example lets assume we can give every integers an integers hear is an attempt at a mapping however this proof works for any arraignment 148230000000... 574895738000000... 57348920489475839000000... 384934000000... 50493249000000... 00000000000001000000... 1010101010... ... however i can prove that there is a integer we missed by taking each number than taking that number + 1 mod 10 so in this case the missing number would start 2840410... can some one tell me the flaw in this reasoning
@@ivanthomas8503 There's no such natural number as "148230000000...", or the like. 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.
The videos on your channel are really impressive. You're creating high quality content without a large number of viewers, but I suspect that will change quickly. Great stuff, keep up the great work!
This is not your best video. The "proof-by-contradiction" piece with the pig probably should be replaced with something betterer - I found it pretty clunky: "1=2 therefore pigs don't fly"
You can treat each Pokemon as an integer. Charmander is 0, squirtle is 1 and bulbasaur is 3. Then list them by counting. In the respective (number of Pokemon)^n fashion.
Im here from a graduate class in computer science; Theory of Computation. The problem was to prove why the infinite sequence over {0,1} is uncountable.
Undefined Behavior What if I told you there are just as many rows of Pokemon as there are natural number how much would maths change?? (assuming I disprove this prove of course) and prove that the infinity are in fact equal using your same bijection rule???
I think of infinity as a numerical representation of a universe. Some universes can be bigger than others with more space inside of them even though both are expanding.
¿Será posible, verificar la correspondencia biunívoca, existente entre los números reales y (0, 1) de (R), empleando el método del Argumento de la diagonal de Cantor? {Siendo, aún más significativo, poder verificarla entre: (0, 1) de (R) y (0, 1) de (R)} Del mismo modo, en que Cantor no detalla (FC(x)) - que en principio definiría como una función biyectiva entre los conjuntos de Lista(C) {f: (N?R)}, misma que, posteriormente declarara inexistente -; no detallare (FG(x)) - que en principio, definiría una función biyectiva entre los conjuntos de Lista(R) {f: (R?(0, 1) de R)}-. Y, si os pones muy quisquillosos, podemos recurrir a {f: ((0, 1) de R?(0, 1) de R)} Siendo (A: el conjunto de los números reales) y (B: el conjunto de los números reales entre (0, 1)) equipotentes, necesariamente deberá existir una correspondencia biunívoca entre sus elementos. Bien. Confirmémoslo, empleando exclusivamente el método del argumento de la diagonal de Cantor (ADC). Para ello, construimos una Lista(R), mediante (FG(x)), igualando (1 a 1) los números reales a los números reales entre (0, 1). Seguidamente, empleemos la (PDC()) - usada por Cantor para construir su número real x(C) entre (0, 1) del Codominio -, para construir el nuestro. Mismo que, obviamente, no estará contenido en Lista(R). Conclusión: entonces. Con un grado de rigurosidad similar, al empleado por Cantor en su método, demostramos que: empleando ADC, no es posible verificar una relación sobreyectiva - y por consiguiente biyectiva -, en Lista(R). En consecuencia, según ADC: los conjuntos de Lista(R), no deberían considerarse equipotentes - o sea: ((R)?˜(0, 1) de (R)) -. Demostrando así, lo contingente de este método, y consecuentemente, una fuente de inconsistencias de la teoría de conjuntos. Nota: ¿acaso demostré la absurdidad del método del argumento diagonal de Cantor? Salvo que: ¿propongáis revisar el teorema de Cantor-Schroder-Bernstein - o sea, los criterios para reconocer una biyección entre conjuntos -, y/o las demostraciones de equipotencia entre (0, 1) de (R) y (R)? No, mejor será, no seguir perdiendo el tiempo leyendo este compendio de tonterías, ¿verdad? Entonces, ¿el argumento de la diagonal de Cantor, es fuente de inconsistencias para la teoría de conjuntos? Entonces: un obvio resultado inevitable - la diagonal alterada del Codominio, no-pertenece al Codominio -, es prueba suficiente, de algo más, que de sí mismo - es decir: tal resultado, es independiente de la cardinalidad del conjunto del Dominio -? PD: dado que, al parecer, no he planteado esta obviedad de forma suficientemente inteligible, la repetiré de forma sutilmente más burda: a excepción de alguna inconducente convención matemática, ¿qué lista de números - construida en forma de un arreglo bidimensional cuadrado de dígitos -, puede contener, al número construido a partir de los dígitos alterados de su diagonal? Obviamente, la anterior pseudo-refutación, podrá ser constituida entre cualesquiera conjuntos numéricos infinitos - equipotentes o cuya potencia del dominio sea superior a la del codominio (para evitar suspicacias de devotos Cantorianos, emplear el intervalo unidad en ambos conjuntos de la función, apelando, a la equipotencia de un conjunto con un subconjunto propio) -, siempre y cuando, las propiedades del conjunto numérico del codominio, permitan expresiones decimales infinitas - distinta de cero - no periódicas.
Before now, I was content with diagonalization proving the uncountability of the real numbers. But I have thought of an example that is troubling me. Suppose you have an infinite string of zeros and ones. By diagonalization, the space of all possible such strings is uncountably infinite. But why can't I let each string represent a binary number, where the nth digit in the string represents 2^n? If this were valid, then I could make a bijection between each string and the natural numbers. Can somebody please explain?
You can't do that, because the decimal (or base-2) representation of any natural number is finite. (In fact, this is how a finite set is defined in set theory: a set is finite, if its number of elements is equal to some natural number). If you apply diagonalization to base-2 representations of natural numbers, you get a string with infinitely many non-zero digits; this doesn't represent any natural number. But you can use this to prove that you can't map natural numbers one-to-one with the set of all functions from natural numbers to the set {0,1}. (These functions naturally map to subsets of natural numbers. It can also be proven that real numbers, and subsets of natural numbers, have the same cardinality.)
If somebody could clarify this for me, it'd help me understand this video way better: Why is it at 3:16 ,when creating a new row of pokemon , that you need to change the each pokemon? English is not my native language so please forgive me for my horrible grammar.
You are constructing a row which is different from all the infinitely many rows already in the list. The row differs from the 1st row at position 1, from 2nd row at position 2, from 3rd row at position 3, from 4th row at position 4, and so on.
Could you not use the diagonalisation method to prove that there are an uncountable number of natural numbers by writing out all the natural numbers in binary, then taking the diagonal through them and switching 1s and 0s?
No, because every natural number is finite. Your diagonal number would have infinitely many non-zero digits (in fact: if you were to list all natural numbers in order, then *all* digits of the diagonal number would have been 1), which doesn't represent any natural number.
Once you create a new pattern from a "complete" list then there would also be a new natural number to "count" or index the new possible pattern. The only reason this appears to be a contradiction is because you are supposing that the natural numbers can be used as a container or index. This initial assumption already places a limit on an infinite potential of natural numbers.
I do not have a problem with the theorem except for when it is used to suggest that the infinity of 0-1 is larger than the infinity of natural numbers. At least equal to, I can accept.
no, you are iterating across the list for infinity and are never able to add a new natural number to index the new pattern. Because you are iterating for infinity, when are you able to insert a new number? You're thinking about infinity as if it's finite, as if you can add a new number when you get to the end except you can't, infinity cannot grow, it is complete by definition.
6:56; we assumed that the number of rows matches the number of columns. And this is what a square grid is. If we take any finite countable list, and fill a square grid; then alter the diagonal .... we get a new sorting that cannot be in the square grid .... which means the grid was not a complete representation of all the possible combinations of the elements within it. But we assumed the list was complete. For example, binary form, of length 1; gives us a complete list: { 0 1 } what does our square grid look like? each element of the set is of length 1, so should it be a 1x1? the are only 2 elements in the set, maybe a 2x2? but we have no elements of length 2 ... maybe we alter the form of each element? but then thats not assumed by the process given to us. The length of each element is not changed ... so to be fair to the proofing method, lets assume a 1x1 grid. Lets fill it up. Grid (1x1) { [0] } Now lets assume our square grid contains all the items of our complete list .... because we are told to assume it. Take the diagonal, and we get 0, change it to 1 because thats how we work the process. Show that the new item is not contained in the square grid ... well, its not in the grid. Since we assumed that the complete, finite list was contained by the grid ... Conclude that the list itself is incomplete? --------------------------------- Maybe we just need to grow our grid so that its gets to an infinite size? Well, lets see what an element length of 2 gets us: binary form, of length 2; gives us a complete list: { 00 01 10 11 } what does our square grid look like? Oh yeah, same as the size of an element; 2x2. Lets fill it up. Grid (2x2) { [ 0 0 ] [ 1 0 ] } Now lets assume our square grid contains all the items of our complete list .... because we are told to assume it. Take the diagonal, and we get 00, change it to 11 because thats how we work the process. Show that the new item is not contained in the square grid ... well, its not in the grid. Since we assumed that the complete, finite list was contained by the grid ... Conclude that the list itself is incomplete? ................... Well it did not work for the smallest possible setup; and it did not work for next largest one either. It seems that our grid holds the same number of items from the list, that is equal in size to the length of an element. For each growth in element size, the list is 2^n items long; but the grid can only hold n items total. Hmm, a 10x10 square grid only has enough room to hold 10 items; but the binary list is 2^10 items total. As our grid expands towards infinity; the number of items that the grid cannot hold is: 2^n -n. Is it fair to say the list is incomplete; because we assume the grid can hold it? This all has nothing to do with the value of any item in the list, it is purely a property of form alone.
"we assumed that the number of rows matches the number of columns." Yep. And that's because the decimal places of a real number are always in one-to-one correspondence with the natural numbers (giving us natural-number-many columns), and we also assumed the real numbers are countable, meaning they can be placed in one-to-one correspondence with the natural numbers (giving us natural-number-many rows). If the set of real numbers were countable, it absolutely could fit into a square grid.
@@MuffinsAPlenty We cant even fit a finite list of fractions into a square grid. My first example was all the ways we could represent a binary decimal expansion: 0/2 and 1/2. Two representations cannot fit into a one element tool. My second attempt example was all the ways we could represent a binary decimal expansion: 0/4, 1/4, 2/4, 3/4. Four representations cannot fit into a two element tool. We could do the same thing for the binary decimal representation of 8ths: 0/8 = .000 1/8 = .001 2/8 = .010 3/8 = .011 4/8 = .100 5/8 = .101 6/8 = .110 7/8 = .111 2^3 elements in the list; and only 3 of them fit into the grid When we get to the 1/2^n example, our list is composed of all the ways we could represent the binary decimal expansion: 0/n, 1/n, 2/n, ... , (n-1)/n. And 2^n representations cannot fit into an n element tool. These finite lists of fractions are said to be countable, and so they should absolutely fit into a square grid - but they obviously do not. Because? As the limit of n -> inf, the list does not get any better at fitting into the square grid. And we havent even tried to account for the infinite decimal fractions.
@@anthonym2499 "We cant even fit a finite list of fractions into a square grid." Yep. And similarly, you can't fit all real numbers into a square grid, which is what Cantor's Diagonal Argument shows. If the set of real numbers were countable, you would be able to fit them within a square grid. But you can't. So they're not countable.
@@MuffinsAPlenty If the set of rational numbers were countable, you would be able to fit them within a square grid. But, the set of rational numbers is countable ... so you should be able to fit them within a square grid. The proof isnt demonstrating the countability of the set. It is only demonstrating the property of the grid itself and not the contents within it.
This is high-key the only video online that made me understand Cantor's Diagonalization. It wasn't even the Pokemon pictures, it was just the really clear animations that put this together. Thank you so much
Well great. On a sidenote there are otger videos which are equally good as well.
this is the best video i've eve seen for a mathematical proof! well done with the animation and simple explaination
i've been looking for an explanation for that for days, this on is BY FAR the best
Somewhere I don't quite understand how this works... I mean, assuming I have a list of numbers 2234, 7128, 5826 and 1343 (in that order), wouldn't the diagonal proof still just result in 2234, which is a number of my list? What am I missing here?
Add a bunch of zeros to each of your numbers and continue the diagonal pattern. This theorem would not work if we were limited to a set of only 4 numbers. You would run out after 9,999 variations of numbers 0-9 in a set of 4.
But even in your example the new number would be 3234
Hey great vid but question: the first thing u discuss is how we can have a surjection between rows of Pokémon and numbers and this shows there are at least as many rows as numbers. But isn’t surjection the wrong word? Since we can have a million rows all mapped to one number and it’s still a surjection but it’s not one to one/injective. So I don’t see how simply a surjective shows that the rows are at least as big as the naturals. Can you help me off?
Excellent video explaining Carton’s diagolization.
My dog Frances died 6 years ago. If I waited for her to come back to life how long would I wait? That would be an infinity right? So a bigger infinity would mean a longer wait time than infinity? What would that mean in terms of hours and days? And I would suggest the famous Hilbert Hotel paradox about infinity is nonsense. The Hilbert Hotel has an infinite number of rooms and each room has a guest. A new guest arrives and the guest in room 1 moves to room 2, the guest in room 2 moves to room 3 and so on. After that process finishes... um, no that process will continue to the end of time. After it finishes we can see if there's a paradox. The diagonalization proof also assumes that infinity is finite. You will never produce a number using that process since every real decimal number has an infinite number of digits and the process will take an infinite amount of time and never produce a number. All the diagonalization proof proves is that Cantor did not understand infinity.
you're confusing the mathematical space with actual physical world.
All I am saying is infinity is not a number, it is a process. If you want to do operations on numbers and get meaningful results, use numbers. You can create a number that is so huge it may as well be infinite. For example, you might compute the practically infinite number Pri by raising a googolplex to the power of a googolplex and take that result and raise it to the power of a googolplex and repeat that process a googolplex number of times. Pri is a natural number and you can perform arithmetic on it while avoiding any paradoxes. If you have a hotel with Pri rooms and guests and add a guest, moving everyone to the next room results in guest number Pri having no room. Want to prove 0.9 followed by Pri 9s equals 1? It won't happen. Multiple 0.9 followed by Pri 9s by 10, subtract 0.9 followed by Pri 9s from it and divide the result by 9 and you get 0.9 followed by Pri 9s once again, and not 1. As for the physical world suppose you have a monkey hitting random keys on a typewriter and each of 100 different characters has an equal chance of being produced. Would the monkey ever type out a perfect copy of Hamlet? Hamlet has 177,000 characters and the first part of the document is DRAMATIS PERSONAE, the cast of characters. If a supercomputer were to produce a random string of characters, with each character having 1 chance in 100 of being the next character in Hamlet, the sun would burn out long before it would correctly produce the DRAMATIS PERSONAE section in the front of the play. That is your physical world. But a string of characters of length Pri would have a practically infinite number of copies of Hamlet in it, a number 99.9 with 9s stretching to the moon percent of Pri as the number of copies of Hamlet. The number of combinations of characters that will contain Hamlet is 100 to the power of 177,000, a miniscule number compared to Pri. Please excuse me for ranting but I get tired of mathematicians trying to do mathematics on something not a number and then marveling at the weird results.
Shouldn't we be able to work out that the number of rows must exceed the number of columns? If so, the resulting matrix isn't a square matrix and the diagonal method doesn't work because it omits rows. Maybe that's the point, but couldn't we just work that out with math on factorials?
If the number of columns is larger than the number of rows then you have already proven that there is an infinity larger than the set of all natural numbers. If the number of rows is larger than the number of columns then your sequence of Pokémon is finite because there is a natural number N that is map to the last Pokémon sequence.
Thank you, I watched a similar video before but there were no pokemon so i didnt get it. Pokemon really helped me underestand.
Number of Marth clones is uncountably infinite
So, you just add 1 to list and go on. Ez.
I still can't get, why the size of all natural's is countable? You may as well do the diagnolization. Just put 0's before the num so every number has the same length. Then in your list change the first symbol for the first number, second for second and so on and vuala, you uncountable list of natural's
The point is, no matter how long your list is, your still always missing numbers, you could add an arbitrarily large amount to the list and you would be forever missing infinitely many reals.
As for the 'reverse cantor', you do get a number thats not part of the natural set, but it isnt a natural number, it has infinite digits.While naturals do _approach_ infinite digits, they are still extremely finite.
Amazing video man! Thank you
a really great video
wish you infinite number of views :)
Pokemons really helped me understand Diagonalization. XD
The finite curve
Finally i understand it somehow
Really dig the video, it’s the best explanation I’ve found.
However, I don’t understand why the same diagonalization proof can’t be used on the natural numbers to prove the size of its infinity?
Wouldn’t any number in the rational number set map to the natural number set if we lobbed off the “0.” prefix (e.g, 0.284 -> 284)? So whatever the new rational number created via diagonalization would also map to a natural number, meaning their infinites are the same size?
That just maps Natural into Reals but for them to be equal you need to map them both ways. Diagonalization shows that this is not possible. You can always find new Reals that is not included in your mapping. For example in your mapping scheme what natural number represent 0.02, 0.002, 0.0002 all of them will be map into 2 so the mapping is not 1 to 1.
"How can we reconcile the contradiction here? Well, because everything we did was mathematically valid, there must be something wrong with our starting assumption."
How do we know everything we did was mathematically valid? Is there really not a way to perform this same trick the other way around, to prove that the set of natural numbers is larger than the set pokemon? My intuition says that such a technique of creating a new element simply breaks down at infinity, or there's some axiom that somehow assumes there are different sizes of infinity that you're sneakily appealing to, making the proof subjective.
mind blown
Could you use diagonalization on lists of natural numbers? (thereby proving that there are more natural numbers than... natural numbers?)
This is a great question! Try it out, first we take each digit off the diagonal, string them together...but then what did we actually make? It's something with an infinite list of digits, which isn't a natural number anymore. So this new thing we created doesn't need to be on the list.
The reason diagonalization works with real numbers is because when you string together the numbers, it's still another real number due to the infinite nature of decimals.
Actually all natural numbers have an infinite number of digits, but by convention we don't write the infinite list of 0s preceding the significant digits. It's not tidy.
If you're truly asserting that a natural number must have a finite number of digits, then how many digits does one need to represent all of the elements of N?
I think the contradiction is raised not by invalidating the initial conjecture, but by invalidating the subsequent conjecture that you can create a diagonal across a non-square matrix in which each of the rows is represented in the computed line.
So. if we have a set of N-element lists where each element can have one of three values, then there are 3^N lists in the set of all possible lists. So how do you even construct a diagonal of N elements where each of the 3^N lists corresponds to an element in the computed N-element list? Keep in mind that as N approaches infinity, the number of lists grows exponentially faster than does the number of elements per list, so the portion of lists represented by the diagonal rapidly approaches 0% as N approaches infinity.
John Eisenmenger It doesn't matter how much the rows are represented in the finla row, it just needs to differ by at least one digit from each row. As for the natural numbers with an infinite amount of digits, it just doesn't work that way; a number like ...999999 would need to be infinite and thus not a natural number. After the decimal point, however, the values decrease exponentially (is that the right word?) and therefore has a limit, just like no 3-digit number can be bigger than 1000.
Sobez,
I realize that the whole "N lists represented on the diagonal versus 3^N lists in the full set" is probably the point of this proof. I'd even considered replying to my own comment saying as much... My issue is that this conjecture breaks down for lists of any length > 0, so proving it is breaks down for lists of infinite length (IMO) doesn't really demonstrate anything new.
I'm willing to accept that I'd need to study a lot more to understand why this proof is accepted as such, but I'm just poking at it and not really vested in spending the time to figure it out. I do appreciate your response though!
John Eisenmenger In what way does it break down?
is there anything bigger than taking the power set of an infinite set an infinite number of times? lol
the power set of that
fite me
Benjamin McLean: The power set of the set of all infinite sets. 😉😉😉😈
Mind-Forged Manacles The Power set of the power set of the set of all infinite sets. My set is bigger than yours
infinity^infinity^infinity^...
there not
why do you start the analogy of flying pigs and then instantly drop it before its even served its purpose or intended purpose ? why even make it at all ? its just confusing
Another way i like to think that there are bigger infinities is this
Think about an infinity that repeats 1
111111111111..
Then think about an infinity that repeats 2
222222222222..
No matter what, the 2 infinity will always be bigger
None of this makes any sense and that’s not due to your explaining it poorly. The problem is that the assumption set out to be disproven is nonsense. How can there be an amount of the numbers (a number of the numbers)? The numbers are used to count amounts but don’t themselves have an amount. We say they are infinite. But infinity isn’t an amount. When we assume the numbers have an amount we derive absurd conclusions like that there are more numbers between 0 and 1 than natural numbers. Unfortunately people don’t seem to realize how outlandish this is. If infinities were amounts then it would be true, but they aren’t.
3:29
See this is where the problem comes in
Lets replace all the dumb pokemans with 123
If the list is complete, we must be able to take a row, lets say row 1 (111...). Because we assumed the list is complete then if we cycle all the digits of row 1 we should get a new row (111.... => 222...) that exist inside the list . The row that we cycled from row 1 should exist just fine
For some examples so you dont get confused: 232323... => 121212.., 2222.... => 3333..., 123123 => 231231... You should get what I meant
Now we construct a row called _d_ by gathering all the diagonal digits
1: *1* 111111111111...
2: 1 *2* 3123123123123...
3: 12 *3* 3231113142122....
4:121 *3* 221332213....
5:1232 *4* 3233121122...
Etc
So _d_ would look something like this :12334.... _d_ can exist just fine in the list no problem, but that means we can cycle all of its digit to get a row that should also exist inside the list (12334... => 23441...) we call that row _i_ . But wait a minute isn't that the row that exist nowhere in the list?
Does that means _i_ can exist inside the list? Well lets say _i_ is the 4th row, _d_ is the 3rd row
1: *1* 111111111111...
2: 1 *2* 3123123123123...
_d_ : 12 *3* _?_ 122...
_i_ :231 _?_ 233...
5:1232 *4* 3233121122...
Why did I hides 2 digits from _d_ and _i_ ? Well because it can't be 0 or 1. Like we said be for _i_ is _d_ cycled which mean those 2 digits must be different (since theyre both 4th digit), but since the 4th digit of _d_ must be the same as the 4th row's 4th digits (which is i's 4th digits) both _d_ and _i_ can't exist. The diagonal row can't exist, the complete list can't exist therefore your argument is invalid even if you came to a valid point (that is no complete list exist).
/Taken from "CONTRA CANTOR: HOW TO COUNT THE UNCOUNTABLY INFINITE"/
You should take a look at that because it also tells you how to count them
Cool.
Is the same true for polling? Noone has ever asked all 300M people to verify asking 2k can be a true representation? I hated stats in college.
The whole point is that the complete list cannot exist; given any function from natural numbers to 10^ω (set of all infinite sequences of digits 0..9), there is some element of the latter set which the function does not cover.
How do you determine the size of an infinity? I would expect that infinities do not have sizes.
This argument is just wrong. If you have an infinite list of every row, then BY DEFINITION you will find said row somewhere on the list. You cannot construct a list that is not on the list that already contains every possible sequence. That is the logical fallacy you are making.
The other thing i would point out is to compose a "new" number, it ONLY works if there is an actual "floor" or END of the sequence. A "new" number will NEVER be created bc the list goes on and on and on forever. It just doesn't seem valid IMO to make assumptions about infinity based on how u can manipulate a finite "sample" list.
@@dom8898 Nope, it still works if the list is infinite. The number created by diagonalisation is new because it doesn't match any of the numbers on the existing infinite list.
@@MartinPoulter but the existing list though is "finite" if you pick any type of an arbitrary stopping point no matter how deep down it is, the so-called existing list represents exactly 0% of infinity [ it would relatively be as if you counted nothing in comparison to what's left to come ]
@@dom8898 Who said anything about a stopping point? There is no stopping point: the premise is that the rows of the list correspond to the natural numbers, which do not end.
@@MartinPoulter This is where it gets a little too weird for me though..... for example if you pause it at 4:04 at look at the highlighted sequence of 7 pokemon.... that is NOT a "complete" diagonal. There is no way he could ever "show us" a "complete diagonal" , it will always have to just be a "sample" which IMO is in fact a stopping point. You are only able to point out its not on the list by having a finite list above to point at to begin with. I understand the concept of what the video is trying to prove but I guess I just can't buy into it, it seems too big a leap of faith to assume it works on an infinite scale..... The other thing is whenever you pause the sequence like at 4:04, there will always be an infinite amount of sequences that can still be counted..... It seems to invalidate the "we made a new sequence that is not on the list" argument when there is simply infinite amount to go anyway, its all the same isn't it? On a side-note even IF we accept the point of the video that new numbers are being made by composing new ones along the diagonal, I guess that would possibly prove real numbers progress quicker in the count vs naturals? But is that what is being debated in the first place? progression is different from total size..... if they are both never-ending whats the difference?
Prove that if pigs can fly, 1=2.
Pigs can't fly. QED. (Anything follows from a false statement.)
Sounds like gibberish to me...
Also, if you cannot prove something is true, then it is safe to conclude that it's false-
Instead of just labeling the rows...also label the diagonalization with a number and boom...
The infinities are equal again...
This is so stupid... infinity is infinity... they cannot be less than...
Then you can put it on the list and literally do the same thing again smh
@@bruhbruh1807 there is no “putting on the list”
The diagonal is always labeled, and therefore always on the list… making the infinities equal.
@@bruhbruh1807 anyways this video is an example of potential infinities (growing infinities)… not actual infinity.
Potential infinities can be unequal… as they can be “stopped” and examined at any point in time and their finite sets compared.
An actual infinity is not comprehensible… but if it were comprehensible… the lists would have to be equal.
How is this possible... cantor's diagonalisation is so bull....how can you possibly take all the diagonals from a infinite sequence....the serial number rows are also never ending ...we are just within the numbers ....you just can't take infinity from infinity and say this shit is bigger than that....there is no scale to measure the infinity...so there is no point taking diagonals and changing them to something else ....that row itself will never end...number of elements that makes sense to our perception which yk like this infinity has this much elements till here so but this infinity has less....which is soo stupid both of them never ends...such a bogus video...ahhhh
This Math is so discrete even I'm not picking up on it.
This math is wrong, period.
There are no bigger and smaller infinities. There are only FASTER and SLOWER growing infinities.
@@DataLog Actually sir, YOU are wrong. There is no "growing" at all. The set of all real numbers is not "growing". It IS. It contains all real numbers. If you reference the set of all real numbers you are not referring to a bucket of real numbers that is having more and more real numbers added to it all the time, you are referring to ALL REAL NUMBERS THAT EXIST at once.
@@DataLog Now, given that we know that there is no "growing" involved in infinite sets, we can go on to the next point. If two sets are the same size, we would be able to create a 1 to 1 mapping of elements from one set to the next. If there is not exactly 1 element in Set A to which we can attach to exactly 1 element in Set B, they must not be the same size. If there are 5 boys and 5 girls, we can match one boy for each girl. The set of boys and girls are the same size. If we had 6 boys and 5 girls, the sets would not be the same size and we know this because we cannot create a 1 to 1 mapping from the set of boys to the set of girls; one of the girls would need to be mapped to two boys. Thus, when we show that the set of integers cannot have a 1 to 1 mapping to the set of real numbers, we are demonstrating that they are not the same size. If two sets are not the same size, one of them is larger. If two infinite sets are not the same size, then one of the infinite sets are larger. I.E. one of the infinite sets has a larger quantity of numbers.
@@blackhawk8261 Ok dude, I think you get the point. In some infinities you get to a larger and larger digit faster (and in some slower) by moving from the prevous number to the next. I know it's not the most precise way to explain things, but I assumed that detailed explanation wasn't necessary...
@@blackhawk8261 Yes, I've argued this mapping argument in another comment section. We literally wrote books about it. And in the end, the argument distills to a very simple conclusion. Both sets are infinite.
I didn't think that this requires much explanation.
It's not like we are talking about rational and irrational numbers, where you lack the description of an irrational number if you keep it in just 1 dimension, we are comparing two rational infinities.
Infinity is infinite, and the only difference you can find between these two mentioned infinities would be this "speed" (same explanation as from the previous comment due to simplicity). In which, this diagonal number will most definitely reach over the final number in the infinity that we are observing.
And precisely because there are no speeds (now I'm talking literally about the speed of growth as an incorrect concept) between infinities, this rule doesn't really prove anything.
I'm not saying that these two infinities are the same, I'm just saying that this "diagonalization" rule is a very flawed explanations and basically it relies on semantics and a limited definition of an integer in order to work.
It doesn't intuitivly, nor mathematically prove anything. I will try to link you a comment section where I've discussed this with a mathematician in a great detail. Making too much of these comments is difiicult and useless.
+ my english vocabulary is somewhat limited, so I am making big mistakes in translation. For example, in my language, we use the word that translates to "faster/slower growth" when we describe infinities of different sized steps between the integers. So this doesn't translate well. I made an effort once, I can't make it twice.
Brilliant video. That's easily the best explanation of this proof I've ever seen.
I have a problem, didnt this just prove that no such infinite combination can exist? Because no real infinite combination will ever be on that list?
@@ruce9269 This math is wrong, period.
There are no bigger and smaller infinities. There are only FASTER and SLOWER growing infinities.
Veritasium is now spreading the same misinformation.
Yes especially the example at 3:30 were you could see that the new row almost matches with the fifth row but because the fifth row was on the list it was off by a Pokémon.
@DataLog I understand your point of view but do you understand stand what they are trying to say.☝️
@@DataLog read the comment that I tried to manually tag you in☝️
Some infinities' mothers are bigger than other infinities' mothers
I’m in love with this comment
Points at Doug drunkenly “YOU THINK YOUR BETTER THAN ME?”
Those are very well-explaining videos! Thanks for doing this. I wonder why you don't have more views/subscribers yet.
Because this is completely incorrect.
Man, just found your channel. It's definitely amazing! How do you animate your videos?
Love you content and editing style!
When you look at a fraction of a real number, it's like you're zooming-in on one point of the numberline Infinitely.
When you look at a never-ending set of integers, it's like you're zooming-out to see the ever-increasing numberline.
I wish I had found your channel while I was taking my Discrete Mathematics course! Great videos
TERDLINGS: Same here, lol. 😂
Thank you sincerely. I just spent hours watching lectures from other professors on youtube and reading math forum posts to understand this, and you explained it brilliantly in less than 7 minutes. This has been a fantastic help.
thank your for clearing up the concepts, I was having a hard time understanding these infinities concept from automata theory class. :D
This video is completely incorrect.
There are no bigger and smaller infinities. There are only FASTER and SLOWER growing infinities.
Hey man, love the videos! I just have a question about the logic here. How is it ok to just alter a list like that. That list WOULD'VE existed if you didn't pull it out and alter it. The only reason it can't exist now is because of the external parameters you put on it. I feel like it's analogous to questioning where your dinner went after you just ate it. :/
I can see how it feels like we altered the list, but we actually didn't. First, we fix some arbitrary list (which must exist if we have a countably infinite set). We then use the list to define an element and ask where that element lives. This list itself is unchanged, we are just trying to figure out where one of the rows of Pokémon (or numbers) exists. The answer is that it has to be there if the list contains everything, but by the way we created this row, it also cannot be there, a contradiction.
In the dinner analogy, it's as if you said you have eaten every possible food, and then I create some weird recipe and ask you at what point in your life you ate this strange food. If the answer is you never did, then you didn't actually eat every food possible.
the problem is that it relies on LEM
it's not analogous to questioning where your dinner went after you just ate it because that is finite but this problem is dealing with infinities, that means you can take a list out and alter it because the very act of being able to alter it and create a new list means that it is possible for that list to exist thus it must be part of an infinite set
I first learned about bigger and smaller infinities when I was a junior high school kid and read George Gamow's "One, Two, Three, Infinity." I still haven't recovered from the shock.
I think it has clicked with this video. You're all basically saying because the angular number (that is infinitely long) is derived from the infinite list, for a change in all numbers (whatever the rules you use to change it, the only rule: no number matches the number it originally was), no number in that infinite list could possibly match the new number because it is derived from an angle of all the numbers (hence infinitely long). The list could contain any possible number including the one you made up... including until you form a number from the angle of those numbers. This number would be there, but a change to it would make it not possibly there even in all infinity.
Somebody please explain.
consider you assume that you can match up natural and real numbers
1 -> 0.043343...
2 -> 0.34334...
3 -> 0.4333343...
etc...
we apply diagonal argument to the real number
however why could we do this for the real numbers
eg
take the first number 1, the second number 2 the third 3, change them and end up with a new number - why is this wrong?
thank you
There's lots of videos on YT about Georg Cantor's diagonalization proof re. the cardinality of the infinite set of all rational numbers vs the infinite set of all real numbers... but, not gonna lie, I picked this one because it had Pokemon in the thumbnail instead of some old guy in front of a black board. And I actually understood it this time!
Pokemon, Charmander, Squirtle, Bulbasaur........ How old are you guys?
p.s. I like Jigglypuff
Jigglypuff isn't an option, silly!
you lost me at 5:08 “add a decimal in front”. Why can’t you use the same process with whole numbers?
Because every natural number is finite in magnitude, and so it has finitely many digits. If you were to try to apply the diagonal procedure to a sequence of all natural numbers, you get a string with infinitely many non-zero digits, and that doesn't represent any natural number. (Conversely, while real numbers are also finite in magnitude, they can have infinitely many non-zero digits after the decimal point.)
4:32 But if I got a natural number with infinite digits and added one to each digit diagonally and if it’s a 9 make it a 0 then it would also be different from every other natural number
A natural number cannot have infinite digits.
@@charlieharris4881 but why can a number have infinite decimal numbers? Both or Non?
@@LC19. That follows from how real numbers are defined. A decimal expansion 0.abcdef... is defined to mean the infinite sum a/10 + b/100 + c/1000 + ... . And an infinite sum is defined to mean the limit of the sequence of partial sums: a/10, ab/100, abc/1000, ... [where by abc etc. I mean the natural number whose decimal expansion is abc, not a*b*c]. And this sequence is a bounded, non-decreasing sequence (for example, no element of the sequence is greater than 1); so by the property of supremum the sequence has a limit. It can also be shown that every real number has a decimal expansion (but some real numbers have two different decimal expansions: 0.1000... = 0.0999...).
Finally a video that explained this so clearly!
Here's an existential crisis inducing thought: The number of characters we use in the union of all human languages is finite (English, Chinese, all natural languages, and all symbols used to make well-formed formulas in formal maths). If we take every possible string of such characters and put them into a set, it would only be countably large (and would include all computable numbers and probably lots of uncomputables like Chaitin). With the reals being uncountable, there must exist an uncountable about of numbers that individually cannot be defined with well-formed formulas. I like to call these numbers "ineffable numbers." The fact that this argument works for any uncountable set also tells us that ineffable numbers are dense within the reals, stretching across the infinite like an eldritch horror, yet seeping their Lovecraftian tentacles into every crevice of the known universe. And somehow, despite all of this, these numbers are practically invisible to the human mind.
For anyone wondering if this could be formalized: all you need to do is use a finite set A to represent an alphabet, and, for each natural n, create a map from {1,...,n} to A. Such maps are strings. Take the set of all strings of size n, and pick out the gibberish strings (there are grammars that can be used to keep the sensible strings. These are essentially operations that let one take small wff's and inductively combine them to make each of the bigger ones.), then take each sensible wff with one free variable: P(x), and keep the ones that which are satisfied by exactly one real number. These can be thought of as "definitions" of said reals. Since the set of "definitions" of size ≤ n must be finite, the set of all definitions is countable.
Also, If you are thinking you can get around this by formally defining the set of definable real numbers D, and creating its complement R\D, and saying let x be a member of R\D (which you can totally do), note that you haven't really defined an undefinable number. Yes, you can follow each of these steps, but the number you make isn't a specific number, it's a generic number, meaning it isn't truly rooted to an actual value. It's a stand-in, much like letting p be prime creates a stand-in for a prime and doesn't define a particular number like 2. I guess, in a way, these ineffable numbers can be talked about, but they cannot be constructed.
An interesting consequence of this fact is that the existence of a number implying its constructability is in direct conflict with the existence of uncountable sets. This would also put such exotic beings in conflict with Cantor's theorem and with the ZFC axioms that allow uncountable sets to exist.
I also have to wonder how many of math's "choice functions" (which are used for bizarre things like the well-ordering theorem, the Banach-Tarski Paradox, the construction of sets with undefined Lebesgue Measures, and every other reality-breaking thing mathematicians have built) would no longer work without these ineffable entities?
Feeling small yet? Well, with the subsets of the real line, continuous nowhere-differentiable functions (Check out the Baire-Category Theorem for more info on this b.s.), higher cardinal numbers in general, Conway's surreal numbers (They make the proper class of ordinals look like a joke), and inaccessible cardinals (outside the reach of ZFC), we've only just begun.
Good luck on being able to sleep ever again, lol.
Awesome video, I really like the style. It was able to explain to my mother why there are different sized infinities :) while still being mathematically accurate.
I still cannot wrap my head around comparing one thing that never ends to another thing that never ends. Even after the video, it just doesn’t make sense to me. There are an infinite amount of both, they are the same infinity. You can’t have more or less infinity ever. It just doesn’t make sense to me. That row that wasn’t on the list.. of course it was, just so long the list is infinite. Infinity holds all possibility, all lists. I don’t know.
I personally dont agree but cool vid
Wait, does this mean we can take a finite list and basically create inifnite new information from it? Or does this only work for already infinite lists? 🤔
By far the clearest video on the topic. I finally understand it.
Thank you Sir. Excellent video well explained, even to someone who has no knowledge about Pokémon, if I'm correct in assuming that is what they are?
hahaha agreed
"Paul Cohen proved that we can't prove the Continuum Hypothesis true or false."
Actually *pushes up glasses* Kurt Gödel proved that we can't prove it false (i.e. CH is consistent with ZFC).
blargoner Actually, Gödel was addressing Hilbert's Second problem. Cohen is the one that revisited Hilbert's first problem/CH.
Interestingly, Gödel did more than one thing in his career. I'd suggest looking up his book "The Consistency of the Continuum Hypothesis" (1940, Princeton University Press).
The better response to my first post would be "Actually, only if ZFC is consistent."
Thank you for giving such a nice explanation! Subbed.
I cant even pretend to understand this
As they say, redbull gives you wings1
Every "proof" that there are different sizes of infinities is predicated on immediately tossing out the definition of infinity and assuming that you could iterate through an infinite sequence in a long afternoon. You can't just whip through the list and get a new combination BECAUSE THE LIST IS INFINITE. If you could magically take forever changing Pokeymens around, you would still NEVER finish, and every combination that you came up with would already be on the list.
Let's disprove this dumb idea by considering another possibility. Imagine we invented some brand new natural numbers and added them to the set of all natural numbers. Now the list of natural numbers is bigger than the list of combinations of Pokeymen. Ha ha!! Proof that you're wrong!! OK, I can't just invent more natural numbers. And you can't find a combination that isn't on a list of every possible combination, either.
But, I feel like you need more, so here it is. Imagine the list is not infinitely long, it's only two digits and there are only two Pokeymen. So, there are four possible combinations: [1,1 1,2 2,1 2,2]. Now, find another combination that isn't already on the list. You can't. The list already holds EVERY POSSIBLE COMBINATION. But, what if you spent an infinite amount of time scrambling those digits around. EVENTUALLY you would come up with a new combination, right? No, you wouldn't. Yet, in the other example, we started with an infinite list of EVERY POSSIBLE COMBINATION, yet, somehow, magically, we come up with a new combination. Sleight of hand. The list is far too long to see the whole thing, so the rube will imagine that EVENTUALLY there is a new possible combination to be found. But, there simply isn't. You got to make up the rules and assumptions to your own proof, and yet you almost immediately violate them. But, there's this process . . . Yeah, your process is a joke and it won't work.
Like a lame magic trick, this fakie [tired of calling it a "proof"] is based on misdirection. Once the guy in the cheap suit gets you nodding about how this method would lead to a NEW combination, you are stuck. But it won't and it can't and it really has nothing to do with infinity, nor does it have to do with forever. The faker asks you to assume that every combination is taken up, then tells you that there's a new combination. There isn't, is a lie, it's already taken up, there are no new ones to be made, you can't do it, your logic sucks, you have proposed your own demise, no, no, no, no. There is exactly one size of infinity.
You can iterate all the natural numbers in and hour. First count 1 then after 30 minutes you count 2 after 15 minutes you count 3. If you keep halving the time to count the next number. You can count all of then in 1 hour.
my brain just exploded and is now leaking out of my ears
dude you should see a doctor
Why not just use base 3. 0, 1 and 2 are the symbols.
Hey would this work to prove this proof of different sized infinities false or am I an idiot
0.10000..
0.20000..
0.30000..
...
0.01000..
0.11000..
Okay. That covers all numbers with finitely many non-zero digits after the decimal point. All such numbers are rational, and that there are countably many rational numbers is not a new result. At what position does 1/3, or √2/2, or pi-3 appear?
i like your idea. however if you read the numbers backward than we can use the same proof to show that there are more integers than integers. for example lets assume we can give every integers an integers hear is an attempt at a mapping however this proof works for any arraignment
148230000000...
574895738000000...
57348920489475839000000...
384934000000...
50493249000000...
00000000000001000000...
1010101010...
...
however i can prove that there is a integer we missed by taking each number than taking that number + 1 mod 10
so in this case the missing number would start
2840410...
can some one tell me the flaw in this reasoning
@@MikeRosoftJH if you read the numbers backward than we can use the same proof to show that there are more integers than integers. for example lets assume we can give every integers an integers hear is an attempt at a mapping however this proof works for any arraignment
148230000000...
574895738000000...
57348920489475839000000...
384934000000...
50493249000000...
00000000000001000000...
1010101010...
...
however i can prove that there is a integer we missed by taking each number than taking that number + 1 mod 10
so in this case the missing number would start
2840410...
can some one tell me the flaw in this reasoning
@@ivanthomas8503 There's no such natural number as "148230000000...", or the like. 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.
@@MikeRosoftJH no you read it backward so it becomes ...000000032841 or just 32841
The videos on your channel are really impressive. You're creating high quality content without a large number of viewers, but I suspect that will change quickly. Great stuff, keep up the great work!
This video is completely incorrect.
There are no bigger and smaller infinities. There are only FASTER and SLOWER growing infinities.
This is not your best video. The "proof-by-contradiction" piece with the pig probably should be replaced with something betterer - I found it pretty clunky: "1=2 therefore pigs don't fly"
this doesnt make sense to me, couldn't you theoretically, ' diagonalize ' the natural numbers
at a big enough natural number you could start diagonalizing the number seemingly infinitely
You can treat each Pokemon as an integer. Charmander is 0, squirtle is 1 and bulbasaur is 3. Then list them by counting. In the respective (number of Pokemon)^n fashion.
Im here from a graduate class in computer science; Theory of Computation. The problem was to prove why the infinite sequence over {0,1} is uncountable.
Undefined Behavior
What if I told you there are just as many rows of Pokemon as there are natural number how much would maths change??
(assuming I disprove this prove of course) and prove that the infinity are in fact equal using your same bijection rule???
2:41 evil ben shapiro
I think of infinity as a numerical representation of a universe. Some universes can be bigger than others with more space inside of them even though both are expanding.
WHere did you fucking go?
OH MY GOD, I GET ITTTTTTT!!!!!!! THANK YOU, THANK YOU!!!!!!!!!!!!!
This video is completely incorrect.
There are no bigger and smaller infinities. There are only FASTER and SLOWER growing infinities.
discrete Red Bull plug noted
¿Será posible, verificar la correspondencia biunívoca, existente entre los números reales y (0, 1) de (R), empleando el método del Argumento de la diagonal de Cantor? {Siendo, aún más significativo, poder verificarla entre: (0, 1) de (R) y (0, 1) de (R)}
Del mismo modo, en que Cantor no detalla (FC(x)) - que en principio definiría como una función biyectiva entre los conjuntos de Lista(C) {f: (N?R)}, misma que, posteriormente declarara inexistente -; no detallare (FG(x)) - que en principio, definiría una función biyectiva entre los conjuntos de Lista(R) {f: (R?(0, 1) de R)}-. Y, si os pones muy quisquillosos, podemos recurrir a {f: ((0, 1) de R?(0, 1) de R)}
Siendo (A: el conjunto de los números reales) y (B: el conjunto de los números reales entre (0, 1)) equipotentes, necesariamente deberá existir una correspondencia biunívoca entre sus elementos.
Bien. Confirmémoslo, empleando exclusivamente el método del argumento de la diagonal de Cantor (ADC). Para ello, construimos una Lista(R), mediante (FG(x)), igualando (1 a 1) los números reales a los números reales entre (0, 1). Seguidamente, empleemos la (PDC()) - usada por Cantor para construir su número real x(C) entre (0, 1) del Codominio -, para construir el nuestro. Mismo que, obviamente, no estará contenido en Lista(R).
Conclusión: entonces. Con un grado de rigurosidad similar, al empleado por Cantor en su método, demostramos que: empleando ADC, no es posible verificar una relación sobreyectiva - y por consiguiente biyectiva -, en Lista(R). En consecuencia, según ADC: los conjuntos de Lista(R), no deberían considerarse equipotentes - o sea: ((R)?˜(0, 1) de (R)) -. Demostrando así, lo contingente de este método, y consecuentemente, una fuente de inconsistencias de la teoría de conjuntos.
Nota: ¿acaso demostré la absurdidad del método del argumento diagonal de Cantor? Salvo que: ¿propongáis revisar el teorema de Cantor-Schroder-Bernstein - o sea, los criterios para reconocer una biyección entre conjuntos -, y/o las demostraciones de equipotencia entre (0, 1) de (R) y (R)? No, mejor será, no seguir perdiendo el tiempo leyendo este compendio de tonterías, ¿verdad?
Entonces, ¿el argumento de la diagonal de Cantor, es fuente de inconsistencias para la teoría de conjuntos?
Entonces: un obvio resultado inevitable - la diagonal alterada del Codominio, no-pertenece al Codominio -, es prueba suficiente, de algo más, que de sí mismo - es decir: tal resultado, es independiente de la cardinalidad del conjunto del Dominio -?
PD: dado que, al parecer, no he planteado esta obviedad de forma suficientemente inteligible, la repetiré de forma sutilmente más burda: a excepción de alguna inconducente convención matemática, ¿qué lista de números - construida en forma de un arreglo bidimensional cuadrado de dígitos -, puede contener, al número construido a partir de los dígitos alterados de su diagonal?
Obviamente, la anterior pseudo-refutación, podrá ser constituida entre cualesquiera conjuntos numéricos infinitos - equipotentes o cuya potencia del dominio sea superior a la del codominio (para evitar suspicacias de devotos Cantorianos, emplear el intervalo unidad en ambos conjuntos de la función, apelando, a la equipotencia de un conjunto con un subconjunto propio) -, siempre y cuando, las propiedades del conjunto numérico del codominio, permitan expresiones decimales infinitas - distinta de cero - no periódicas.
It was this video that the concept of Cantor's Diagonalization finally clicked for me. Thank you so much!
I was trying to remember how the infinite hotel thing worked and this helped thanks
great video!
This was great it gave me true joy I think the love for math that school slowly managed to kinda kill in me is finding it's way again
Before now, I was content with diagonalization proving the uncountability of the real numbers. But I have thought of an example that is troubling me. Suppose you have an infinite string of zeros and ones. By diagonalization, the space of all possible such strings is uncountably infinite.
But why can't I let each string represent a binary number, where the nth digit in the string represents 2^n? If this were valid, then I could make a bijection between each string and the natural numbers. Can somebody please explain?
You can't do that, because the decimal (or base-2) representation of any natural number is finite. (In fact, this is how a finite set is defined in set theory: a set is finite, if its number of elements is equal to some natural number). If you apply diagonalization to base-2 representations of natural numbers, you get a string with infinitely many non-zero digits; this doesn't represent any natural number. But you can use this to prove that you can't map natural numbers one-to-one with the set of all functions from natural numbers to the set {0,1}. (These functions naturally map to subsets of natural numbers. It can also be proven that real numbers, and subsets of natural numbers, have the same cardinality.)
If somebody could clarify this for me, it'd help me understand this video way better: Why is it at 3:16 ,when creating a new row of pokemon , that you need to change the each pokemon? English is not my native language so please forgive me for my horrible grammar.
You are constructing a row which is different from all the infinitely many rows already in the list. The row differs from the 1st row at position 1, from 2nd row at position 2, from 3rd row at position 3, from 4th row at position 4, and so on.
But is math infinite or is there a limit of theorems we can proof?
1. 0/1
2. 1/1
3. 0/2
4. 2/1
5. 1/2
6. 0/3
And so on.
Could you not use the diagonalisation method to prove that there are an uncountable number of natural numbers by writing out all the natural numbers in binary, then taking the diagonal through them and switching 1s and 0s?
No, because every natural number is finite. Your diagonal number would have infinitely many non-zero digits (in fact: if you were to list all natural numbers in order, then *all* digits of the diagonal number would have been 1), which doesn't represent any natural number.
really awesome videos
i liked the way u explain
ur analogies,animations and sense of humour are superb
Natural numbers does not include zero!
your explanations are just amazing. Please make more videos.
Thank you, very nice video :)
Once you create a new pattern from a "complete" list then there would also be a new natural number to "count" or index the new possible pattern. The only reason this appears to be a contradiction is because you are supposing that the natural numbers can be used as a container or index. This initial assumption already places a limit on an infinite potential of natural numbers.
I do not have a problem with the theorem except for when it is used to suggest that the infinity of 0-1 is larger than the infinity of natural numbers. At least equal to, I can accept.
no, you are iterating across the list for infinity and are never able to add a new natural number to index the new pattern. Because you are iterating for infinity, when are you able to insert a new number? You're thinking about infinity as if it's finite, as if you can add a new number when you get to the end except you can't, infinity cannot grow, it is complete by definition.
What i heard was “BRUH”
i didn't get .
and not gonna try pfffff
This video is amazing. Thank you
omega+1
Ace Attorney reference anyone?
Wonderful,awesone .
I like how he says Bulbasaur
GREAT explanation!!! thanks!
6:56; we assumed that the number of rows matches the number of columns. And this is what a square grid is.
If we take any finite countable list, and fill a square grid; then alter the diagonal .... we get a new sorting that cannot be in the square grid .... which means the grid was not a complete representation of all the possible combinations of the elements within it. But we assumed the list was complete.
For example, binary form, of length 1; gives us a complete list:
{
0
1
}
what does our square grid look like?
each element of the set is of length 1, so should it be a 1x1?
the are only 2 elements in the set, maybe a 2x2? but we have no elements of length 2 ...
maybe we alter the form of each element? but then thats not assumed by the process given to us. The length of each element is not changed ... so to be fair to the proofing method, lets assume a 1x1 grid. Lets fill it up.
Grid (1x1)
{
[0]
}
Now lets assume our square grid contains all the items of our complete list .... because we are told to assume it.
Take the diagonal, and we get 0, change it to 1 because thats how we work the process.
Show that the new item is not contained in the square grid ... well, its not in the grid.
Since we assumed that the complete, finite list was contained by the grid ... Conclude that the list itself is incomplete?
---------------------------------
Maybe we just need to grow our grid so that its gets to an infinite size? Well, lets see what an element length of 2 gets us:
binary form, of length 2; gives us a complete list:
{
00
01
10
11
}
what does our square grid look like? Oh yeah, same as the size of an element; 2x2. Lets fill it up.
Grid (2x2)
{
[ 0 0 ]
[ 1 0 ]
}
Now lets assume our square grid contains all the items of our complete list .... because we are told to assume it.
Take the diagonal, and we get 00, change it to 11 because thats how we work the process.
Show that the new item is not contained in the square grid ... well, its not in the grid.
Since we assumed that the complete, finite list was contained by the grid ... Conclude that the list itself is incomplete?
...................
Well it did not work for the smallest possible setup; and it did not work for next largest one either. It seems that our grid holds the same number of items from the list, that is equal in size to the length of an element. For each growth in element size, the list is 2^n items long; but the grid can only hold n items total.
Hmm, a 10x10 square grid only has enough room to hold 10 items; but the binary list is 2^10 items total.
As our grid expands towards infinity; the number of items that the grid cannot hold is: 2^n -n.
Is it fair to say the list is incomplete; because we assume the grid can hold it? This all has nothing to do with the value of any item in the list, it is purely a property of form alone.
"we assumed that the number of rows matches the number of columns."
Yep. And that's because the decimal places of a real number are always in one-to-one correspondence with the natural numbers (giving us natural-number-many columns), and we also assumed the real numbers are countable, meaning they can be placed in one-to-one correspondence with the natural numbers (giving us natural-number-many rows).
If the set of real numbers were countable, it absolutely could fit into a square grid.
@@MuffinsAPlenty We cant even fit a finite list of fractions into a square grid.
My first example was all the ways we could represent a binary decimal expansion: 0/2 and 1/2. Two representations cannot fit into a one element tool.
My second attempt example was all the ways we could represent a binary decimal expansion: 0/4, 1/4, 2/4, 3/4. Four representations cannot fit into a two element tool.
We could do the same thing for the binary decimal representation of 8ths:
0/8 = .000
1/8 = .001
2/8 = .010
3/8 = .011
4/8 = .100
5/8 = .101
6/8 = .110
7/8 = .111
2^3 elements in the list; and only 3 of them fit into the grid
When we get to the 1/2^n example, our list is composed of all the ways we could represent the binary decimal expansion: 0/n, 1/n, 2/n, ... , (n-1)/n. And 2^n representations cannot fit into an n element tool.
These finite lists of fractions are said to be countable, and so they should absolutely fit into a square grid - but they obviously do not. Because?
As the limit of n -> inf, the list does not get any better at fitting into the square grid. And we havent even tried to account for the infinite decimal fractions.
@@anthonym2499 "We cant even fit a finite list of fractions into a square grid."
Yep. And similarly, you can't fit all real numbers into a square grid, which is what Cantor's Diagonal Argument shows. If the set of real numbers were countable, you would be able to fit them within a square grid. But you can't. So they're not countable.
@@MuffinsAPlenty If the set of rational numbers were countable, you would be able to fit them within a square grid.
But, the set of rational numbers is countable ... so you should be able to fit them within a square grid.
The proof isnt demonstrating the countability of the set. It is only demonstrating the property of the grid itself and not the contents within it.
@@anthonym2499 "But, the set of rational numbers is countable ... so you should be able to fit them within a square grid."
And you can.