0
$\begingroup$

I have an issue with Cantor's Diagonal Argument.

We suppose we have an infinite list with every real in $(0, 1)$ listed. Then we take the diagonal and change every digit in a predefined way (e.g. $+1 \pmod {10}$). And we get a new real number, not included in the list. This is supposed to prove that reals are not countable.

The problem I see is that, to apply the argument, we must have every real in a square matrix of digits (I use the matrix just as a form of representation). And we can't list every real with a square matrix. For a fixed precision, we need a matrix of $N$ columns (digits) by ($10^N$) rows (for any $N$). I understand the Cantor list would have infinite precision, but we still need $N\times(10^n)$, and we are still construing a list of $N\times N$ digits ($N$ being infinite).

So, it seems to me that the Cantor's Diagonal Argument only proves that we can't list all reals in a square matrix.

What am I missing?

$\endgroup$
  • $\begingroup$ I have never thought about the argument as a matrix. It's just an infinite list of numbers indexed with an infinite number of indices. $\endgroup$ – Randall Aug 24 '17 at 17:49
  • 2
    $\begingroup$ The "matrix" in the diagonal argument has a countably infinite number of rows and a countably infinite number of columns. There is one row for each real number, and the columns are the digits in the decimal expansion (which may have an eventually zero tail). There is no finite matrix in sight. $\endgroup$ – MPW Aug 24 '17 at 17:58
  • $\begingroup$ @MPW I understand that the matrix is infinite (I have updated the question to show this), but I fail to see how this makes a difference. $\endgroup$ – raven Aug 24 '17 at 18:12
  • $\begingroup$ The assumption that the reals in (0,1) are countable essentially is the assumption that you can store the reals as rows in a matrix (with a countable infinity of both rows and columns) of digits. You are correct that this is impossible. Your hand-waving about square matrices and precision doesn't show that it is impossible. Cantor's diagonal argument does show that this is impossible, hence the reals are not countable. $\endgroup$ – John Coleman Aug 24 '17 at 18:12
  • 1
    $\begingroup$ Hmmm... Thank you everyone. I think I need to think a bit about this all. $\endgroup$ – raven Aug 24 '17 at 18:19
2
$\begingroup$

I would say that you are missing nothing. The problem is that you are adding one thing, namely a matrix. That's not part of the diagonal argument.

$\endgroup$
  • $\begingroup$ I don't think I'm adding anything. There is a list of real numbers. Each real number is a list of digits. So we have a two-dimensional list of digits (call it matrix, table, list of list, or whatever you will). To apply the diagonal, it must be square (NxN digits). $\endgroup$ – raven Aug 24 '17 at 17:58
  • 3
    $\begingroup$ @raven : There is no $N$. The diagonal is infinitely long. $\endgroup$ – MPW Aug 24 '17 at 17:59
  • 3
    $\begingroup$ OK, call it a matrix, but it's an $|\aleph_0| \times |\aleph_0|$ matrix. $\endgroup$ – Randall Aug 24 '17 at 18:09
2
$\begingroup$

The idea of a "list" here being a matrix is taking the diagonal argument too literally. The actual argument does not involve doing anything to a physical list of numbers (which you describe as a matrix). It instead involves showing that there cannot exist any one-to-one correspondence (or bijection) between the reals and the natural numbers. The diagonal argument is a way of visualizing the proof, but the underlying nature of the argument has nothing to do with any list of fixed, finite size. These are infinite lists (technically, infinite sequences), and the ideas of finite precision do not apply to them.

For instance, what does it even mean to have a "square" matrix, when your matrix is of infinite size? In the finite sense we understand it (if a matrix is $m\times m$ where $m$ is a natural number, it is square), but we don't have a rigorous method for talking about matrix dimensions when the matrices are infinite. Sure, one could define what that means, but it is neither necessary nor helpful in formulating the diagonal argument.

We often use the visual aide of an infinite list of reals, each real with infinite precision, but that is not necessary for the actual rigorous proof. Here is the proof without that visual aide (glossing over many details).

Suppose the reals are countable. Then there exists a one-to-one correspondence (bijection) between the reals and the natural numbers. Thus we must be able to make an infinite sequence (with a first, second, third, millionth, etc, number) of real numbers in which each real appears at least once. Consider one such sequence $\{s_n\}$. Now we are going to construct a new number which does not appear $\{s_n\}$. We take the first digit of $s_1$ and change it to $s_1+1$ modulo 10, and make that our first digit of the new number. We do the same for the second, third, and all other digits. We now have a number not appearing in the sequence $\{s_n\}$ we had before, because it differs from every term of the sequence in at least one decimal place. It must be a real number, in fact, since it is defined as and represented by an infinite decimal. Thus, our initial sequence did not actually have all the reals appear at least once, so we have a contradiction. Hence, the reals are uncountable.

Note that the argument never makes use of a matrix in any way. The fundamental idea of the proof lies in the use of infinite sequences, which we do have a rigorous grasp on. If you'd like more understanding of the details by which we construct ideas like sequences, it's turtles all the way down in that it comes back to set theory. However, I hope this gave the gist of the proof in a more understandable way, and showed that it does not in any way rely on a physical representation (such as a matrix) of the infinite sequence being dealt with.

(This got much longer than I expected, cheers!)

$\endgroup$
1
$\begingroup$

You don't need a column for each value of digit, just for each digit.

And you don't construct a list of length $\Bbb{N\times N}$. That is just the matrix itself, all the real numbers and their decimal expansions. We start with a list of length $\Bbb N$, and each one of these has a decimal expansion of length $\Bbb N$, and so each row in the matrix is actually just this decimal expansion of one of the real numbers on the list.

Next, we go over the diagonal of this matrix, i.e. nodes indexed by $(n,n)$, and use the digits that appear on that diagonal to generate a new real number which you can now prove is not any row (or column for that matter) of this matrix.

And if each row is a real number on your original list, then it means your original list is not the entire interval.

$\endgroup$
  • $\begingroup$ A short response that explains the 'whole deal' while addressing OP's issues. Also, the clarification "(or column for that matter)" is helpful. +1 $\endgroup$ – CopyPasteIt Aug 25 '17 at 15:37
  • $\begingroup$ Sorry, but this doesn't address my issue. I have always written about a matrix of DIGITS. You need one column for each digit, yes (i.e. N), but you need one row for each possible value of each digit (10^N; for one digit you need 10 rows (10 real numbers, 0.0, 0.1, ...0.8, 0.9 assuming we are working in [0, 1]). That was precisely my argument: with a square matrix you can't represent all the numbers, and to take every digit in a diagonal you need a square matrix. It seems that is the infinity of the "matrix" that makes it work (that was my intuition, but is hard to think about it). $\endgroup$ – raven Aug 25 '17 at 16:08
  • $\begingroup$ This definitely addresses your issue, since you seem to simply not understand what the idea behind "using a matrix" is in this context. Of course that a square matrix represents all the numbers on your list, if your first number is $0.123123123\ldots$, then the first row would have $1$ in the first column, $2$ in the second, $3$ in the third, $1$ in the fourth, and so on. The matrix is not binary. $\endgroup$ – Asaf Karagila Aug 25 '17 at 16:13
  • $\begingroup$ I understand it perfectly (I'd say it's obvious). Please, read carefully my question again. The issue is that, to list all real numbers with N digits, you need 10^N entries in the list. But to extract a new number with all digits changed, you need one digit per entrie, i.e. a square matrix (of DIGITS, yeah). So it's obvious in a square matrix you won't have all real numbers with N digits. I don't even know why you talk about binary matrices. $\endgroup$ – raven Aug 25 '17 at 16:24
  • $\begingroup$ (1) You're using "N" like it is a finite integer, but it's not, and the rules of infinite arithmetic can change, especially when talking about limit cardinals like $\aleph_0$. (2) Secondly, don't think about it as "list all the reals", but rather think of it as taking an arbitrary list of real numbers in [0,1], indexed by the natural numbers, and proving that this list is not the entire interval. $\endgroup$ – Asaf Karagila Aug 25 '17 at 17:18
0
$\begingroup$

It is best not to think of matrices but to use the precise definition of countability.

A set $S$ is countable if there is a bijective function

$$f: \mathbb{N} \rightarrow S$$

A function is a bijection if it is 1-1 and surjective.

The proof of uncountability of the real numbers relies on the use of decimal expansions, and in general there may be more than one decimal expansion for a real number. In the following I will therefore assume that we have chosen a unique decimal representation for each real number (it does not matter which one). Suppose we had such a bijective function

$$f: \mathbb{N} \rightarrow \mathbb{R}$$

But then we could define a real number $d$ that is not in the range of $f$ by defining its decimal expansion in binary as follows. Let $x_i$ be the $i$th digit in the decimal expansion of real number $i$. Then the $i$th digit of $d$ is given by

$$d_i = \begin{cases} 0 & \text{if}\; r_i = 1 \; \text{where}\; r_i = f(i) \\ 1 & \text{if}\; r_i = 0 \; \text{where}\; r_i = f(i) \end{cases}$$

However, $d$ is by definition different from every real number for at least one decimal, so $d$ cannot be in the range of $f$. Therefore $f$ cannot be onto.

The "matrix analogy" is simply used to represent the function $f$ as an infinite table using an entry to hold each decimal for any given real number in the range of $f$; entry $(i,j)$ in the table contains the $j$th decimal of $f(r_i)$.

$\endgroup$
0
$\begingroup$

It should be pointed out that something implicit is happening in this Cantor Diagonal Construction argument (see MathTrain's answer). Recall,

A decimal representation of a non-negative real number $r$ is an expression in the form of a series, traditionally written as a sum ${\displaystyle r=\sum _{i=0}^{\infty }{\frac {a_{i}}{10^{i}}}}$ where $a_0$ is a nonnegative integer, and $a_1, a_2, ...$ are integers satisfying $0 \le a_i \le 9$, called the digits of the decimal representation.

The representation is unique up to the fact that if the ${a_i}^{'}s$ trail off in $9^{'}$s it can be simplified.

This representation is really a statement on the limit of a sequence (convergence),

$\tag 1 r=\lim _{n\to \infty }\sum _{i=0}^{n}{\frac {a_{i}}{10^{i}}}$

The Cantor argument is constructing the $a_i$ for (1) one step at a time, so that for any $N$, none of the $N + 1$ finite expansion sums

$\tag 2 s_n = \sum _{i=0}^{n}{\frac {a_{i}}{10^{i}}} \; n \le N$

can be equal to any of the first $N+1$ 'matrix rows', and that also holds true as the limits are taken.

So there are assumptions being made during the Cantor construction, the underlying facts about decimal representations of real numbers.

Finally, although it can be handled, that little detail about trailing $9^{'}$s needs to be addressed in a rigorous proof. You might want to skip that and study a Cantor proof showing that the binary sequences, $2^{\mathbb{N}}$, is uncountable (and more).


If you look at related material in math.stackexchange, for some inexplicable reason, many people have questions about Cantor's Diagonal Argument. So, as this is the most recent instance, permit me the liberty of simply giving another proof that the real numbers are uncountable.

Recall the following property of real numbers,

Theorem 1: Let $(s_n)$ be a sequence of real numbers satisfying the following conditions,

$\quad s_0 \lt s_2 \lt s_4 \lt \cdots$
$\quad s_1 \gt s_3 \gt s_5 \gt \cdots$
$\quad \text{For every even } i \in \mathbb{N}\text{, } \; s_i \lt s_{i+1}$
$\quad \text{The alternating sequence } s_{k+1} - s_k \text{ converges to } 0$

Then $(s_n)$ converges to the limit $s= \text{LUB} \, \{s_i \, |\; i \text{ is even} \} = \text{GLB} \, \{s_i \, |\; i \text{ is odd} \}$,
and for every $n \in \mathbb{N}$, $s_n \ne s$.

Theorem 2: The set of all real numbers is an uncountable set.
Proof
To arrive at a contradiction, let $f: \mathbb{N} \to \mathbb{R}$ be a surjective mapping. We claim that we can construct a sequence $(s_n)$ satisfying the conditions of theorem 1 with a limit that can't be in the range of $f$, giving the contradiction.

Set $s_0 = f(0)$.
Let $m_1$ be the smallest integer satisfying $f(m_1) \gt s_0$, and set $s_1 = f(m_1)$.
Let $m_2$ be the smallest integer satisfying $f(m_2) \gt s_0$ and $f(m_2) \lt s_1$, and set $s_2 = f(m_2)$.
Let $m_3$ be the smallest integer satisfying $f(m_3) \lt s_1$ and $f(m_3) \gt s_2$, and set $s_3 = f(m_3)$.
etc.

Note that the increasing sequence $(m_j)$ of integers must be unbounded.

It is not difficult to show that $(s_n)$ satisfies the conditions of theorem 1; let $\alpha$ denote this limit. Observe that $f$ can't take on the value of $\alpha$, for if it did, $\alpha$ would have to appear as a term in the constructed $(s_n)$ sequence, since it is inside the alternating $(s_n$) 'clamp-down', and we keep going further out along the domain of $f$ to construct this converging sequence..
$\blacksquare$

Note: In the proof of theorem 2 we only used the fact that the range of $f$ is dense in $\mathbb{R}$, and from that constructed a number $\alpha$ that $f$ can't assume as an output value.

$\endgroup$
  • $\begingroup$ I know there is a lot of people thinking that they are smarter than Cantor and can prove him wrong. I also know better. I know R is uncountable (I "get" it, and I'm pretty confident I could prove it in an at least almost formal way). I think what I miss is some basic understanding of infinity. As I said in another comment, I'll think about this for a few ways and then come back (with a better understanding, I hope). Thank you for the effort, BTW. $\endgroup$ – raven Aug 25 '17 at 16:18
  • $\begingroup$ Indeed, this really started with me trying to prove wrong one of those guys. $\endgroup$ – raven Aug 25 '17 at 16:28
0
$\begingroup$

"We suppose we have an infinite list with every real in (0,1) listed. ... The problem I see is that, to apply the argument, we must have every real in a square matrix of digits." This is a common objection, that is a result of how the proof is taught incorrectly.

First, Cantor did not apply the proof to real numbers; intentionally and specifically. He applied it to infinite-length strings of the two characters "m" and "w." This is a minor point, since we can (and I will) use "0" and "1" instead. Note that such a string is just a function that maps N to the set {'0','1'}, written f:N->{'0','1'}.

Yes, every real number between 0 and 1 can be represented in binary by such a string. But some can be represented by two, which is a problem. It is easily resolved, but unnecessary to do so if we follow what Cantor actually said.

Second, he never assumed there was an infinite list of all such strings, only that there was an infinite list of some such strings. Objections like yours naturally arise when you try to imagine how to physically accomplish what Cantor claimed proved was impossible. You can't, so you quite naturally try to find the flaw.

Lastly, it isn't a proof by contradiction. To be one, you have to show the opposite of a known truth follows from all of what you assume. Not that one thing you assume contradicts something else you assume. So it is not a valid proof-by-contradiction to assume "all" and then derive "not all" from another assumption.

But it is still a valid proof. What Cantor assumed was that there is a set T comprising all of his strings, and that a subset S of it could be generated by the function s:N->S. The diagonalization method is another function d:N->{0,1}, that maps every n to the opposite of nth character of s(n). There is no square matrix here, just a definition of one of Cantor's strings as a function.

What this directly proves, is "If S is a countable subset of T, then S is not all of T." By contraposition ("If A then B" implies "If ~B then ~A"), not contradiction, this proves "If S is all of T, then S is not countable."

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.