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

Question

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.

Answer 1

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.

Answer 2

A question of cardinality is always "secretly" a question about functions - specifically, which one-to-one or bijective functions exist. So let's rephrase your three facts in terms of these.

1. There is an injective function $F$ mapping numbers in $(0,1)$ to binary expansions. (Think of binary expansions as just infinitely long strings of symbols, not numbers. Just like a person's name isn't the same as the person - Elvis the musician and the word "Elvis" are not the same thing - a binary expansion is not a number, but it does name a number.) This map is almost surjective; the only issue is that (for example) $0.0111\ldots$ names the same number as $0.1000\ldots$ does. But this sort of thing is the only problem. The standard fix is to call $B$ the set of binary expansions that do not end in an infinite string of $0$'s; then we can make $F$ be a bijection between $(0, 1)$ and $B$.

2. There is a bijective function $G$ mapping binary expansions to subsets of $\mathbb{N}$ (the set of natural numbers). This is usually taken to be the function that gives the set of points at which the expansion has a $1$ - for example, $0.00101101\ldots$ has a $1$ at the third, fifth, sixth, and eighth positions, so its corresponding set would begin $\{3, 5, 6, 8, \ldots\}$.

3. For any $X$, there is no bijective function $H$ mapping the set of subsets of $X$ to $X$. In particular, there is no function $H$ mapping the set of subsets of $\mathbb{N}$ to $\mathbb{N}$ itself.

Okay, putting it all together - let's assume for contradiction that $(0,1)$ is countable. What that would mean is that there would be a bijective function $J$ mapping $(0,1)$ to $\mathbb{N}$. Recall $F$ from fact (1) and $G$ from fact (2). What happens if we start from $\mathcal{P}(\mathbb{N})$ (the set of subsets of $\mathbb{N}$) and apply first $G$ and then $F^{-1}$? Well, applying $G$ gets us to binary expansions. If we started with an infinite subset $A$ of $\mathbb{N}$, then $G(A)$ has infinitely many $1$'s, and so is one of the binary expansions in our set $B$. Then applying $F^{-1}$ (that is, doing $F$ backwards) will take this binary expansion to a unique number in $(0,1)$. That means that $F^{-1} \circ G$ is an injection from the set of infinite subsets of $\mathbb{N}$ into $(0,1)$. But then $J \circ F^{-1} \circ G$ (that is, applying $J$ after we've gotten to $(0,1)$) is an injection from the set of infinite subsets of $\mathbb{N}$ into $\mathbb{N}$ itself.

So we've concluded that - under the assumption that $J$ exists, remember - the set of infinite subsets of $\mathbb{N}$ is countable. But we also know (you've probably seen this in class, but if not it'll make a good exercise) that the set of finite subsets of $\mathbb{N}$ is countable. And the union of these two sets is the set of subsets of $\mathbb{N}$ that are either finite or infinite - that is, all subsets of $\mathbb{N}$. So we've shown that $\mathcal{P}(\mathbb{N})$ is the union of two countable sets. Again, you've probably seen in class that the union of two countable sets is countable. So, in fact, we've shown that $\mathcal{P}(\mathbb{N})$ is countable.

But Fact 3 tells us that there is no injection from $\mathcal{P}(\mathbb{N})$ into $\mathbb{N}$. And to say that $\mathcal{P}(\mathbb{N})$ is to say that there is an injection from $\mathcal{P}(\mathbb{N})$ into $\mathbb{N}$. This is a contradiction, proving our initial assumption - that $(0,1)$ is countable -false.

TL;DR: Whenever you're stuck on a problem like this, go back to the definitions. Figure out what exactly "countable" and "uncountable" mean, and how they apply in the situation you're looking at. Then try chaining functions together, and see where it takes you.