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.

Fix $A, B \in \mathbf{\Delta}_{1}^{1}$ (i.e. they're Borel). Is the statement $A \subseteq B$ generally only $\mathbf{\Pi}^{1}_{1}$ (at best)? Of course, it's $\mathbf{\Pi}^{1}_{1}$ via $\forall x[x \in A \rightarrow x \in B]$.

EDIT: Here's my situation in more detail. For each continuous function $f\in C[0,1]$, let $S_f \subseteq [0,1]$ be a $\Sigma_{3}^{0}(f)$ set (that is, a set that is lightface sigma zero three in $f$) and for each $e\in \omega$, the set $Q_{e}\subset \mathbb{Q}$ is finite and computable (uniformly in $e$). I want to know the complexity of $\exists e[S_{f}\subseteq Q_{e}]$. In general, must I have a set (i.e. real number) quantifier to express that subset relation?

share|improve this question
    
Something about the way I phrased this seems weird to me. If you agree, let me know and I'll try to clean it up. Also let me know if you have a suggestion. –  Quinn Culver Jul 9 '12 at 16:00
add comment

2 Answers

up vote 1 down vote accepted

Even in the simple case where all of the $Q_e$ are empty, the complexity you asked about can be complete $\Pi^1_1$. To say $S_f\subseteq\varnothing$ is to say that $f$ is outside the projection of the binary relation $R(f,g)$ defined as $g\in S_f$. Even for quite low complexity relations $R$, the projection can be complete $\Sigma^1_1$, so the complement can be complete $\Pi^1_1$. Here "quite low complexity" depends on the space $g$ ranges over. If it were the Baire space $\omega^\omega$ then closed sets would be complex enough. For your situation, where the space is $[0,1]$, one needs to go a little higher in the Borel hierarchy, but I believe $\Pi^0_2$ (i.e., $G_\delta$) is enough.

share|improve this answer
add comment

I'm not sure if this is completely correct, but I have always thought of a particular statement $A$ being in a class $\Gamma$ (at least in the context of descriptive set theory) if the set $\{x\in X; A(x)\}$ is in $\Gamma$. So, for example, "$(x_n)$ has infinite zeros" is $\Pi^0_2$ in $2^\omega$ since $\{(x_n)\in 2^\omega ; (x_n) \mbox{ has infinite zeros}\}$ is $\Pi^0_2$.

In that sense, you must be careful with your statement. If you are looking at the statement as a statement in your original space (lets call it X) of which $A,B$ are subsets, then the statement will be open, since it doesn't have free variables in your space, so is either true or false.

If on the other side, you are looking at the statement in $\mathcal{P}(X)$ , you will need $X$ to be countable for $\mathcal{P}(X)$ to be Polish, in which case your statement will be closed as a subset of $\mathcal{P}(X)\times\mathcal{P}(X)$.

They could be other Polish spaces in which your statement could be more complicated, at least a priori. But you will need to make sure that the space of subsets which you are taking (say, the domain for $A$ and $B$) could be given a Polish topology. For a nice example (the subset relation will still be closed) consider the compact sets of a Polish space with the Vietoris topology, refer to chapter 4.F in Kechris' Classical Descriptive Set Theory.

share|improve this answer
    
I've not thought about it carefully yet, but I think you're right and this is what I meant by "...the way I phrased this seems weird to me." –  Quinn Culver Jul 9 '12 at 20:29
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.