>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.
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.
I'll bite. You can make a program the maps from integers (expressed in binary) to the real interval between 0 to 1. No matter what bit string the program outputs, it is meant to be (and thus interpreted as) the binary digits of the number that come after the decimal point. Thus there is no need for a proof of convergence, by the very nature of the representation it is impossible for the machine to output something that isn't a number somewhere on the interval from 0-1. All that matters then is proving it won't halt. But I can easily make sure it never halts by having a program that sits on top waiting for it to halt, and then if it does, restarts the program. So I can check the mapping from the integers to the interval, and by extension from the integers to the real number line.
Yes, you can write your program. And yes, you can guarantee that it will not halt. And yes, you can guarantee that its output is different than any program it managed to emulate.
But what happens when it tries to emulate itself? Well, if it produced any output, it would immediately produce a different output. The way out of paradox is that it returns nothing at all.
The program that sits on top now has a choice. If it decides to let the program continue to grind away, it NEVER produces that next digit. If it has any kind of logic that will give up after long enough, it WILL give up and move on.
Either way your program will fail to produce an output that is different from its own output. And therefore diagonalization fails.
>But what happens when it tries to emulate itself? Well, if it produced any output, it would immediately produce a different output. The way out of paradox is that it returns nothing at all.
Why immediately. It only has to differ by one bit somewhere along the infinite chain right? Why waste that perfectly good output when it can just as well output some of the emulation before interrupting it?
All will fall prey to the fact that the program must produce the same output as its emulation of itself. It can never get around this fact. Therefore it either produces a finite amount of input and then stops waiting for its emulated self, or it never gets around to producing something different than itself.
Either way it fails to diagonalize itself. The exact cause will vary. The eventual result will not.
Classical mathematics gets around this by waving hands over constructions with impossible procedures based on undiscoverable truths. By assumption these procedures can never be the input to themselves. The result is an insane number of possible outputs about whose tenuous existence we can say little but our claim that they exist.
No argument of pure logic alone can demonstrate any form of existence for these impossibilities, you must make additional unprovable philosophical assumptions about the nature of truth and existence.
I know that these techniques and results seem natural to you. But that is a consequence of your indoctrination into a system of thought which glosses over these complications instead of exploring them.
I am just guessing here, but I think the problem is that even if you redefine a real number as "that which can be written by a program", you cannot write a program that enumerates all such numbers.
That's kinda because different real numbers require programs of different complexity (for any specific complexity, e.g. the number of bytes, there is only a finite number of programs with that complexity), so listing all the real numbers would require infinite complexity, i.e. not a (finite) program.
So there is a countable set of integer, and a set of reals (by the new definition) which is countable (by the usual definition) but cannot be enumerated, so it is technically "uncountable" (by the new definition).
The trick is that if you are changing definitions, you may accidentally also change the definition of "countable". Because it is defined as "that which can be mapped to integers", but the problem is, which mappings are considered legal and which are not. In the world of "only things written by programs exist", only mappings which can be generated by programs exist; which is not the same as all possible mappings, so a few previously countable things now become "uncountable".
You can write a program that will always generate a real number, but you can't write a program that will generate all of the reals, or even any single real that's irrational (like pi). And the vast, vast majority of reals are irrational.
The best you can do is a program that generates a crude approximation to an irrational, because you'd need an infinite number of states to write the entire number and every physical computer has a finite number of states.
If your program that sits on top restarts the underlying program, then it will generate a repeating binary sequence. And that's a rational number.
>The best you can do is a program that generates a crude approximation to an irrational, because you'd need an infinite number of states to write the entire number and every physical computer has a finite number of states.
I can provide you with the requested infinite amount of state, I merely require infinite amounts of time.
>If your program that sits on top restarts the underlying program, then it will generate a repeating binary sequence. And that's a rational number.
And that would be stupid and obviously wrong. I should have clarified that the program sitting on top interrupting stuff is obviously changing something before restarting. Could be anything. Maybe flips some stateful starting info, maybe swaps to a different program, maybe starts xoring the output with something. Could be anything
It doesn't matter what the program sitting on top changes, it does so in a deterministic way. And therefore the emulation of the program changes the same thing, in the same way. Which means that the emulation cannot figure out the next bit of its output faster than the actual program.
And therefore the program either never decides to output anything which would have diagonalized itself, or it gets stuck after a finite time by a liar's paradox attempting to figure out the next bit of it would put out so that it can put something different out instead. Either way diagonalization of itself cannot succeed.
The reasoning here is very similar to Turing's proof of the Halting Problem - no program exists that is able to take a program + input and reliably determine whether that program will halt. And the reason is that you set up a program which would have to set up a liar's paradox about itself fed input that translates to itself fed input about itself recursively. The only logically consistent result is that this program both cannot halt, and cannot figure out that it doesn't halt.
Just 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...
Also (this is a very very minor detail) it is best to inly consider numbers without the digit eight. Otherwise you might end up with 0.99999999 which is one.
This is the tiniest of details but important for precision.
I 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.
100000... 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.
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.
If 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.
Infinity 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”.
That's incorrect. The assumption was that there was a 1:1 (injective) mapping, and the proof was that it (regardless of it's exact value) wasn't onto (surjective) and so isn't bijective.
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.
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.