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.

  • 1
    Would you reconsider your wording following "I could demonstrate ..."? What do you mean by distance, last, and series?2012-04-12
  • 0
    Don't you mean "if $a_{kk}=1$" and "if "$a_{kk}=0$", intead of $a_{nn}$?2012-04-12
  • 0
    @gspr: Actually no, since I'm referring to the notations used in [Artuno's answer that I linked](http://math.stackexchange.com/a/39285/15274) Sorry for that confusion.2012-04-12
  • 0
    @TheChaz: Sorry, I'm not great with math or words. I added more of my thoughts to attempt to clarify. It's possible (probable?) that those thoughts that I can't articulate _are_ my error.2012-04-12
  • 0
    No need to apologize. I realize how difficult being precise can be, especially in math! Often the process of trying to explain things more "mathematically" leads to deeper insight, whence my comment :)2012-04-12
  • 1
    @TheChaz: In programming, we call that "Rubberducking". I totally understand making me clarify my intent.2012-04-12
  • 6
    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.2012-04-12
  • 3
    For your last sentence, see [Why Doesn't Cantor's Diagonal Argument Also Apply to Natural Numbers?](http://math.stackexchange.com/questions/35107/why-doesnt-cantors-diagonal-argument-also-apply-to-natural-numbers)2012-04-12
  • 1
    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.2012-04-12

7 Answers 7