MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

It's a question I've been thinking about but I can't find an easy answer. I think it will be interesting. Can there be a countable collection of real valued functions $f_1, f_2 , ... $ such that for any subset $K$ of $\mathbb R$ of cardinality continuum, the set of those $n$ such that $f_n(K)$ is not the whole of $\mathbb R$ is finite?

share|cite|improve this question
If CH fails, it is impossible, by taking any uncountable $K$ of size less than $\mathbb{R}$. Perhaps you want $K$ of size continuum? – Joel David Hamkins Dec 19 '10 at 15:39
Do finitely many $f_1,...f_n$ not always satisfy the desired property? – Stefan Hoffelner Dec 19 '10 at 15:45
@Joel - yes. I have not even considered that option :) @oktan - You are totally right, but that's easily fixed by extending the list to an infinite set consisting of constant functions – mathahada Dec 19 '10 at 15:53
@oktan, @mathahada: you don’t need to throw constant functions in; if the finite set of functions is presented as an infinite sequence, as the question specifies, e.g. $f_1, \ldots f_k, f_k, f_k, \ldots$, and if again we’re careful to take the question literally and look not at whether sets of functions are infinite but at whether subsequences are, then it’s clear that this list doesn’t satisfy the property. – Peter LeFanu Lumsdaine Dec 19 '10 at 17:25
up vote 6 down vote accepted

I have three observations.

First, I have noticed that there can be no such sequence of functions $f_n$, if one insists that every $f_n$ is a measurable function. In particular, there can be no sequence of Borel functions with your property. To see this, suppose that $f_n:\mathbb{R}\to\mathbb{R}$ is a countable sequence of measurable functions. If infinitely many $f_n$ are not surjective, then clearly the property will fail and we are done. So we may assume that all but finitely many of the functions are surjective, and by throwing away finitely many functions, we reduce to the case where all $f_n$ are surjective. For each natural number $n$ and real $y$, let $A^y_n=f_n^{-1}(y)=\{\ x\ \mid\ f_n(x)=y\ \}$. For any fixed $n$, the sets $A^y_n$ for various $y$ partition $\mathbb{R}$ into continuum many disjoint measurable sets. Since one cannot have uncountably many disjoint positive measure sets, it follows that there must be some $y_n$ (and in fact many such $y_n$) with $\lambda(A^{y_n}_n)=0$, where $\lambda$ is the Lebesgue measure. Let $K=\mathbb{R}-\bigcup_n A^{y_n}_n$, which is the complement of a measure $0$ set, and so in particular, $K$ has size continuum. Observe that $f_n[K]$ omits $y_n$ by construction, and so there is no $n$ for which $f_n[K]=\mathbb{R}$, showing that the desired property fails. I guess the argument actually doesn't need that every $f_n$ is measurable, but only that $f_n^{-1}(y)$ is a measurable set for every $y$.

Second, this idea combines with the idea that Gowers had briefly posted yesterday, namely, the idea of making a large cardinal assumption, and allows us now to prove the following theorem.

Theorem. If the continuum is a real-valued measurable cardinal (a hypothesis that is equiconsistent over ZFC with the existence of a measurable cardinal), then there is no such sequence of functions $f_n:\mathbb{R}\to\mathbb{R}$.

Proof. Suppose that the continuum is a real-valued measurable cardinal. This means that there is a countably-additive real-valued measure $\mu$, measuring every subset of $\mathbb{R}$ and giving points measure $0$. We may assume that $\mu$ extends the Lebesgue measure. Using this measure, every function $f_n$ is measurable, of course, and so the idea of the paragraph above goes through, using the new measure in place of the Lebesgue measure. QED

In particular, this shows that if large cardinals are consistent with ZFC, then a negative answer to your question is also consistent with ZFC. So one shouldn't expect to be able to build a sequence of functions provably exhibiting the property.

Finally, third, I noticed that if the Continuum Hypothesis holds, then there is a sort-of-near-positive solution in the sense that there is a sequence of functions $f_n:\mathbb{R}\to\mathbb{R}$ such that for every uncountable set $K\subset\mathbb{R}$, the combined range is onto, meaning $\bigcup_n f_n[K]=\mathbb{R}$. (And in fact, the existence of such $f_n$ is equivalent to CH.) To see this, let $\lt$ well-order $\mathbb{R}$ in order type $\omega_1$. In particular, every real $x$ has only countable many predecessors in $\lt$, so enumerate them as $f_n(x)$ for $n\in\omega$. If $K\subset\mathbb{R}$ is any uncountable set, then $K$ is unbounded in the well-order, and so every real $y$ is a predecessor of some element of $K$, and so $y=f_n(x)$ for some $x\in K$. Thus, $\bigcup_n f_n[K]=\mathbb{R}$, as desired.

Your question is very interesting!

share|cite|improve this answer

EDIT: The following answer was not correct, as pointed out in the comments (though the false part is now deleted). At least it shows that there cannot be a finite collection of functions with the demanded property, but the infinite case is still open:

$\textbf{Claim}$: Let $A \subset \mathbb{R}$ of continuum size and let $f: A \to \mathbb{R}$ then there exist $\mathcal{c}$ (contiuum size) many subsets of $A$ of size $\mathcal{c}$ such that for each such $X$, $f(X) \neq \mathbb{R}$.

$\textit{Proof}$: Consider a partition $P$ of $A$ of size $\mathcal{c}$ such that each element of $P$ has size $\mathcal{c}$. If for $\mathcal{c}$-many elements of $P$ $f(X) \neq \mathbb{R}$ then we are finished thus we may assume w.l.o.g that for each $X \in P$ $f(X) = \mathbb{R}$. Then we can pick for each $r \in A$ and each $X_i \in P$ an $x_i \in X_i$ such that $f(x_i) = r$. Thus we obtain for each $r \in$ $A$ a set $Y_r \subset \mathbb{R}$ of size $\mathcal{c}$ such that $f(Y_r) \neq \mathbb{R}$.

Now let $f_1, f_2,..$ be an arbitrary sequence of functions from $\mathbb{R}$ to $\mathbb{R}$. By our claim there is a set $A_1$ of continuum size such that $f(A_1) \neq \mathbb{R}$. Then using our claim again there exists an $A_2 \subset A_1$ such that $f_2(A_2) \neq \mathbb{R}$, and an $A_3 \subset A_2$ and so on.

Thus if $f_1,...,f_n$ are real valued functions, then there is a set $A$ of continuum size such that $f_i (A) \neq \mathbb{R}$ for each $i \le n$.

share|cite|improve this answer
I don't understand the last paragraph. What if each $A_n$ happens to be set of all those reals larger than $n$? – mathahada Dec 19 '10 at 19:05
I am sorry and you are right. So please forget my incorrect answer. – Stefan Hoffelner Dec 19 '10 at 19:08
It still proves the claim that a finite collection of functions can't satisfy the criteria so I think you should edit your post to emphasize that – mathahada Dec 19 '10 at 19:12

Your Answer


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.