9
$\begingroup$

I understand how Cantor's diagonalization argument works with respect to disproving that a bijection between integers and real numbers can exist. What I don't get is why the same reasoning doesn't apply to a bijection from integers to integers. Consider the argument as described here:

http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument#An_uncountable_set

My intuition is telling me that the same thing is not possible because the representation of a given integer is finite in length. I realize that this question has been asked before here: Why Doesn't Cantor's Diagonal Argument Also Apply to Natural Numbers?

But I found the answers somewhat opaque. That's why I am asking again.

$\endgroup$
2
  • $\begingroup$ A set $A$ is countable if either there exists an surjection $f:\mathbb N\to A$ or there exists an injection $f:A\to\mathbb N$. The absence of such a function just proves $A$ isn't countable, not that $\mathbb N$ isn't. The natural numbers are the quintessential countable set, and through those we can show $\mathbb Z$ is countable. $\endgroup$
    – Ian Coley
    Commented Sep 9, 2013 at 3:33
  • 2
    $\begingroup$ So if you follow the same process, you get a string of digits 0-9 where the $n$th digit is different from the $n$th digit of the $n$th entry. But such a thing is not an integer! So it has no business being in your list, and no contradiction is reached. $\endgroup$
    – Henry Swanson
    Commented Sep 9, 2013 at 3:37

1 Answer 1

Reset to default
9
$\begingroup$

As it has been explained in those answers, Cantor's diagonal argument works because we're working with strings of $0$s and $1$s under no constraint at all, whereas natural numbers will eventually "zero out", that is, the sequence will eventually become an infinite string of zeroes. Thus, if you're working with all of $$\{(a_0,a_1,\ldots):a_i\in\{0,1\})=2^{\Bbb N}$$ then the counterexample produced by Cantor's algorithm will again be an element of the sets of sequences of zeroes and ones, but if you're working with a proper subset of this, namely $$\{(a_0,a_1,\ldots):a_i\in\{0,1\} \text{ and } a_n=0 \text{ eventually} )\subsetneq 2^{\Bbb N}$$

it might be the case the "counterexample" is not one at all, since it will not be eventually zero. Thus the argument fails. It is not too hard to come up with such problem:

Consider $2,4,8,16,\ldots$. This is $(0,1,0,\ldots)$, $(0,0,1,0,\ldots)$, $(0,0,0,1,\ldots),\ldots$ and Cantor dictates we take $(1,1,1,1,\ldots)$ as a counterexample. But $(1,1,1,1,\ldots)$ is certainly not eventually zero!

$\endgroup$
1
  • $\begingroup$ I think that works for me. $\endgroup$
    – readyready15728
    Commented Sep 9, 2013 at 11:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .