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.

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?

share|improve this question
    
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}$... –  N. S. May 12 '11 at 22:33

1 Answer 1

up vote 7 down vote accepted

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.

share|improve this answer
    
Thank you. I didn't realise it was unique for all real numbers except dyadic rationals. –  Jonas Teuwen Oct 29 '10 at 21:07
    
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. –  Qiaochu Yuan Oct 29 '10 at 21:15
    
Hmm. So the bijection above doesn't actually work; it misses 1/2 (and no other number)... but you get my point. –  Qiaochu Yuan Dec 2 '10 at 17:13

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.