# Projecting onto (lightface) Borel sets

Suppose $A \subseteq \omega^{\omega} \times \omega^{\omega}$ is Borel. If we project $A$ onto $\omega^\omega$, we get a $\mathbf{\Sigma^{1}_{1}}$ set $\{y: \exists x (y,x) \in A\}$. What if we project it via some Borel set $B\subseteq \omega^{\omega}$? I.e. is $\{y: (\exists x\in B) \; (y,x)\in A\}$ Borel? What about if $B$ is lightface Borel?

I suppose these results are standard, but I can't seem to find them in the literature. I'd prefer a hint over a full solution, and references to the literature will also be accepted (and appreciated).

EDIT 1. As Carl pointed out in the comments, since $\omega^{\omega} \in \Delta^{0}_{0}$ (that's lightface), the answer to both my questions is NO. But here's the intuition I was trying to capture. Quantifying over $\omega^\omega$ is "harder" than quantifying over $\omega$. I was thinking, then, that quantifying over something "simpler" (e.g. a $\Sigma^{0}_{2}$ set) would be simpler. But I guess I was mistaken since $\omega^{\omega} \in \Delta^{0}_{0}$, which is as simple as can be. However, there certainly are cases where quantifying over a Borel set does make things simpler, e.g. when the Borel set is countable. Thus I now have new questions: if $B \subseteq \omega^\omega$ is an uncountable Borel set, is the set $\{y: (\exists x \in B)\; (y,x)\in A\}$ necessarily properly $\mathbf{\Sigma^{1}_{1}}$? What if $B$ is lightface Borel?

EDIT 2. Okay, here's specifically what I'm interested in. It is well known that the set $\mathrm{DIFF}:=\{f \in C[0,1] : \forall x \in [0,1]\; f'(x) \text{ exists}\}$ is $\mathbf{\Pi^{1}_{1}}$ complete in $C[0,1]$ (see Kechris' Classical Descriptive Set Theory, 33.d). That it is $\mathbf{\Pi^{1}_{1}}$ holds because $\{(f,x): f'(x) \text{ exists}\}$ is easily shown to be $\mathbf{\Pi^{0}_{3}}$, and $\mathrm{DIFF}$ is the projection of this set onto $C[0,1]$. What about $\mathrm{DIFF_{MLR}}:=\{f \in C[0,1] : \forall x \in \mathrm{MLR}\; f'(x) \text{ exists}\}$, where $\mathrm{MLR}$ is the collection of Martin-Löf randoms in $[0,1]$? Please only give me a hint, since I'm new to descriptive set theory and want to learn this. Of course, even if you don't know the answer, ideas will be appreciated.

• $\omega^\omega$ is lightface Borel... May 10, 2012 at 17:59
• @CarlMummert Good point, thanks. I'll edit my question to more accurately represent what I'm thinking about. May 10, 2012 at 18:19
• Project $A \cap (\omega^\omega \times B)$. May 10, 2012 at 21:01
• @ccc Are you saying that it's possible to find a Borel $A$ such that the projection of $A\cap (\omega^{\omega} \times B)$ is properly $\mathbf{\Sigma^{1}_{1}}$? May 11, 2012 at 21:48
• I guess I misunderstood your question. Certainly $\{y : (\exists x \in B) (y,x) \in A\}$ is analytic, as it is the projection of the Borel set $A \cap (\omega^\omega \times B)$. If you are asking whether something is properly $\mathbf{\Sigma^1_1}$ then maybe you can clarify the question? (But in response to your last comment, yes, if $B$ is uncountable Borel then there is in fact a Borel subset $A \subseteq \omega^\omega \times B$ whose projection is not Borel simply because $B$ is Borel isomorphic to $\omega^\omega$). May 11, 2012 at 22:08

Obviously not since $B=\omega^\omega$ is both uncountable and lightface Borel but yet the projection of (A,B) onto B merely gives A which, as a borel set, is not properly boldface $\Sigma^1_1$
A more interesting question is what condition on $A,B$ guarantees the projection is properly $\Sigma^1_1$. Or to make it a little nicer how about this:
Is there a nice condition on $(A, B)$ such that the projection of $A$ onto $B$ is either very simple (say somehow no more complex than A) or properly $\Sigma^1_1$.