Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
4  
2  
3  
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. –  Ilya Mar 22 '12 at 17:44
1  
@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"? –  André Nicolas Mar 22 '12 at 17:50
2  
I down-voted, since Googling "Proving (0,1) is not countable" returns pages and pages of proofs –  you Mar 22 '12 at 19:16

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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