4

How many different proofs are there of the uncountability of the set $[0,1]$ ? I know of the nested interval proof and the Baire Category theorem proof ; please suggest other proofs . Thanks in advance .

$EDIT$ : Is there a proof of this uncountabilty using Shroder-Bernstein Theorem ?

  • 3
    The 'Cantor diagonalization proof' is one. – Prahlad Vaidyanathan Jan 06 '15 at 12:35
  • I don't tink that the Schroder-Bernstein theorem is the right tool for this, because it only says that some sets have bijections between them. It can never be used to prove non-existence of a bijection, although, if you know that no bijection exists, it tells you that injections can only go one way. – Arthur Jan 07 '15 at 13:08

3 Answers3

5

Matthew H. Baker of Georgia Institute of Technology uses a game.

enter image description here

BCLC
  • 13,459
  • 1
    in the given link , page 2 , 4th line from top , how is it that $\alpha < b_n , \forall n \in \mathbb N$ ? I only see $\alpha \le b_n , \forall n \in \mathbb N$ ; moreover from it how does it follow that $\alpha \notin S$ ? –  Jan 06 '15 at 13:10
  • Nice. Not sure. Maybe it's supposed to be that $a_n < b_n$? – BCLC Jan 06 '15 at 13:21
  • Oh sorry. I misread. Maybe it has something to do with the fact that $a_n < b_n$? Can Alice's limit be one of Bob's choices? – BCLC Jan 06 '15 at 17:04
  • 1
    Since they both have to choose strictly monotonous sequences, the limit $\alpha$ of Alice's sequence has to be strictly larger than any $a_n$ and strictly smaller than any $b_n$. – Arthur Jan 07 '15 at 13:05
  • @Arthur Does it? Limits of sequences need not be part of the sequences right? – BCLC May 13 '15 at 10:44
  • 1
    Yes, you're right about that, and I still stand by my comment. Since $[a_{i+1},b_{i+1}]\subset(a_i,b_i)$ for all $i$, we must have $\alpha\in (a_i,b_i)$ for all $i$ as well. – Arthur May 13 '15 at 11:03
  • What are some other interesting games you would like to recommend to others? (Not limited to OP's question) – Michael Dec 24 '22 at 10:23
4

The game proof given by BCLC is nice!

The classical ones that I know are the following:

  1. Direct use of the nested interval theorem : given a sequence of real numbers, construct a real number different from all the numbers in the sequence as the common point of a nested sequence of intervals. (This proof is already pointed out in the question).

  2. The proof using the decimal expansion of real numbers : given a sequence of real numbers given by their decimal expansion, use the diagonal method to produce a real number whose decimal expansion is different from all the ones you are given. (This one should be that suggested in Prahlad's comment).

  3. A variant of 2, where one first shows that there are at least as many real numbers as subsets of the integers (for example, by constructing explicitely a one-to-one map from $\{ 0,1\}^{\mathbb N}$ into $\mathbb R$), and then show that $\mathcal P(\mathbb N)$ is uncountable by the method you like best.

  4. The Baire category proof : $\mathbb R$ is uncountable because 1-point sets are closed sets with empty interior. (Also pointed out in the question).

  5. The measure proof : $\mathbb R$ is uncountable because $1$-point sets have measure $0$. (This is in idm's answer).

5'. The measure proof without measure. First show that a countable set $D$ is negligible in the following sense: for any $\varepsilon >0$, $D$ can be covered by a sequence of intervals $(I_n)$ such that $\sum_0^\infty \vert I_n\vert<\varepsilon$. Then show that a nontrivial interval $I$ is not negligible in this sense, by proving that if $I$ is covered by a sequence of intervals $(I_n)$, then $\sum_0^\infty \vert I_n\vert\geq \vert I\vert$ (this requires some work).

Without any doubt, there are lots of other proofs. For example, an amusing one in this paper: http://arxiv.org/pdf/0901.0446v1.pdf I also found a proof using "only" the completeness property in Theorem 8.1 of this paper: http://arxiv.org/pdf/1209.5119.pdf

Etienne
  • 13,636
  • This is the best answer.. – Matthew Levy Jan 06 '15 at 13:34
  • I knew the author was just being humble! – BCLC Jan 06 '15 at 16:55
  • Btw some of your proofs are kind of repeats of others already presented...? – BCLC Jan 06 '15 at 16:56
  • 1
    @BCLC Yes, I should have said that; and actually I will. – Etienne Jan 06 '15 at 17:44
  • 1
    @BCLC This is done, now. – Etienne Jan 06 '15 at 17:48
  • "Mathematically this proof is very similar to Cantor’s first proof. Alice chooses the left endpoint of each interval In and Bob chooses the right endpoint. When Alice wins it means she has found η which is not in the sequence {ωk}. However this proof is much easier to visualize than the proof of Theorem 2.1. This gave us the idea to write Cantor’s other proofs with a game argument. " – BCLC Jan 07 '15 at 21:25
  • 1
    Could the downvoter explain why he downvoted?? – Etienne Jan 11 '15 at 11:32
2

There are many I think.

I can give you this one:

Let $m$ be Lebesgue measure. If a set is countable, then its measure is null (but the converse is not true e.g. the cantor set). We have that $$m([0,1])=1>0.$$ Therefore, [0,1] is uncountable.

idm
  • 11,824