Some Infinities ARE Bigger Than Other Infinities (Diagonalization)
Вставка
- Опубліковано 24 жов 2016
- With so many infinities being the same, just which infinities are bigger, and how can we prove it?
Created by: Cory Chang
Produced by: Vivian Liu
Script Editors: Justin Chen, Brandon Chen, Elaine Chang, Zachary Greenberg
Countable Infinity: • How to Compare Infinities
Diagonalization: en.wikipedia.org/wiki/Cantor%...
Continuum Hypothesis: en.wikipedia.org/wiki/Continu...
Power Set: en.wikipedia.org/wiki/Power_set
---
Twitter: / ubehavior - Наука та технологія
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 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.
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.
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 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.
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☝️
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!
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.
i've been looking for an explanation for that for days, this on is BY FAR the best
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?”
By far the clearest video on the topic. I finally understand it.
It was this video that the concept of Cantor's Diagonalization finally clicked for me. Thank you so much!
this is the best video i've eve seen for a mathematical proof! well done with the animation and simple explaination
Finally a video that explained this so clearly!
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.
Thank you for giving such a nice explanation! Subbed.
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!
really awesome videos
i liked the way u explain
ur analogies,animations and sense of humour are superb
I wish I had found your channel while I was taking my Discrete Mathematics course! Great videos
TERDLINGS: Same here, 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.
Amazing video man! Thank you
your explanations are just amazing. Please make more videos.
a really great video
wish you infinite number of views :)
Excellent video explaining Carton’s diagolization.
This video is amazing. Thank you
GREAT explanation!!! thanks!
Finally clear!! Thank you!
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
Wonderful,awesone .
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?
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.
Excellent video
This is excellent. Thanks!
Yeah
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? 🤔
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
Keep it up bro you are "awesome"
Thank you, very nice video :)
I was trying to remember how the infinite hotel thing worked and this helped thanks
Thank you, I watched a similar video before but there were no pokemon so i didnt get it. Pokemon really helped me underestand.
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
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
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.
Impressive vids.
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.
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
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.
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.)
thanks
Pokemons really helped me understand Diagonalization. XD
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???
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.
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.
But is math infinite or is there a limit of theorems we can proof?
mind blown
Number of Marth clones is uncountably infinite
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.
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.
¿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.
As they say, redbull gives you wings1
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...).
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.
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.
my brain just exploded and is now leaking out of my ears
dude you should see a doctor
discrete Red Bull plug noted
Pokemon, Charmander, Squirtle, Bulbasaur........ How old are you guys?
p.s. I like Jigglypuff
Jigglypuff isn't an option, silly!
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.
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.)
"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."
Why not just use base 3. 0, 1 and 2 are the symbols.
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?
I like how he says Bulbasaur
The finite curve
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.
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 cant even pretend to understand this
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.
How do you determine the size of an infinity? I would expect that infinities do not have sizes.
1. 0/1
2. 1/1
3. 0/2
4. 2/1
5. 1/2
6. 0/3
And so on.
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
2:41 evil ben shapiro
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^...
"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.
Natural numbers does not include zero!
What i heard was “BRUH”
I personally dont agree but cool vid
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
i didn't get .
and not gonna try pfffff
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
omega+1
This is just a matter of perspective; the contradiction is illusory. The problem is resolved by recognizing that the meta-list (the larger of two infinities which the contradiction proves) would not compete with a list of all possible Pokemon combinations because it is actually a list of all possible Pokemon-in-certain-positions. So, if the first domain is the theory, the second domain is the application of the theory. We only think they are the same object because they look very similar and would produce only rows containing Pokemon. Metaphorically, one would not think that a water molecule contradicts the underlying chemical theory of the periodic table of elements simply because it is a compound.
Cantor was wrong. Diagnolization simply proves that infinity itself is uncountable. You can convert ALL conceivable values between 0 and 1 into a discreet natural number by simply flipping it around the decimal point. IE .1 is 1, .123 is 321, .09878901 is 10987890, there is no other value between 1 and 0 that will result in the same natural number when put through the same operation and the converse is also true. Both extend infinitely. Cantor is trying to prove that ♾ < (♾ +1 ), which while definitionally “true,” is not actually true because infinity already encompasses everything there is, so it can not be added to.
Try converting the decimal form of 1/3 to a natural number using your function then.
Lmao this video was so fun to watch
I never like Proofs that are based on assumptions
The proof is not based on an assumption (other than basic axioms). All we're doing is saying that IF some proposition A is true, then some set of mutually exclusive propositions must also be true: for instance, you might be able to show that if A is true, then another proposition B is both true and false. This is a logical inconsistency and is valid proof that A is not true. We are not assuming anything at all.
You can remove the initial assumption, in which case the proof goes like this: Let f be any function whatsoever from natural numbers to real numbers. It is possible to construct such a real number x which is not equal to any f(0), f(1), f(2), ... Therefore, no function from natural numbers to real numbers can cover all real numbers; in other words, there are strictly more real numbers than natural numbers.
there not
I think there's a mistake in this proof: you aren't comparing the diagonal to each number in the list. Instead, you are comparing each number with its own modification, which by definition will be different.
But somewhere down on the list, there is a row that is the same as the earlier one except with the modification... This is tiring to think about, so it's hard for me to get to the end of my reasoning, here.
But so far, I don't find any explanations of Cantor's Diagonal, that I've seen, to be convincing.
It's like there's a logical step that nobody notices that they are skipping, here. But maybe i'm the.one who is not making the connection.
The diagonalised number is different from *every* number on the list, so it's not on the list, so the list isn't complete. If you think the diagonalised number is somewhere on the list, maybe you're not getting how it's constructed.
@@MartinPoulter Possibly. There is an issue though: when forming non-infinite lists of this kind, the diagonal does not modify every number in the list, because the list has exponentially more rows than it has columns.
In an infinite list, the number of columns is inf, whereas the number of rows is inf^inf
If the diagonal modification does not touch every number on the list, then... well, I'm not experienced enough in Math to know what that entails, but it seems like there is plenty of room for the new number to be there. It has every combination of every digit by definition.
I suspect there is a logical step that people are jumping over/forgetting in making this proof.
@@MartinPoulter One of the implications is that the longer the diagonal gets, the more numbers/rows there will be which are beyond the diagonal.
Hence, all the diagonal argument demonstrates is that the diagonal will never succeed at creating a unique number that is not in the list. That's because, the way the list is constructed, the list outpaces the diagonal ad-infinitum.
@@Yamikaiba123 I don't know where you get this idea the list has more rows than columns; the rows correspond to the integers 1,2,3,4.... and so on and the columns are just places after the decimal point: tenths, hundredths, thousandths and so on if we are using base 10. It should be clear that these sets are the same size.
Diagonalisation *always* creates a new number that is not on the list. The number of digits of the new number maps perfectly onto the number of rows of the list. Put another way, corresponding to every row of the list (row 1, row 2, row 3, and so on) there is a digit in the diagonal number.
@@MartinPoulter That's demonstrably false. Sit down at a sheet of paper and try writing a list of binary values. I'll write the 2-digit list:
00
10
01
11
The number of rows = (number of possible integers)^(number of digits)
Maybe I'm getting this right, haha. Sometimes I forget which is the base and which is the exponent.
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
putting two infinite integer sets into 1-1 correspondence says absolutely nothing about there relative cardinality; it just means when it comes to infinite sets any set of labels will do.............
if you accept diagonalisation as a valid argument (many don't), the conclusion that a non-countable set has greater cardinality does not follow from the premises
By definition, the 1-1 correspondence establishes that the sets are of the same size. That's what the size of a set *means*. The alleged "many" people who don't accept the simple deductive argument of diagonalisation must not have any maths qualifications: this is well-established, proven stuff.