8
$\begingroup$

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.

$\endgroup$
9
  • 1
    $\begingroup$ Would you reconsider your wording following "I could demonstrate ..."? What do you mean by distance, last, and series? $\endgroup$ – The Chaz 2.0 Apr 12 '12 at 16:29
  • 1
    $\begingroup$ @TheChaz: In programming, we call that "Rubberducking". I totally understand making me clarify my intent. $\endgroup$ – Mooing Duck Apr 12 '12 at 17:01
  • 6
    $\begingroup$ Note: I do not "try to find $s_f=f(n)$ for some $n$." I prove that $s_f\neq f(n)$ for every $n$. The proof of this is by showing that $s_f(n)\neq f(n)(n)$, which proves that $s_f\neq f(n)$, since they are both functions and two functions are equal if and only if they have the same domain and the same value at every element of the domain ($s_f$ and $f(n)$ both have the same domain, but we show that they don't have the same value at all points). There is no circularity, and in fact there is no proof by contradiction either in the presentation I give. $\endgroup$ – Arturo Magidin Apr 12 '12 at 17:21
  • 3
    $\begingroup$ For your last sentence, see Why Doesn't Cantor's Diagonal Argument Also Apply to Natural Numbers? $\endgroup$ – user856 Apr 12 '12 at 17:33
  • 1
    $\begingroup$ After studying all these answers for over an hour until well after my head hurt, I realized that I was defining f(n) with a particular n as matching the definition, instead of attempting to find the n that matched that definition. By forcing a particular f(n) to have the value of s_f I ran into the element defined in terms of itself issue. So the whole thought was stupid from the get-go. $\endgroup$ – Mooing Duck Apr 12 '12 at 18:08
8
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ This is very well written, and along with Rahul Narain's link, says that "integers" that are infinitely repeating are not "natural numbers", which was definitely the flaw in that part of my reasoning. I guess that means I don't have the right definition of "natural numbers", but even so, that solves that issue. $\endgroup$ – Mooing Duck Apr 12 '12 at 17:43
  • $\begingroup$ They're not integers, either. They're just infinite sequences of digits. $\endgroup$ – user856 Apr 12 '12 at 17:46
  • $\begingroup$ That was why I put integers in quotes, because I didn't know the right term. Sorry for the confusion. I shouldn't have put the natural numbers in quotes, I shouldn't have done that. $\endgroup$ – Mooing Duck Apr 12 '12 at 17:49
2
$\begingroup$

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.

$\endgroup$
13
  • $\begingroup$ I can see that that is the intent, but the proof doesn't make sense (to me) if the element is in the list. It appears to be impossible to construct $s_f$ by the definition given if the element is in the list, as it defines one element to be the opposite of itself. The concepts appear incompatible to me. $\endgroup$ – Mooing Duck Apr 12 '12 at 16:44
  • $\begingroup$ The diagonal element isn't in the list. The point here is that given any such enumeration of reals, we can find a real which does not appear in the list. $\endgroup$ – Benedict Eastaugh Apr 12 '12 at 16:49
  • $\begingroup$ @MooingDuck: Try thinking about it like this: Do you agree that $a_{11}$ is just a $0$ or a $1$? Do you agree that $a_{22}$ is just a $0$ or a $1$? Do you, in fact, for every $i$ agree that $a_{ii}$ is just a $0$ or a $1$? Then surely there is no problem in defining $s_f$? $\endgroup$ – gspr Apr 12 '12 at 16:49
  • $\begingroup$ @gspr: I do agree that each $a_{nn}$ is either a $0$ or a $1$, and that $s_f$ is comprised only of $0$s and $1$s, but the definition of each element of $s_f$ is defined in terms of an another set from $f$, which for $f(n)$ means an element is defined in terms of itself, in a way that is impossible. Benedict: That comment does not appear to add to the discussion. $\endgroup$ – Mooing Duck Apr 12 '12 at 16:54
  • 1
    $\begingroup$ @MooingDuck: I don't know if your doubt has been cleared up yet, or if this was written afterwards your last comment on the question. But: The definition of $s_f$ depends only on $f$ being a function $f\colon\mathbb{N}\to 2^{\mathbb{N}}$; nothing more. It is a consequence of the definition of $s_f$ that in fact $s_f\neq f(n)$ for all $n$. The definition depends on nothing except what $f$ is: the fact that $f$ is a function with domain $\mathbb{N}$, and that every $f(n)$ is a function with domain $\mathbb{N}$ and values in $\{0,1\}$. $\endgroup$ – Arturo Magidin Apr 12 '12 at 19:25
1
$\begingroup$

"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.

$\endgroup$
13
  • $\begingroup$ I realize that the intent is proof by contradiction, but since the definition of s_f is impossible, by claiming it is possible, that excludes the possibility of s_f being in f, which is begging the question. $\endgroup$ – Mooing Duck Apr 12 '12 at 16:50
  • $\begingroup$ @MooingDuck: If I give you an infinite list of zeros and ones, why can't you make another infinite list of zeros and ones that's opposite to the list I gave you at every place? Just take what I gave you, and flip every entry. $\endgroup$ – gspr Apr 12 '12 at 16:51
  • 1
    $\begingroup$ @MooingDuck: No. $f$ is a given function with domain $\mathbb{N}$ and images in $2^{\mathbb{N}}$; the images of $f$ are "sequences" (not series), and they are not sets (except in the general sense that in set theory "everything is a set). The values of $f$ are themselves function. $s_f$ is a function, as is $f$ and each $f(m)$. $\endgroup$ – Arturo Magidin Apr 12 '12 at 17:25
  • 2
    $\begingroup$ @MooingDuck: Note that the proof you link to is not a proof by contradiction (despite what everyone here is writing). It's a direct proof of the proposition: "If $f\colon\mathbb{N}\to 2^{\mathbb{N}}$ is a function with domain $\mathbb{N}$ and image in the set of all functions from $\mathbb{N}$ to $2$, then $f$ is not onto; that is, there exists $s_f\in 2^{\mathbb{N}}$ such that $s_f\notin \mathrm{Im}(f)$." $\endgroup$ – Arturo Magidin Apr 12 '12 at 17:27
  • 3
    $\begingroup$ By the way, I do like to see the correct use of the phrase "begging the question." I've heard newscasters say things like "Which begs the question, which candidate will succeed?" Totally wrong! $\endgroup$ – Cheerful Parsnip Apr 12 '12 at 18:29
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This is an awesome piece. I learned the history behind Cantor's original argument. Thanks. $\endgroup$ – Behnam Esmayli Jan 18 '20 at 15:32
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ No; you are confusing the incarnation of the proof that attempts to deal with the case of real numbers in $(0,1)$ represented by binary expansion, and the incarnation here which deals with the set of functions from $\mathbb{N}$ to $\{0,1\}$. As a function, the binary string $011111\cdots$ does not represent the same function as the binary string $10000\cdots$; because we are interpeting these strings as functions with domain $\mathbb{N}$ and codomain $\{0,1\}$, and not as real numbers. When dealing with functions, there is not "dual representation" problem at all. $\endgroup$ – Arturo Magidin May 6 '12 at 4:16
  • 2
    $\begingroup$ In other words, as sequences, it is false that the string $0,0,1,1,1,\ldots$ is "equivalent" to the string $0,1,0,0,0,\ldots$. It is true that they map to the same real number under the mapping $\{a_1,a_2,a_3,\ldots\}\mapsto \sum 2^{-a_i}$, but we aren't going all the way to the real numbers. Binary strings are not real numbers, they are sequences (that is, functions). $\endgroup$ – Arturo Magidin May 6 '12 at 4:21
  • 1
    $\begingroup$ Thank you. You are right that the original poster asked a question about Cantor's argument in relation to strings representing functions. However Mark Bennett in his response applied Cantor's reasoning to Real Numbers. In that case one has to be a bit more careful, as my example demonstrates. $\endgroup$ – M. Wind May 6 '12 at 19:43

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