Prove (0,1) is uncountable (any method)

1,166

The cardinal of the set of all binary expansions of elements of $(0,1)$ is equal to the cardinal of $\mathcal{P}(\mathbb{N})$. On the other hand, when is it true that an element of $x\in(0,1)$ has more than one binary expansion? When and only when $x=\frac{m}{2^n}$ with $m,n\in\mathbb{N}$ and $m<2^n$. Furthermore, those numbers (which form a countable set) have two and only two binary expansions. Therefore, $\mathcal{P}(\mathbb{N})$ and $(0,1)$ have the same cardinal.

To be more precise, let $B$ be the set of those elements of $(0,1)$ of the form $\frac{m}{2^n}$ with $m,n\in\mathbb{N}$ and $m<2^n$. You have a surjective function$$\begin{array}{rccc}F\colon&\{\text{binary expansions}\}&\longrightarrow&(0,1)\\&(a_1,a_2,a_3,\ldots)&\mapsto&\displaystyle\sum_{n=1}^\infty\frac{a_n}{2^n}.\end{array}$$The function $F$ is surjective, but it is not one-to-one, because every element of $B$ has two (and only two) pre-images. Let $B'=F^{-1}(B)$. You can write $B'$ as a disjoint union $B_0\cup B_1$ such that $F|_{B_0}$ and $F|_{B_1}$ are both bijections onto $B$ (for instance, $B_0$ is the set of those binary expansions which are $0$ after a certain order and $B_1$ is the set of those which are $1$ after a certain order). So, the restriction of $F$ to $\{\text{binary expansions}\}\setminus B_1$ is a bijection onto $(0,1)$. Since $B_1$ is countable, and $\{\text{binary expansions}\}$ is not, $\{\text{binary expansions}\}\setminus B_1$ is uncountable too. Therefore, $(0,1)$ is uncountable.

Share:
1,166

Related videos on Youtube

kemb
Author by

kemb

Updated on July 23, 2022

Comments

  • kemb
    kemb over 1 year

    I am asked to prove (0,1) is uncountable.

    Comment: Prove (0,1 is uncountable) using any method. Update: I tried using contradiction and it worked out well. Thank you.

    • Xander Henderson
      Xander Henderson about 6 years
      (1) asserts that we can work with the binary representations of $(0,1)$, rather than the decimal representations. (2) implies that there is a bijection between the set of binary representations, and the power set of $\mathbb{N}$. (3) implies that $|\mathbb{N}| < |\mathscr{P}(\mathbb{N})|$. Can you put the pieces together?
    • Andrés E. Caicedo
      Andrés E. Caicedo about 6 years
      @bof There are others. See here (and several of the other answers in that thread).
    • bof
      bof about 6 years
      @AndrésE.Caicedo Thanks. Come to think of it, the Dilworth–Gleason proof of their generalized Cantor theorem is not (I guess) a "diagonal" argument, but it does use Hartogs' theorem. Now I'm wondering just how one would define a "diagonal argument" in general, and whether I could be sure that a complicated argument didn't contain a hidden use of diagonalization.
    • Andrés E. Caicedo
      Andrés E. Caicedo about 6 years
      @bof I didn't know that result. Very nice, thank you! I guess at some point I should try to collect examples of such non-diagonal arguments.
  • AlvinL
    AlvinL about 6 years
    ..but you know that any set $A$ contains "strictly less" elements than set $2^A$, therefore $\mathbb N$ has "less elements in it" than $2^{\mathbb N}$ and since $(0,1)$ and $2^{\mathbb N}$ have the "same amount of elements", then ..
  • José Carlos Santos
    José Carlos Santos about 6 years
    @kemb I've added another paragraph. I hope that it helps.
  • José Carlos Santos
    José Carlos Santos about 6 years
    @kemb As Alvin Lepik wrote, “I'm unable to see what precisely you have a problem with.”
  • kemb
    kemb about 6 years
    Sorry , I'm just trying to understand. I don't understand how B is the set of the elements m/2^n. I don't understand where m/2^n comes from.
  • José Carlos Santos
    José Carlos Santos about 6 years
    @kemb $B$ is that set because that's how I defined $B$. Now, consider $x=\frac34\in B$. One binary expansion of $x$ is $0.110000000\dots$ and another one is $0.101111111111\dots$, by the same reason why $1=0.999999999\dots$