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.

  • 1
    $\begingroup$ $\omega^\omega$ is lightface Borel... $\endgroup$ May 10, 2012 at 17:59
  • $\begingroup$ @CarlMummert Good point, thanks. I'll edit my question to more accurately represent what I'm thinking about. $\endgroup$ May 10, 2012 at 18:19
  • $\begingroup$ Project $A \cap (\omega^\omega \times B)$. $\endgroup$
    – user83827
    May 10, 2012 at 21:01
  • $\begingroup$ @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}}$? $\endgroup$ May 11, 2012 at 21:48
  • $\begingroup$ 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$). $\endgroup$
    – user83827
    May 11, 2012 at 22:08

1 Answer 1


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

My guess is no but it's my best attempt to find an interesting Q in the area.

  • $\begingroup$ Hi Peter. Yes, this is basically what I had in mind. Thanks. $\endgroup$ May 12, 2012 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.