# Uncountable preimage of every point

Let $f:[0,1]\to [0,1]$ be a continuous function. Must it have a point $x$ that $f^{-1}(x)$ is at most countable?

Added: Must it have a point $x$ that $dim_H(f^{-1}(x))=0$ ? ($dim_H$ means the Hausdorff dimension)

-
Do you mean 'Must it have a point $x$ such that $f^{-1}(x)$ is countable?'? – HJRW Nov 27 '10 at 20:28
Yes, you are absolutely right. – Nikita Kalinin Nov 27 '10 at 20:31
@Henry: The topic would seem to imply that. – Adam Hughes Nov 27 '10 at 20:32
Countable = at most countable. Anyway, I add it. – Nikita Kalinin Nov 27 '10 at 20:42
Adam - indeed. I just wanted an excuse to write "?'?". – HJRW Nov 27 '10 at 23:14

A simple modification of the ideas of André Henriques, Sergei Ivanov and others shows that it is possible that all fibers have Hausdorff dimension $1$. For completeness I write down a complete proof.

Form a Cantor set as follows: let $I_0 = [0,1/3]$, $I_1=[2/3,1]$. If $I_{i_1,\ldots, i_n}$ has been defined, let $I_{i_1,\ldots,i_n,0}, I_{i_1,\ldots,i_n,1}$ be the two intervals obtained by removing from $I_{i_1,\ldots, i_n}$ a central open interval of length $1/(n+2)$ times the length of $I_{i_1,\ldots, i_n}$. The Cantor set $C$ is then $$C := \bigcap_{n=1}^\infty C_n :=\bigcap_{n=1}^\infty \bigcup_{i_1\ldots i_n} I_{i_1\ldots i_n}.$$ (This is just like the construction of the usual Cantor set, except that the relative lengths of the removed intervals tend to $0$ rather than staying constant).

We define a continuous function $f:C\to [0,1]$, and then extend $f$ to all of $[0,1]$ in an arbitrary way.

Let $x$ be a point of $C$. Then $x$ is coded by a unique sequence $i_1 i_2\ldots\in \{0,1\}^{\mathbb{N}}$, and we define $$f(x) = \sum_{n=1}^\infty i_{n^2} 2^{-n}.$$ It is very easy to check that $f$ is indeed continuous.

Now let $t=[0,1]$, and let $t =\sum_{n=1}^\infty a_n 2^{-n}$ be a binary expansion of $t$. Then $f^{-1}(t)$ consists of those points in $C$ whose code $i_1 i_2\ldots$ satisfies $i_{n^2} =a_n$. In other words, except for places corresponding to perfect squares, the other elements of the sequence are completely arbitrary.

It is a fairly easy exercise in the calculation of Hausdorff dimension to show that $f^{-1}(t)$ has dimension $1$. The easiest way to give a formal proof is perhaps to use the mass distribution principle (see e.g. Falconer's or Mattila's books): we define a measure $\mu$ on $f^{-1}(t)$ inductively as follows. We start by assigning a unit mass to $[0,1]$. After $k$ steps, we have assigned a mass to all intervals $I_{i_1\ldots i_k}$, which is $0$ whenever $I_{i_1\ldots i_k}\cap f^{-1}(t)=\varnothing$. Now, if $k+1=n^2$ for some $n$, then we specify that $\mu(I_{i_1\ldots i_k a_n}) = \mu(I_{i_1\ldots i_k})$ and $\mu(I_{i_1\ldots i_k (1-a_n)})=0$. Otherwise, if $k+1$ is not a perfect square, then we specify that $$\mu(I_{i_1\ldots i_k 0})=\mu(I_{i_1\ldots i_k 1}) = \frac{1}{2}\mu(I_{i_1\ldots i_k}).$$ (In other words, at the stages where the next symbol isn't determined, split mass uniformly; otherwise, pass all the mass to the required interval of next level.)

In this way we have assigned a mass to each of the intervals in the construction of $C$, so that $\mu$ is a well defined measure, which is supported on $f^{-1}(t)$ by construction. Note that if $n^2\le k < (n+1)^2$, then $\mu(I_{i_1\ldots i_k})=2^{k-n}$. Hence $$\lim_{k\to\infty} \frac{\mu(I_{i_1\ldots i_k})}{-\log(2^k)} = 1,$$ for any sequence $i_1 i_2\ldots$, and since $$\lim_{k\to\infty} \frac{\log|I_{i_1\ldots i_k}|}{-\log(2^k)} = 1,$$ it is easy to deduce that $$\lim_{r\to 0} \frac{\log(\mu(B(x,r))}{\log r} = 1$$ for $\mu$-almost every $x$ (indeed for all $x$ in the support of $\mu$). Since $\mu(f^{-1}(t))=1$, the mass distribution principle implies that $\dim_H(f^{-1}(t))\ge 1$ (and hence it is exactly $1$).

Two concluding remarks. A straightforward modification of the argument shows that for any gauge function $\varphi(x)$ such that $\lim_{x\to 0} \varphi(x)/x=+\infty$, there is a continuous function $f:[0,1]\to [0,1]$ such that every fiber $f^{-1}(t)$ has positive $\varphi$-dimensional Hausdorff measure.

Finally, these results are not really surprising, since continuity alone does not imply any Hausdorff dimension bounds. This is the same reason why space-filling curves exist - continuity does not prevent the dimension of the image from being as large as the ambient space, and likewise it does not prevent the dimension of the fibers from being as large as the ambient space.

-
Thanks for the detailed description! – Nikita Kalinin Nov 29 '10 at 20:33

No. For example, let $g : [0, 1] \to [0, 1] \times [0, 1]$ be a continuous surjective map (space-filling curve) and let $p : [0, 1] \times [0, 1] \to [0, 1]$ be the projection onto the first coordinate. Then $p \circ g$ is continuous and the preimage of every point is uncountable.

-
thanks, it is duplicate question. So, I changed it. – Nikita Kalinin Nov 27 '10 at 20:52
If you take the standard example of a space filling curve, and do what Reid and Mark sudgested, then no point-preimage has Hausdorff dimension zero. They actually all have the same Hausdorff dimension: 1/2. – André Henriques Nov 28 '10 at 0:39
@André Henriques Could you clarify it, please? – Nikita Kalinin Nov 28 '10 at 7:25
Every point-preimage is an intersection of subsets of the following form: essentially disjoint unions of $2^n$ intervals, each one of them having a length of $2^{-2n}$. To go from one of these subsets to the next one, you replace every interval of length $2^{-2n}$ by two sub-intervals of length $2^{-(2n+2)}$. – André Henriques Nov 28 '10 at 19:27

Take a composition of a space-filling curve for the unit square with the projection of the square on the first coordinate.

-
Haha. I was about to post the same. Anyway, this question is essentially a duplicate: mathoverflow.net/questions/18666/… – Andrés E. Caicedo Nov 27 '10 at 20:46
thanks for the link. I changed question.... – Nikita Kalinin Nov 27 '10 at 20:52
The answer is exact duplicate, not the question. Peano curves are universal counter-examples". – Mark Sapir Nov 27 '10 at 20:54
@Nikita: I do not have time to think about it, but in Reid and my answers what is the Hausdorff dimension of the preimage of every point? Does it depend on the choice of Peano curve? – Mark Sapir Nov 27 '10 at 20:56
>you cannot find uncountable collections of subsets of [0,1] all of >measure >0. Why? It is true if all subsets have the same dimension...measure can be 0 or $\infty$... – Nikita Kalinin Nov 27 '10 at 21:02

An idea for the Hausdorff-dimension version. I lack the expertise to check whether it really works. Let us imitate the space-filling-curve idea as follows. Take the Koch snowflake and project it in some direction (perhaps even vertically downwards). That is, define the obvious parametrization g of the Koch snowflake and let f(t) be the x-coordinate of g(t). I would expect (but this is the bit I don't know how to check) that the inverse image of each t has the dimension of the Koch snowflake minus 1.

If that doesn't work, then maybe take a Brownian motion and do the same. Now I would guess that you can get up to dimension 1 for each inverse image (in some interval).

-
I don't know much about probability, but it sounds like Brownian motion gives you dimension 1 almost surely, but makes it hard to say things about pointwise lower bounds. (Also, congratulations for reaching 10k.) – S. Carnahan Nov 28 '10 at 13:46
Brownian motion almost surely has uncountable sero set. The similar is true for any other point. But I am not assured that we can commutate these words. I don't now whether is Brownian motion almost surely have uncountable preimage of every point. – Nikita Kalinin Nov 28 '10 at 13:56
I have the same problem with the Koch snowflake: I think abstract results about projecting sets with given Hausdorff dimension will give almost sure statements. But it feels plausible that it should be true. – gowers Nov 28 '10 at 14:24
It is an extremely difficult problem to find the dimension of all (say, linear) fibers of a non-trivial deterministic fractal. Several open questions by Furstenberg (motivated by deep dynamical problems) can be reinterpreted as asking for the dimension of the intersections of certain fractals with all lines in a given direction (or in all directions, depending on the problem). In particular, I guess it is very hard to do this for the Koch snowflake. (continued) – Pablo Shmerkin Nov 29 '10 at 3:17
Do you know something about Brownian preimages? Does Brownial be a example for my question? – Nikita Kalinin Nov 29 '10 at 20:32

Here is a formalization of André Henriques' answer to the Hausdorff dimension variant of the question.

Let $K=\{0,1\}^\infty$ be the standard Cantor set. Define a map $f:K\to[0,1]$ as follows: for a binary sequence $x=x_1x_2\dots\in K$, let $f(x)$ be the real number with binary representation $0.x_2x_4x_6\dots$ (or, equivalently, $f(x)=\sum x_{2k}2^{-k}$). The pre-image of every point of $[0,1]$ contains a subset of $K$ where the even-numbered digits are fixed and odd-numbered ones are arbitrary.

Now embed $K$ as a subset of $[0,1]$ and use your favorite extension theorem to extend $f$ to a map from $[0,1]$ to $[0,1]$. The pre-images could only get larger.

The Hausdorff dimensions of pre-images of course depend on how you represent $K$ as a subset of $[0,1]$. Consider a self-similar Cantor set defined by a parameter $\alpha<\frac12$, namely $K$ is a union of two disjoint subsets homothetic to $K$ with coefficient $\alpha$. Then the distance in $K$ between binary sequences $x$ and $y$ is approximately $\alpha^{-n}$ where $n$ is the first position where the sequences diverge.

Now we can estimate the dimension of pre-images as follows. Consider a map $g:K\to[0,1]$ defined by $g(x_1x_2\dots)=0.x_1x_3x_5\dots$ (base 2). For every $t\in[0,1]$, we have $g(f^{-1}(t))=[0,1]$. And $g$ is Holder with exponent $\beta=\frac12\log 2/\log(\alpha^{-1})$. A $\beta$-Holder map multiplies the Hausdorff dimension by at most $\beta^{-1}$, hence $\dim_H(f^{-1}(t))\ge\beta$.

In this construction $\beta$ can be made arbitrarily close to 1/2. Making all pre-images of dimension exactly 1/2 requires more work.

-
Thanks, your answer clears up my picture! – Nikita Kalinin Nov 29 '10 at 20:34

A simple example is to write any $x$ in $[0,1]$ as a binary sequence of $1$'s and $0$'s and then define continuous functions which takes odd (or even) values in the binary expansion of $x$. That is, if $$x = a_1 a_2 a_3 a_4 a_5 \dots$$ then $$f(x) = a_1 a_3 a_5 \dots$$ This function is obviously continuous and has required property. Also, the Peano curve could be defined in a similar fashion.

-
Nice example, you don't even need to write it in binary. – Nick S Feb 8 '11 at 2:06