# Surjective Function from a Cantor Set

I recently solved an interesting problem on an midterm. Here is one piece of it:

Let $K =\prod_{i=1}^\infty \{0,1\}$ in the product topology, and let $s_1,s_2,\ldots$ be a sequence of positive real numbers such that $\sum_{i=1}^\infty s_i = 1$. Define a function $f\colon K \to [0,1]$ by $(k_1,k_2,\ldots) \mapsto \sum_{i=1}^\infty k_is_i$.

1. Show that $f$ is continuous. (This part I had no trouble with.)

2. Show that if $s_k \leq \sum_{i=k+1}^\infty s_i$ for all $k$, then $f$ is surjective.

I was able to prove this, but I'm not satisfied with my proof of the second part, because it seems like there should be a much easier way to show this. Does anyone see a simple/simpler approach to this problem than mine?

Here's a very rough outline of my proof. I've left out a lot of details, so let me know if something really doesn't make sense.

Suppose there is some $x \in [0,1] \setminus f(K)$. Then there is a neighborhood $(x-\epsilon,x+\epsilon)$ which isn't hit by $f$. Since $K$ is compact, $f(K) \cap [0,x]$ is compact, hence closed, and so it contains its supremum. This supremum is the image of an element of the form $(k_1,\ldots,k_n,0,1,1,\ldots)$. By our hypotheses we get $f((k_1,\ldots,k_n,0,0,\ldots)) < x-\epsilon$ and $f((k_1,\ldots,k_n,0,1,1,\ldots)) > x+\epsilon$, so we take the supremum of the images of all elements that start with $(k_1,\ldots,k_n,0)$ and map into $[0,x]$. This element is again the image of an element whose entries are eventually equal to 1. Repeating this gives a sequence of pairs of elements of $K$ with longer and longer initial parts. These must converge in $K$, but their images have to be at least $2\epsilon$ apart, so we reach a contradiction.

-
How do you conclude "Then there is a neighborhood $(x−\epsilon,x+\epsilon)$ which isn't hit by $f$"? When you say $K$ is compact, which topology are you using? How can you deduce anything from compactness of $K$ without first showing that $f$ is continuous? –  Henning Makholm Nov 12 '11 at 3:05
@HenningMakholm Thanks. I've edited the question a bit to include some stuff I left out. –  Dane Nov 12 '11 at 3:21

It's simpler to show explicitly, for an arbitrary $x\in[0,1]$, how to construct $(k_n)_n\in K$ that maps to $x$.

Define $k_n$ recursively by $k_i=1$ iff $(\sum_{j=1}^{i-1} k_j s_j)+s_j \le x$ and $k_i=0$ otherwise ...

-
nice observation how to proove that your $k$ satisfy $f(k)=x$? –  Hassan Nov 12 '11 at 3:20
Yeah, that was actually my first impulse when I saw the question, but I couldn't manage to prove that $f(k) = x$. Maybe it's obvious and I'm just not thinking of it. –  Dane Nov 12 '11 at 3:41
@Daniel,@hassan: Clearly $f(k) \le x$. Suppose to the contrary that $f(k) < x$. If $k_n = 0$ for infinitely many $n$, then since $s_n \to 0$, we can find an $n$ such that $s_n < f(k) - x$ but $k_n = 0$. This contradicts our construction. If $k_n = 0$ for only finitely many $n$, let $k_N$ be the last one. Then $\sum_0^{N-1} k_j s_j = f(k) - \sum_{N+1}^\infty s_j < x - s_N$ so our construction should have given $k_N = 1$, another contradiction. –  Nate Eldredge Nov 12 '11 at 3:59
Of course! Thank you. –  Dane Nov 12 '11 at 4:06
Since $\sum_{i=1}^\infty s_i$ converges, we have $s_i \to 0$. As Nate said, there is a point where the $s_n$ get smaller than $f(k) - x$. Since there are infinitely $n$ with $k_n = 0$, we can choose one of these which is after the point where all the $k_i$ are small enough. –  Dane Nov 12 '11 at 4:20
show 1 more comment

The question already has been answered. I just wanted to mention, that this result (or a very similar one) appears in mathematical literature.

Ribenboim P. My Numbers, My Friends, Springer, 2000, p. 51.

Let $(s_i)$ be a sequence of positive real numbers such that $s_1>s_2>s_3>\dots$ and $\lim\limits_{i\to\infty} s_i=0$. Let $S=\sum_{i=1}^\infty s_i=S\le+\infty$. We say that $x > 0$ is representable by the sequence $(s_i)$ if $x=\sum_{j=1}^\infty s_{i_j}$ (with $i_1<i_2<i_3<\dots$ ). Then, necessarily $x\le S$.

The first result is due to Kakeya; for the sake of completeness, we give a proof:

Proposition 1. The following conditions are equivalent:

1. Every $x$, $0 < x < S$, is representable by the sequence $(s_i)$, where $i_1$ is the smallest index such that $s_{i_1}<x$.
2. Every $x$, $0 < x < S$, is representable by the sequence $(s_i)$.
3. For every $n\ge 1$, $s_n\le \sum_{i=n+1}^\infty s_i$.

Proof of the above result is basically the greedy approach. If we already have constructed some partial sum $\sum_{k=1}^{n-1} s_i\le x$, $i_n$ will be the smallest index such that $s_i\le x-\sum_{k=1}^{n-1} s_k$. The proof can be found also here. Note that the proof works for non-increasing sequences. (Although the formulation in Ribenboim's book uses decreasing sequences only.)
As can be seen from Henning's answer, the condition that $(s_k)$ is non-increasing is not really needed for this claim to hold.
Alternatively, we can reorder the sequence $s_k$ starting from the largest element. Such reordering cannot influence the validity of condition $s_n\le \sum_{i=n+1}^\infty s_i$. Since $\lim\limits_{i\to\infty} s_i=0$, such reordering is possible. (There are only finitely many terms greater than 1/2, finitely many terms greater than 1/4, etc.)