2
$\begingroup$

Recall that a countable set $S$ implies that there exists a bijection $\mathbb{N} \to S.$

Now, I consider $(0,1).$ I want to prove by contradiction that $(0,1)$ is not countable.

First, I assume the contrary that there exists a bijection $f,$ and I can find an element in $S,$ but not in the range of $f.$ But I can't find such element. How can you construct such $f$?

$\endgroup$
8
  • 4
    $\begingroup$ See en.wikipedia.org/wiki/Cantor%27s_diagonal_argument $\endgroup$ Commented Mar 22, 2012 at 17:40
  • 2
    $\begingroup$ math.stackexchange.com/questions/18969/… $\endgroup$
    – Asaf Karagila
    Commented Mar 22, 2012 at 17:43
  • 3
    $\begingroup$ Does it really deserve two (well, while I was typing the 3rd appeared) downvotes without even stating the reason? Giving 1 upvote just to cancel the effect. $\endgroup$
    – SBF
    Commented Mar 22, 2012 at 17:44
  • 1
    $\begingroup$ @jason: And another upvote. But for the sake of hopelessly not with it people like me, would it be possible to use "I" and not "i"? $\endgroup$ Commented Mar 22, 2012 at 17:50
  • 2
    $\begingroup$ I down-voted, since Googling "Proving (0,1) is not countable" returns pages and pages of proofs $\endgroup$
    – William
    Commented Mar 22, 2012 at 19:16

3 Answers 3

8
$\begingroup$

Assume that $(0,1)$ is countable. Then you can write $[0,1]=(x_n)_{n \geq 0}$. Do the following steps:

  • split $[0,1]$ into three equal parts $[0,1/3],[1/3,2/3],[2/3,1]$. Then $x_0$ is not in one of the given intervals. Denote it by $[a_0,b_0]$.
  • split $[a_0,b_0]$ into three equal parts $I_1,I_2,I_3$. Then $x_1$ is not in one of the given intervals. Denote it by $[a_1,b_1]$.
  • inductively construct an interval $[a_{n+1},b_{n+1}]\subset [a_n,b_n]$ such that $x_{n+1} \notin [a_{n+1},b_{n+1}]$ and $b_{n+1}-a_{n+1}=\frac{1}{3}(b_n-a_n)$.

Since $[a_n,b_n]$ is a decreasing sequence of compact intervals with $b_n-a_n \to 0$ their intersection is a point $C \in [0,1]$. If $[0,1]=(x_n)$ then there exists $m$ such that $x_m=C$. But then $x_m \notin [a_m,b_m]$ and therefore it cannot be in the intersection of all intervals. Contradiction.

$\endgroup$
6
$\begingroup$

This is the famous Cantor's Diagonal Argument.

The bijection $f$, which we have assumed to exist, can map any positive integer to a value in $(0,1)$ (and since it's a bijection, none of the points in $(0,1)$ are left over). Also, the points in $(0,1)$ can be treated as a number line so that each point on the line is a value between $0$ and $1$ which we can write out as a decimal.

Imagine writing these decimals out in order according to the integer they map to. So perhaps $1 \mapsto 0.5$ and $2 \mapsto 2/3$ and $3 \mapsto 1/\pi$:

 1: 0.50000000...
 2: 0.66666666...
 3: 0.31830988...
 ..etc..

Now read down the diagonal (marked in bold above) and pick a different digit than what you see. For instance, if you see a $5$, use "$6$", if you see anything else use "$5$". That gives us a series of digits... in this case it starts out "$0.655...$".

Clearly, this series of digits is not in the list, since it differs from each item in the list by at least one decimal place. Clearly it is a number in the range $(0,1)$. Since we used $5$ and $6$ it also doesn't have a repeating "$99999...$" or "$00000...$" (which is a way $2$ different sequences of digits could represent the same number). So our assumption that $f$ was a bijection must have been false.

$\endgroup$
1
$\begingroup$

This question has already been answered, however I will write another approach to the problem using measure theory, for future reading.


Let $\mu^{*}$ the outer measure and suppose that $(0,1)$ is countable, so we have that $$\mu^{*}((0,1))=0$$ But, also since $$\mu^{*}((0,1))=\mathcal{l}(0,1)=1-0=1$$ but $1\not=0$. Therefore, $(0,1)$ is not countable.

$\endgroup$

You must log in to answer this question.

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