# Complexity of the set of surjective continuous functions

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$.

Thanks!

-

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.

-
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$.

-
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