1
$\begingroup$

Cantor's diagonal method shows that the set $S=\{x\in \Bbb R|x \in [0,1)\}$ is uncountably infinite, because there is no bijection between the set $S$ and the set of natural number $\Bbb N$.

I came up with this method of mapping the set $S$ to $\Bbb N$. It should be wrong, but I don't know where.

We start with any $x \in S$, and we will build the whole set $S$ using the following method. First, for example, choose $x$ that $$x=0.12345678900000......$$ Next, we can choose any digit of x, and change it such that $0 \rightarrow 1$, $1 \rightarrow 2$, $2 \rightarrow 3$, $...$, $8 \rightarrow 9$, $9 \rightarrow 0$, to make a new real number $x_1\in S$. Because the list of digits of $x$ is countably infinite, there are countably infinite ways of choosing a digit, making the set $\chi_1$ of all real numbers differs $x$ by 1 digit a countably infinite set.

For any $x_1^i \in \chi_1$ (the subscript "1" stands for "differs $x$ by 1 digit"), we can follow the previous method, to make a set of real numbers differing $x$ by 2 digits (actually $x$ itself is in this set too, but we don't care about duplication). There are countably infinite number of such sets, denoted $\chi_2^i$, built from each number $x_1^i$ of the set $\chi_1$.

At this point, we might attempt to create the union of all the sets that we have just created: $$U_2=\chi_1 \cup \biggl( \bigcup_{i=1,\\i\in \Bbb N}^{\infty}\chi_2^i\biggr)$$ $U_2$ is countably infinite.

We can now create the set $U_3$ as the countably infinite union of all countably infinite sets $\chi_3^i$. Then $U_4$, $U_5$, ...

For any number $r$, $r \in S$, it differs $x$ atmost at countably infinite number of digits. Therefore, by repeating this procedure countably infinitely many times, we can construct a set that is a superset of $S$ $$U_\infty = U_{i\in \Bbb N,i\rightarrow \infty} \supset S$$ $U_\infty$ is a proper superset of S, because it contains infinitely many duplicates of any number $r \in S$. But if $U_\infty$ is countably infinite, then S is also countably infinite.

Please help me see where the error in my "proof" is.

$\endgroup$
  • $\begingroup$ “Because the list of digits of $x$ is countably infinite...” Why? $\endgroup$ – MathIsLife12 Mar 19 at 12:46
  • 1
    $\begingroup$ Why does this need to be continuous? Do you think that the set of all finite subsets of $\Bbb N$, which is the union of power sets of initial segments of $\Bbb N$ needs to be equal to the power set of $\Bbb N$ itself? $\endgroup$ – Asaf Karagila Mar 19 at 12:48
  • $\begingroup$ Do you obtain at any step a number that differs from $x$ at infinitely many digits? Or do you only get the set of numbers in $[0,1)$ that differ from $x$ at finitely many digits? $\endgroup$ – Doug McLellan Mar 19 at 12:52
  • 2
    $\begingroup$ I think what you need to be careful about is the difference between "the set of numbers that differ from $x$ at arbitrarily many -- but still finitely many -- digits," and "the set of numbers that differ from $x$ at at-most-countably-many digits." The union of all the $U_i$'s will give you the first set; but the second set is strictly larger. $\endgroup$ – Doug McLellan Mar 19 at 15:06
  • 1
    $\begingroup$ If the union is the power set of the natural numbers, tell me please, for which $n$ you have $\Bbb N\subseteq\{0\dots n\}$? $\endgroup$ – Asaf Karagila Mar 19 at 16:25
5
$\begingroup$

Your claim that $S\subset \bigcup_{n\in\mathbb N} U_n:=U_\infty$ is false. I believe this may stem from a misunderstanding of what an infinite union is. In elementary set theory we have, for any index set $I$ and collection $\{A_i\}_I$, that $y\in \bigcup_{i\in I}A_I$ if and only if there exists some $\alpha\in I$ such that $y\in A_\alpha$.

To prove that your claim is false, let $y\in S$ be some real that differs from $x$ at every digit. Suppose that $y\in U_\infty$. By definition we must then have that $y\in U_n$ for some $n\in \mathbb N$, but then $y$ can only differ from $x$ at at most $n$ digits, which is a contradiction.

This is akin to a misunderstanding often seen in mathematical induction. For example with induction you can prove, for every $n\in \mathbb N$, that $\int_0^n 1dx<\infty$. However you cannot conclude from this that $\int_0^\infty 1dx<\infty$. In other words induction does not allow you to pass to the limit. In the same way an infinite union does not allow you to "pass to the limit" to form some set $U_{\mathbb N}$ containing numbers differing from $x$ at all decimal points. It only allows you to talk about numbers differing from $x$ at any arbitrary but finite number of decimal points. If you want to pass to the limit, then you are no longer just taking the countable union of countable sets anymore.

$\endgroup$
  • $\begingroup$ This really makes sense. Now i realize that induction proves some property X for any natural number, as long as that natural number can be explicitly pointed out. And so Cantor’s method and your example show that whenever anyone try to pick out real numbers and map them to natural numbers, some real numbers escape that method. $\endgroup$ – Quoc Trung Phung Mar 24 at 1:00
  • $\begingroup$ @QuocTrungPhung: Right; I'm glad you understand it. Also, it's worth pointing out that the diagonalization is computable, in the sense that if you have any oracle (think of it as a black-box) $L$ such that $L(k,n)$ is the $n$-th decimal digit of the $k$-th real number in some countable list, then the program $D = ( n ↦ L(n,n)<5 \mathbin{?} 7 \mathbin{:} 0 )$ encodes a real number that is not in that list and is furthermore computable given $L$. So it is impossible to even object that we may not be able to 'construct' the diagonal. $\endgroup$ – user21820 Mar 25 at 7:23

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.