Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

Let $X,Y$ be complete separable metric spaces, with $X$ locally compact, and $C(X,Y)$ the space of continuous functions from $X$ to $Y$, equipped with the topology of uniform convergence on compact sets. If I am not mistaken, $C(X,Y)$ is Polish.

Let $S \subset C(X,Y)$ be the set of functions in $C(X,Y)$ which are surjective.

Is $S$ Borel? If not, what can we say about its complexity?

If $X$ is compact, it is easy to show that $S$ is closed. But the locally compact case seems harder.

In particular, I have in mind something like $X = \mathbb{R} \times [0,1]^2$ and $Y = \mathbb{R}^d$.


share|cite|improve this question

Thanks to a suggestion from Clinton Conley, we can show that this set is $\Pi_1^1$, i.e. co-analytic.

$X$ is $\sigma$-compact, so we can write $X = \bigcup K_n$ for compact $K_n$. Then it is easy to check that $$B_n := \{(f,y) \in C(X,Y) \times Y : y \notin f(K_n)\}$$ is open in $C(X,Y) \times Y$. Thus $$B := \bigcap_n B_n = \{(f,y) \in C(X,Y) \times Y: y \notin f(X)\}$$ is $G_\delta$ and in particular Polish. The projection of $B$ onto $C(X,Y)$ is thus analytic, but this projection is exactly the complement of $S$.

This leaves open the question of whether $S$ is necessarily Borel. However, it does guarantee that $S$ is universally measurable. Moreover, and this is what I really wanted, for any Polish $Z$ and any continuous $g : Z \to C(X,Y)$, $g^{-1}(S)$ is again $\Pi_1^1$ and hence universally measurable.

share|cite|improve this answer
That's very clever. – t.b. Jul 26 '12 at 22:38
This is a bit off-topic, but anyway: do you have a simple proof that for $X = Y = \mathbb{R}$ the set $S$ is Borel? Since it is necessary and sufficient to hit all integers the set $S = \bigcap_{n \in \mathbb{Z}} \{f \,:\, \exists x\,:\,f(x) = n\}$ is a countable intersection of analytic sets, hence analytic and your argument shows it to be co-analytic, so it is Borel by Souslin's theorem. But there should be a much easier way to see that, no? – t.b. Jul 27 '12 at 0:14
@t.b.: I think you can use the same trick as in my answer and write $S = \bigcap_n \bigcup_m \{ f : n \in f([-m,m]) \}$, where the latter sets are closed. – Nate Eldredge Jul 27 '12 at 0:36

I have little intuition about the projective hierarchy, and this is presumably far too simple-minded to come close to a sharp estimate, but for what it's worth: the following easy argument shows that the set $S$ of surjective continuous functions is at worst a $\boldsymbol{\Pi}_{2}^1$-set. I have no idea whether $S$ is Borel or not.

The point is that we can describe $S$ by quantifying twice over a Polish space: for all $y \in Y$ there exists $x \in X$ such that $f(x) = y$ or, equivalently, $(f,x,y) \in F$, where $F$ is the closed set $$ F = \{(f,x,y) \in C(X,Y) \times X \times Y\,:\,f(x) = y\} \subset C(X,Y) \times X \times Y. $$ The set $F$ is closed because the map $\operatorname{ev}\colon C(X,Y)\times X \to Y$ given by $\mathrm{ev}(f,x) = f(x)$ is continuous because $X$ is locally compact, and $F$ is the pre-image of the diagonal of $Y \times Y$ under $\mathrm{ev} \times \mathrm{id}_Y \colon C(X,Y) \times X \times Y \to Y \times Y$.

Projecting $F$ down to $C(X,Y) \times Y$ (existential quantification over $X$) gives us the $\boldsymbol{\Sigma}_{1}^1$-set (aka analytic set) $$ A = \{(f,y) \in C(X,Y) \times Y\,:\,(\exists x \in X)\;f(x) = y\} \in \boldsymbol{\Sigma}_{1}^1. $$ Now $\boldsymbol{\Sigma}_{1}^1 \subset \boldsymbol{\Pi}_{2}^1$ and the point class $\boldsymbol{\Pi}_{2}^1$ is stable under universal quantification over a Polish space (here $Y$) — see Kechris, Classical Descriptive Set Theory, Theorem 37.1 on page 314 but this is precisely the set we are interested in: $$ \begin{align*} S &= \{f \in C(X,Y)\,:\,(\forall y \in Y)\;(f,y) \in A\} \\ & = \{f \in C(X,Y)\,:\,(\forall y \in Y)\,(\exists x \in X)\;(f,x,y) \in F\} \\ \end{align*} $$ so we've shown that $S \in \boldsymbol{\Pi}_{2}^1$.

share|cite|improve this answer
To see that $C(X,Y)$ is indeed Polish, observe first that it is second countable. Now let $X = \bigcup_n K_n$ be an exhaustion, i.e., $K_n \subset \operatorname{int}K_{n+1}$ where each $K_n$ is compact and let $d_Y$ be a bounded compatible metric. Put $d_n(f,g) = \sup_{x \in K_n}d_Y(f(x),g(x))$ and $d(f,g) = \sum_{n=1}^\infty 2^{-n} d_n(f,g)$. A sequence converges uniformly on compact sets if and only if it converges uniformly on each $K_n$, so $d$ is a compatible metric and it is clear that $d$ is a complete metric on $C(X,Y)$. – t.b. Jul 26 '12 at 8:01
Thanks! This is good, but I would still like something sharper. Regarding $C(X,Y)$, the hard part for me was seeing that it is separable. – Nate Eldredge Jul 26 '12 at 13:14
Oh, I'm sure that one can do quite a bit better than $\boldsymbol{\Pi}_{2}^1$ (I'll keep thinking about it). I see second countability of $C(X,Y)$ as follows: if $\mathscr{K}$ is a collection of compact sets containing a neighborhood base of each point in $X$ and $\mathscr{B}$ is a basis for the topology of $Y$ then the sets $N(K,B) = \{f \in C(X,Y)\,:\,f(K) \subset B\}$ with $K \in \mathscr{K}$ and $B \in \mathscr{B}$ are a subbasis for the compact-open topology. As both $X$ and $Y$ are second countable, choose both $\mathscr{K}$ and $\mathscr{B}$ to be countable and get a countable basis. – t.b. Jul 26 '12 at 14:01

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.