|
|
|
|
|
|
by mbid
3358 days ago
|
|
|
Honestly, the result hinted at in the wikipedia article caught me by surprise as well: There are some flavors of constructive mathematics (notably CZF), that are still consistent if you also add the statement "There is a subset A of the natural numbers such that there is a surjection from A onto the real numbers". Note that this does not imply that you can prove this in CZF, it only means that you cannot disprove it. See http://www1.maths.leeds.ac.uk/~rathjen/acend.pdf prop. 8.2 if you're interested. Wikipedia says that the Cantor argument shows "no more" than that there is no bijection between the natural numbers and the real numbers. As far as I can tell, it also proves that there is no surjection from the natural numbers onto the reals in every system of constructive mathematics I know of, so I think this is slightly misleading. What do you mean by "distinguishable"? In constructivism, a set A such that x = y or x != y for all x, y in A is sometimes called decidable. And yes, it is indeed not true that the real numbers are decidable. This would imply that there is an algorithm that decides whether two infinite sequences of ones and zeroes will differ at some point or agree indefinitely, which is pretty much equivalent to solving the halting problem.
On the other hand, the natural numbers, integers, rational numbers and every finite algebraic extension of the rational numbers (for example Q[i], "rational imaginary numbers") is decidable. |
|
|
Furthermore if we limit all mathematics to things that can in principle be done on a Turing machine, then this statement is trivially true because all possible Turing machines is a countable set.
Moving from Turing machines to a Turing-complete programming language, we could define a real number as an equivalence class of functions from positive integers to fractions such that for each function |f(n) - f(m)| <= 1/n + 1/m, and two such functions are equivalent if |f(n) - g(n)| <= 2/n for all positive n.
The question of whether a given function is actually a real number is in general undecidable. The question of whether two functions represent the same real number is also undecidable. However it is easy to create a set of functions that will definitely include all real numbers under this definition (and a few things that are not), but some of those real numbers will be included multiple times.
And the really important point about this is that suddenly "uncountable" doesn't mean "more". It just means that there is an undecidable question or three creating complexity in the way of generating the mapping.