4
$\begingroup$

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
    $\omega^\omega$ is lightface Borel...2012-05-10
  • 0
    @CarlMummert Good point, thanks. I'll edit my question to more accurately represent what I'm thinking about.2012-05-10
  • 0
    Project $A \cap (\omega^\omega \times B)$.2012-05-10
  • 0
    @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}}$?2012-05-11
  • 0
    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$).2012-05-11
  • 0
    @ccc Yes, I meant properly $\mathbf{\Sigma^{1}_{1}}$. I've edited to reflect that. Is my question clear now?2012-05-11
  • 0
    It is sort of clear, but I don't know what sort of answer you are expecting, beyond "it depends on the relationship between $A$ and $B$." If, say, every section of $A$ is countable then the projection via $B$ will be Borel irrespective of the choice of $B$. Of course it could be that for some choices of $B$, $A \cap (\omega^\omega \times B)$ is empty while for others it has properly $\mathbf{\Sigma^1_1}$ projection. In terms of general claims, I don't think there's much more you can say except that the projection is $\mathbf{\Sigma^1_1}$. (This is all boldface.)2012-05-12

1 Answers 1