Improving my understanding of Cantor's Diagonal Argument

I studied Cantor’s Diagonal Argument in school years ago and it’s always bothered me (as I’m sure it does many others). In my head I have two counter-arguments to Cantor’s Diagonal Argument. I’m not a mathy person, so obviously, these must have explanations that I have not yet grasped.

My first issue is that Cantor’s Diagonal Argument (as wonderfully explained by Arturo Magidin) can be viewed in a slightly different light, which appears to unveil a flaw in the argument. If we assume that s_f is an image of f at some index n, then it does not make sense to define s_f as $s_f=(s_1,s_2,s_3,…,s_n,…)$ where
$\begin{equation} s_k = \begin{cases}0 & \mathrm{if\ } f(n)_n = 1\\1 & \mathrm{if\ } f(n)_n = 0\end{cases}\end{equation}$

since then the $n$th element of $s_f$ would be defined as the opposite of itself. Since Cantor’s Diagonal Argument uses this definition that wouldn’t make sense if s_f has an index, then s_f must not have an index, and from there it seems obvious that they would reach the conclusion that s_f is not an image of f. Isn’t that begging the question?

My second issue is more complicated, and less articulate, but basically that when I attempt to put numbers into Cantor’s Diagonal Argument, I could demonstrate that the “missing” element was the within a constant distance from the last element in the “series”, which means all of the infinite other numbers must be before it, which means no matter how long you count, you’d never reach it. For example, if one puts these in the most obvious order of “counting” 0000…, 1000…, 0100…., 1100…, 0010… then the element to be found is obviously the element where all $s_k = 1$, which would be the “last” element in that ordering. But that also seems to apply to the counting numbers, which also seems to violate Cantor’s Arguments.

Solutions Collecting From Web of "Improving my understanding of Cantor's Diagonal Argument"

This might be putting the cart before the horse, but let me address your second issue.

when I attempt to put numbers into Cantor’s Diagonal Argument, I could demonstrate that the “missing” element was the within a constant distance from the last element in the “series”

This seems to be a surprisingly common confusion. There is no “last element” of an infinite series. An infinite series goes on forever, which means that there is no end, which means that there is no element at the end. It’s like asking what the last digit of $\pi$ = 3.14159… is.

When we say something is an element of an infinite series, what we mean is it is the $n$th element of the series for some natural number $n$. For example, the 1st digit of $\pi$ is 3, the 2nd digit is 1, the 3rd digit is 4, the 100th digit is 7, and so on. If you say that 2 appears in the digits of $\pi$, you have to be able to show some $n$ for which the $n$th digit of $\pi$ is 2. It won’t do to say that it is “the last one”, because that doesn’t mean anything.

Now perhaps we can see the flaw in your second argument:

For example, if one puts these in the most obvious order of “counting” 0000…, 1000…, 0100…., 1100…, 0010… then the element to be found is obviously the element where all $s_k=1$, which would be the “last” element in that ordering.

Not really. Your ordering only covers the binary sequences with a finite number of ones. And those are indeed countable, as your ordering shows! But where does 01010101…, for example, appear in your ordering? (Don’t say “halfway through”.) That sequence, and the sequence with all ones, and many others, none of them are the $n$th element of your ordering. In other words, they do not appear in your ordering.

But that also seems to apply to the counting numbers, which also seems to violate Cantor’s Arguments.

No, because there is no last natural number. If you applied the diagonal argument to the natural numbers, you would produce a sequence of digits with infinitely many nonzero digits. Your conclusion would be that you have produced a digit sequence which does not appear in the list of natural numbers, which is correct, because there is no natural number with an infinite number of digits.

My first issue is that Cantor’s Diagonal Argument seems to beg the question.

It’s a proof by contradiction. We assume that every real number is listed, and construct an element that cannot be in the list (the “diagonal element”), contradicting our assumption. Consequently we deduce the negation of the assumption: the real numbers are not denumerable.


As far as your second question is concerned, here’s an initial stab. If I’ve missed your intent, let me know and I’ll try to reframe as necessary.

To construct the diagonal element, “counting” is not required: we don’t need to physically go through every tuple listed by $f$. Every digit of $s_f$ is given by its definition (over $f$).

But really your question is answered just by considering the set $\mathbb{N}$ with its natural order: it has a first element, $0$, but no last element. So even if it were important that we iterate through every element, there would be no element without a predecessor (apart from $0$). So the scenario you suggest can’t happen.

“Begging the question” means “assuming what you are trying to prove.” Proof by contradiction is different. You assume the negation of what you are trying to prove, and then derive a contradiction. You can then conclude that what you are trying to prove must be correct since its negation leads to a problem.

Suppose I could list all the relevant Real numbers in a list so that each one had a serial number which was a positive integer.

I could then construct a number not on the list by taking the opposite of each diagonal element in turn. Check this can be done – it is well-defined.

Check: what we get is a number, and it should be on the list.
But we can see that it isn’t – it disagrees with every number on the list by the way we constructed it, and that is a contradiction.

So something must be wrong – you can see that, by what you have written. And you suggest resolving it by saying that the diagonal number can’t be constructed. But that can’t be the mistake, because the recipe for that is so easy, and it is clearly well-defined. There isn’t a way of having a number on the list which thwarts the recipe.

We can also check easily that what we construct is a number and it should be on the list.

So the only thing which can have gone wrong is the original assumption – that must be wrong. And because we didn’t specify any particular method for creating the list, we only assumed that the list existed, we can’t get round it by changing the list or by finding a cunning method. The only possibility left is that no such list exists.

The comment by Marc Bennett appears convincing. However there is one important aspect yet to be considered, namely that (occasionally) one real number can be represented by two different infinite strings. To be precise, a binary string S followed by 01111111111… represents the same number as the binary string S followed by 100000000000… This can be verified easily, by summing the infinite string of 1’s.

Now let us construct a list of real numbers R, represented by strings S:
R(1) = 0.5 S(1) = {1}
R(2) = 0.25 S(2) = {0,1}
R(3) = 0.75 S(3) = {1,1}
R(4) = 0.125 S(4) = {0,0,1}
R(5) = 0.375 S(5) = {0,1,1}
R(6) = 0.625 S(6) = {1,0,1}
R(7) = 0.875 S(7) = {1,1,1} etcetera.

Applying Cantor’s diagonal method, leads to the construction of a real number X represented by the string {0,0,1,1,1,1,1,1,1…}. As shown above, this string is equivalent to the string {0,1,0,0,0,0….} which represents the real number X = 0.25. And this number is on our list as the second entry: X = R(2). So this is an example where the diagonal method fails.

Many people object to what is taught to beginning students as “The diagonalization proof,” and for good reason. It’s not what Cantor wrote, and it is wrong. The problem is that, as beginning students, they are not taught enough mathematics to understand why it is wrong. They sense that there are flaws, but try to associate them with the premise rather than the incorrect presentation.

To avoid length, I’ll explain this without the rigor of defining functions and bijections and all that. If you have advanced far enough past being a beginning student, understand how they apply, you can translate what I say into better language. If not, I hope this is easier to understand.

First, the premise is “There is an infinite set that cannot be counted,” not “The real numbers can’t be counted.” Cantor’s first proof of this premise was published 16 years before diagonalization. It used the reals only as the example, not as the intended subject. But other mathematicians had objections about assumptions he made, so he devised diagonalization specifically because it does not use real numbers. It used (and you cited this, but I’m not sure you understood all of it) the set of all infinite-tuples of two characters. I’ll call this set T, as Wikipedia does. But note that the two characters don’t have to be “0” and “1.” In fact, Cantor used “m” and “w.”

Second, what is typically taught as diagonalization was only a visualization of the more formal proof, which is sometimes called the power-set proof (if I find time, I will explain more in a comment). I’m not saying there is anything wrong with it, just that there is a more rigorous proof for more advanced students.

Third, the visualization is NOT a proof by contradiction. Say you assume A&B (that is, two disjoint propositions). If you can derive a contradiction that follows from A alone, then all you have proven is that A alone must always be false. Not that B must always be false. What Cantor proved follows only from the assumption that you have counted a subset of T, not that you have counted all of T. All Cantor meant when he used the word “Widerspruch,” which can mean “opposition” or “contradiction,” is that finding an element that is not in the set you counted is in opposition to having all of T.

What diagonalization is, is a proof by contraposition. That is, if you prove “If A then ~B,” then you have also proven “If B, then ~A.” What Diagonalization proves directly, is “If a subset S of T that can be counted, then it is not all of T.” By contraposition, it also proves “If a set S is all of T, then it cannot be counted.”

Here’s an outline of the proof, modeled on what is in Wikipedia but corrected for my points and made clearer to address your questions:

  1. Let T be the set of all infinite-tuples of the two characters “0” and “1.” Call these tuples “Cantor Strings.”
  2. Let S be any infinite set of Cantor Strings that is countable.
  3. Being countable means that for any integers $n$ and $m$, there is a function $d(n,m)$ that represents the $m$th character of the $n$th Cantor String in the counting we assumed exists.
  4. Let $a(n)$ be the opposite character of $d(n,n)$.
  5. So $a$ is Cantor String, and it cannot be in S.
  6. But since T is the set of all Cantor Strings, $a$ must be in T.
  7. This directly proves “If S is a countable set of Cantor Strings, then it is not all of T.
  8. By contraposition, it also proves “If S is all of T, then it is not countable.

To address your issues:

“The $n$th element of $s_f$ would be defined as the opposite of itself.” No. You are confusing what I called $a(n)$ with what I called $d(n,n)$.

“I could demonstrate that the ‘missing’ element was the within a constant distance from the last element in the ‘series’.” Only if you assume that S is all of T, which is not a part of the (correct) proof.

Cantor’s diagonal argument (to prove that $\mathbb{R} > \mathbb{N}$), is not based on counting the elements of both sets (which is used afterwards in the concept of transfinite numbers), but in the fact that they cannot be put into an 1-1 correspondence between them and since the set $\mathbb{N}$ is contained in $\mathbb{R}$ thus $\mathbb{R}$ is a strictly greater set.

The diagonal argument shows that this attempted 1-1 mapping fails. This is all, no explicit counting is done, since one deals with infinite (which btw literally means “not finished“) sets.