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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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|cite|improve this answer

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|cite|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

Your Answer


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.