5 ms·
Responding as a constructivist would. Let's define real numbers in a concrete way where they certainly exist, such as by equivalence classes of Cauchy sequence
by btilly 4y ago
Responding 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.
- nemo1618 4y agoThis kinda blew my mind, thanks!
- btilly 4y agoYou're welcome. :-)
- IIAOPSW 4y agoI'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.
- Viliam1234 4y agoI 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".
- yababa_y 4y ago… in python?
- dreamcompiler 4y agoYou 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.