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.

  • 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

2

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.

  • 0
    Hi Peter. Yes, this is basically what I had in mind. Thanks.2012-05-12