Complexity of subset relation on Borel Sets

Question

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?

Answer 1

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.

Answer 2

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.