# Can countability coexist with infinity?

This question concerns the countability of the real numbers. First I will show how I count the numbers between 0 and 1 on the real line. It is done by reversing digits behind the coma, so that e.g. 0,761 maps to 167. Obviously this is 1 to 1 mapping, but there are infinite number of those unique mappings depending on the chosen reasonable radix. In decimal number system I could count numbers like this:

## $0 , 0.1 , 0.2 , 0.3 ... 0.9 , \\ 0.01 , 0.11 , 0.21 , 0.31 , ... , 0.91 , \\ 0.02 , 0.12 , 0.22 , 0.32 , ... , 0.92 , \\ 0.03 , 0.13 , 0.23 , 0.33 , \dots , 0.93 , \\ \vdots \\ 0.09 , 0.19 , 0.29 , 0.39 , \dots , 0.99 , \\ 0.001 , 0.101 , 0.201 , 0.301 , \dots , 0.901 , \\ \vdots \\ 0.002 , \dots , 0.902, \\ \vdots \\ 0.092, \dots , 0.992 , \\ 0.003 , \dots , 0.903 , \\ \vdots \\ 0.004, \dots , 0,904,\\ \vdots \\ \infty \\$

Now, given that I can "succeed" to count to infinity, I would also count all irrational numbers. There is no reason to haste. But then all irrational numbers are "somewhere" in the infinity. So either counting to infinity allows me to write irrational numbers backwards, or infinity and countability can not coexist. Which one is true ? How does your solution compare to rational numbers ?

-
No, your "counting" of the numbers in $[0,1]$ is missing all numbers with non terminating decimal digits, for example, $\frac 1 3=0.33\dots$ which is rational, and in particular all irrational numbers. –  Pedro Tamaroff May 15 '13 at 22:55
Why would you think that? Try and count to "$\cdots333$" from $1$. You can't; it's not an integer. Perhaps you tacitly think "counting" can include ordinal induction (in which one can "count" beyond countable infinitiy), but you need to restrict yourself to the actual definition of counting: putting things in bijection with $\bf N$. –  anon May 15 '13 at 23:05
@rivocantus That is not true. What number in $\mathbb{N}$ does 0.33333... map to? –  Old John May 15 '13 at 23:20
There is no bijection between $[0,1)$ and $\mathbb{N}$. The reason you cannot elaborate on your proposed proof is because you do not really have a proof. Your intuition is wrong. It happens to all of us at some point -- all it means is that you need to revise your intuition in light of the facts. –  Trevor Wilson May 15 '13 at 23:41
@trevor I am looking here for those "facts". –  rivocantus May 15 '13 at 23:49

Let's denote the $n^\text{th}$ number in your list by $f(n)$. To use your method to prove that $[0,1)$ is countable, you need to show that $f$ is a surjection, that is, for every real number $x \in [0,1)$ there is a natural number $n$ such that $f(n) = x$. In particular, you have to show that there is a natural number $n$ such that $f(n) = 1/3$. Note that $n$ here is just an ordinary, finite, natural number. So you have to show that $1/3$ appears at some finite stage in your list (e.g. it is the tenth number listed, or the millionth number listed.)

This is not the case, and it is not correct to argue that it must appear sometime because $\mathbb{N}$ is so very large. For no value $n \in \mathbb{N}$ do we have $f(n)=1/3$, any more than we have $f(n) = -1$ or $f(n) = 37$. These numbers simply do not appear in the list.

-
I thought of [0,1). Do you suggest that N is also uncountable ? If it is, then infinity must be taken seriously, I suppose. –  rivocantus May 15 '13 at 23:26
@rivocantus Ok, I changed $[0,1]$ to $[0,1)$ in my answer. The idea is the same. I do not suggest that $\mathbb{N}$ is also uncountable. It is not. Personally I take infinity seriously because I am a set theorist. (I'm not sure what the point of that last sentence in your comment was, however.) –  Trevor Wilson May 15 '13 at 23:29
@rivocantus The thing is that $333...$ with infinitely many 3's is not a natural number---it is not in $\mathbb{N}$. Although $\mathbb{N}$ itself is an infinite set, each member of $\mathbb{N}$ is a finite number. An object of the form $333....$ could be considered as a kind of number: see en.wikipedia.org/wiki/P-adic_number. However, it is not a natural number. –  Trevor Wilson May 16 '13 at 1:43
@rivocantus What your argument shows is that the interval $[0,1)$ is a surjective image of the set of 10-adic numbers, not the set of natural numbers. (And I agree that the same argument works for other radices in place of 10.) –  Trevor Wilson May 16 '13 at 1:45
@wilson No, 333... is not natural number following Peano axioms, but I just wanted to say, that it's successor exists. Obviously that is not sufficient. Seeing p-adic numbers, it opens for the whole new world, fresh air. I think definitions sort out my question. It seems everything depends on defined concepts in use. From now on I will be using p-adic numbers more often. –  rivocantus May 16 '13 at 2:58

You have only counted the numbers whose decimal expansion is finite. This covers absolutely no irrational number, and in fact not even all the rational numbers as well.

Furthermore there is absolutely no reason to expect that this sort of process is continuous. That is to say, the set of finite strings of integers is countable, but the set of infinite strings is uncountable. Even if you can approximate one infinite string by its finite initial segments with a countable process, you can't approximate all the infinite strings at the same time with finite approximation with a countable process.

-
Well, the rationals are countable and they are dense in $\bf R$, so I'd consider enumeration of $\bf Q$ a sort way of approximating them all at the same time. Ultimately, the point is that approximating all the reals and actually obtaining them all in the list are two different things. –  anon May 15 '13 at 23:07
True. So on the right side of the coma we can add infinite sequences of digits, but on the left side we are not allowed to do so. The fact that all digits can be mirrored around coma is insignificant. And the idea about reversed Pi is a ghost number, even if I feel deep inside that if there is one Pi there must be one reversed Pi. I can not but be very fascinated how this is. –  rivocantus May 16 '13 at 6:29
@rivocantus: The natural intuition we come with is hardly ever applicable to infinite objects. This is why we spend time understanding the definitions, and developing new intuitions which suit them. –  Asaf Karagila May 16 '13 at 10:23

To extend a little Peter's comment, you are assuming that you have the decimal expansion of all real numbers. Even if you find a way to extend your method to reals with infinite decimal places (such as $\pi$), there are still a countable number of them. You are missing actually a number of reals that are uncountable and cannot be written with any algorithm: the uncomputable numbers (that is: most of the real numbers!)

-
@fernandez That is true, as far as I can see. But when the sequence grows to infinity it should come closer to the uncomputable reals. The moment when countable becomes uncountable can not be known as much as moment when infinity starts can not be known. My whole point is about ordering so that numbers do not pop out in the middle of the sequence as in Cantors argument. All numbers that have infinite number of decimals are thus squeezed to infinity. I would like just to prove that they have unique place in the sequence, if they do so, then [0,1) has cardinality \aleph_0 . –  rivocantus May 16 '13 at 0:25
well, it is known (well, if you accept the definition of infinite countable vs inf. uncountable) that the set of all computable real numbers is countable. So the number of uncomputable ones must be uncountable, as the whole set of reals. I agree that in principle (but not in practice), you can get as close to any real as you like, but that is not enough (intuition fails). Could you please give me an example, for instance, how do you write PI backwards in your sequence? –  Wolphram jonny May 16 '13 at 0:53
I mean, how do you start at least? –  Wolphram jonny May 16 '13 at 1:06
to me your statement "if natural numbers are infinite there must be place in it so that Pi can be reversed" is wrong. And I don't see any contradiction between countability and infinity. –  Wolphram jonny May 16 '13 at 1:52
I disagree. there is an infinite number of natural numbers, but none of them has an infinite number of digits (you assume there is one if you assume you can write pi that way). You can have a natural number with as many digits as you want, but the number will always be finite. –  Wolphram jonny May 16 '13 at 2:41