1
$\begingroup$

I know a few proofs over this theorem (where $\mathfrak{c}$ is the cardinality of $[0,1]$ and $\aleph_0$ is the cardinality of $\mathbb{N}$) where they construct two injections and then use Schröder-Bernstein (via the Cantor set or something like that).

Now I was wondering if I could do something like this:

Define $s: \{0,1\}^\mathbb{N} \to [0,1]$ by $$s(x) = \sum_{i = 1}^\infty \frac{x(i)}{2^i}.$$

Now this is clearly a surjection because this is just a binary expansion of numbers in $[0,1]$, but not injective because these expansions are not unique. Is there a way to make this work? Can I use this to construct a bijection?

  • 0
    This observation is obvious in Qiaochu's answer: the function $s$ is actually a bijection between $(0,1]$ and the set of infinite subsets of $\mathbb{N}$...2011-05-12

1 Answers 1

6

Yes, but in my opinion, it's really not worth it. Binary expansions are unique for all real numbers except dyadic rationals $\frac{k}{2^n}$, since they can end with a string of zeroes or a string of ones. But there are only countably many dyadic rationals. So define $s : \{ 0, 1 \}^{\mathbb{N}} \to [0, 1]$ to be what you said for all strings that don't end with a string of zeroes or a string of ones, and for the countably many exceptions pick any bijection you like. For example, if a sequence $a_i \in \{ 0, 1 \}^{\mathbb{N}}$ ends with a string of ones, send it to $0.1 a_1 a_2 a_3 ...$, and if it ends with a string of zeroes, send it to $0.0 a_1 a_2 a_3 ...$.

But really, there's no point in not using Schroeder-Bernstein. Explicit bijections are highly overrated; in general it is much easier to construct an injection and a surjection.

  • 0
    Thank you. I didn't realise it was unique for all real numbers except dyadic rationals.2010-10-29
  • 0
    Oh, and it's also unique for 0 and, if you don't allow a units digit, for 1. I forgot to mention that part. But that's covered by how I defined my bijection.2010-10-29
  • 0
    Hmm. So the bijection above doesn't actually work; it misses 1/2 (and no other number)... but you get my point.2010-12-02