Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
$\omega^\omega$ is lightface Borel... –  Carl Mummert May 10 '12 at 17:59
    
@CarlMummert Good point, thanks. I'll edit my question to more accurately represent what I'm thinking about. –  Quinn Culver May 10 '12 at 18:19
    
Project $A \cap (\omega^\omega \times B)$. –  user83827 May 10 '12 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}}$? –  Quinn Culver May 11 '12 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$). –  user83827 May 11 '12 at 22:08
show 2 more comments

1 Answer

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.

share|improve this answer
    
Hi Peter. Yes, this is basically what I had in mind. Thanks. –  Quinn Culver May 12 '12 at 15:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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