8 ms·
>If you have two infinite sets, then isn’t it always possible to map an element from one to a new element in the other, because there’s an unlimited number of e
by IIAOPSW 4y ago
>If you have two infinite sets, then isn’t it always possible to map an element from one to a new element in the other, because there’s an unlimited number of elements to pick from?
No. Consider the set of integers vs the set of real numbers. Suppose I have a 1 to 1 mapping from integers to reals. Lets pick an example of such a mapping to demonstrate.
1 - .152345...
2 - .897454...
3 - .908345...
...
Now I can always construct a new real number by going down the diag, taking the first digit of the first number, second digit of the second, etc, and selecting a different number than that (say, by doing +1 mod 10). In the example this new number would be .209... By construction, this number doesn't match any real number already on the list.
Therefore, after mapping all the integers to real numbers, there's still left over real numbers. Hence the reals are a larger infinity than the ints.
- xchkr1337 4y agoJust picking digits from the diagonal might not work, you have to make sure the digits of the new number aren't equal to the ones on the diagonal, one way is to add 1 mod 10, in the case you showed it would result with 0.209...
- cjohnson318 4y agoI always explain this with binary digits. You can always construct a new one from the diagonal by flipping each bit. I think the smaller domain {0,1} instead of {0,1,2,3,4,5,6,7,8,9} keeps people from getting distracted and trying to find a loophole.
- hgsgm 4y agoBinary is the only base where that proof does not work well easily, because 100000... = 011111... in a metric system.
- IIAOPSW 4y ago100000... is only equal to 011111... if your digits roll over, but if your digits roll over then you have a p-adic number system (specifically a 2-adic system), and the exact same argument would hold equally well for the 10-adic applied to 10000..... = 99999..... You argument isn't dependent on being binary or not. Only that the numbers roll over.
- Dylan16807 4y agoIn bases higher than 2, you can avoid the issue entirely by saying that some digits get +1 and other digits get -1. If the generated number only has digits 1-8, then 0000... vs 9999... is obviously not a problem.
- deleted 4y ago[deleted]
- sorokod 4y agoThe "therefore" is not quite right. You have shown that that the original assumption leads to a contradiction and so doesn't hold.
- btilly 4y agoResponding as a constructivist would. Let's define real numbers in a concrete way where they certainly exist, such as by equivalence classes of Cauchy sequences. Where a Cauchy sequence is a computer program that takes in a natural number, and returns a rational, complete with a proof that the rationals that it spits out will converge at a calculable rate. Your mapping can now be constructed from an enumeration of such programs. (A single real may appear many times because many programs are equivalent. That's just a detail.) For each program we can put in a large enough number that we get the decimal place down to one of two. (The old 0.9999.... = 0 problem is a small complication here.) And then we pop out a clearly different digit. Given the mapping, this program can be easily written. And so we can produce our number which starts off in your example as the sequence .6, .64, .643, ... . So far, so good. But what goes wrong? Well we have a program that we assert produces a real. It certainly seems to do so. But proving that it represents a real requires proving that the program will always give the next digit. That requires proving that it works as advertised. That requires proving that the logic we used to make all of our decisions is consistent. But by Gödel's Incompleteness Theorem, we can only prove that if our logic is INCONSISTENT. And therefore our nice program doesn't have a proof that when ask for the n'th rational that it will ever return anything. And therefore it doesn't represent a real number! This is why Cantor's diagonalization argument fails in constructivism. The impossibility of making a one-to-one map between naturals and reals becomes a statement about the self-referential logic embedded in the definition of real numbers, and NOT a proof that there exist an uncountable number of real numbers that we can never write down any meaningful description of! Even if you don't subscribe to constructivism, I think it is important to recognize that the confident statements we make about infinity in classical mathematics rest on unprovable philosophical assumptions of a potentially dubious nature.
- jpcfl 4y agoOkay, I think that jogged my memory. So, the idea is that no matter what mathematical mapping you create from Natural -> Real, it will always be possible to find a Real number that is not in that mapping. Therefore, |Real| > |Natural|. Still, it feels wrong. If my "function" is an immortal monkey I've trained to grab one item from an unlimited Natural number bucket, and another from an unlimited Real number bucket, and put them together, that process could go on ad infinitum. It's hard to imagine one bucket as been larger than the other, when both are endless.
- hobs 4y agoIf you had a bucket with 10 million options in one and 100m in another, you'd take 10 million picks before you realized via a 1-1 picking that one was smaller than the other. Infinities obviously dont collapse and "end", but seeing infinities "grow" faster than others makes a lot of sense to me.
- vishnugupta 4y agoInfinity as a concept is not easy to reason about because it’s not something we ever encounter in our daily lives. It leads to interesting paradoxes such as Hilbert Hotel. Coming to Natural and Real numbers, one way I’d like to think is that real numbers are more “dense” (or continuous) compare to integers which are discrete. A cup full of sugar and cup full of water could be of equal volume but you can count sugar grains and not water because water is not grainy and is “continuous”.
- ouid 4y agothis argument is very slightly wrong, because I could pick 1.0000... for all of my numbers, and then choose the diagonal .99999...
- kgwgk 4y agoIf the “map” goes to 1.0 only you don’t need the argument to deduce that not every real is represented.