# 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
An almost identical argument was posted on MO recently, and it was commented there why is fails. – Old John May 15 '13 at 22:59
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

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.

-
@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
@rivocantos I should mention that the countability of $\mathbb{N}$ is immediate from the definition of "countable", so perhaps you should take another look at that definition. – Trevor Wilson May 15 '13 at 23:31
@wilson How shall I prove that 1/3 does not appear in my list ? – user3288 May 15 '13 at 23:53
@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

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
@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!)

-
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
I don't think this is the right way to view it. All real numbers have decimal expansions, even if we can compute only countably many of them. Just like all real numbers are either $1$, or smaller than $1$, or greater than $1$, even if we can't tell which one it is. The problem here is not with the existence of decimal expansions, but rather with the fact that vast majority of them do not terminate, so "reversing" makes no sense. – tomasz May 19 '13 at 0:04