0
$\begingroup$

My friend and I were talking about Cantor's Diagonal Argument, and he was asking why the Real Numbers were uncountable. He proposed the following situation:

On the first axis, we put 0, 1, 2, ..., 9

On the second axis, we put 0.1, 0.2, 0.3, ..., 0.9

On the third axis, we put 0.01, 0.02, 0.03, ..., 0.09

On the fourth axis, we put 0.001, 0.002, 0.003, ..., 0.009

.

.

.

On the n$^{\text{th}}$ axis, we put 0.(n-2 zeros)1, 0.(n-2 zeros)2, 0.(n-2 zeros)3, ..., 0.(n-2 zeros)9

Similarly, on another axis, we put 10, 20, 30, ..., 90

On the next axis, we put 100, 200, 300, ..., 900

And so on.


We can pick any point in that array, and it will correspond to a Real Number - we should be able to represent the irrational numbers because we have an infinite number of dimensions, and hence can represent a number with an infinite number of decimal places.

It seems to me that this array would have a countably infinite number of dimensions. Given that each axis has only a finite number of elements, and a countable union of countable sets is countable, we should then have a countably infinite number of elements in this array, meaning that the Real Number set should be countable.

But it is not. Where are we going wrong?

$\endgroup$
  • $\begingroup$ The description is highly incomplete. So far, you have got some of the rationals. $\endgroup$ – André Nicolas Jun 21 '14 at 6:27
  • $\begingroup$ @AndréNicolas Why can't we represent any irrationals in this way? $\endgroup$ – user102033 Jun 21 '14 at 6:34
  • 1
    $\begingroup$ Even if I try to complete your argument - I don't see where you get a countable union. Seems like you're stuck with a countable product and then note that $2^{\Bbb N}$ is not countable, while $\bigcup_{n \in \Bbb N} 2^n$ is. $\endgroup$ – Stefan Mesken Jun 21 '14 at 6:43
  • $\begingroup$ "This way" is not described. $\endgroup$ – André Nicolas Jun 21 '14 at 6:46
  • $\begingroup$ @user155124 You are entirely correct, I was going to edit the question to better explain but David's answer beat me to it. $\endgroup$ – user102033 Jun 21 '14 at 7:03
3
$\begingroup$

I'm not entirely clear on your proposed scheme, but it seems to me that you are doing something like this. You have "axes" representing the ten possible units digits, the ten possible first digits after the decimal point, the ten possible second digits after the decimal point, and so on; then also the ten possible digits for "tens", the ten possible digits for "hundreds" and so on. You wish to represent a real number as a "point" in this "space" of countably many dimensions. So for example you would think of $$\pi\leftrightarrow(\ldots,0,0,3,1,4,1,5,9,\ldots)\ .$$ If I have got this right, the problem is that you talk about a countable union of countable sets, which is countable; but you are actually using a countable Cartesian product of countable sets, which is not countable, except in certain special cases.

$\endgroup$
  • $\begingroup$ Ah yes I see it, you are completely correct! $\endgroup$ – user102033 Jun 21 '14 at 7:02
0
$\begingroup$

Even if you had only two elements per "axis", the number of points in your array is uncountable. That's precisely what Cantor's diagonal argument shows.

Technically, what I'm saying is that the Cartesian product of countably many copies of $\{0,1\} $ is uncountable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy