From lightface $\Sigma^1_1$ to boldface $\mathbf\Delta^1_1$

Fix some standard Polish space, e.g. Baire's space. It's a simple observation that every $\Delta^1_1$ is also $\mathbf\Delta^1_1$. It is the same observation that $\Sigma^1_1$ becomes $\mathbf\Sigma^1_1$.

Is it possible that there is some $A\in\Sigma^1_1$ is not $\Delta^1_1$, but is $\mathbf\Delta^1_1$? If this is true, is there any good characterization of this phenomenon? Can $\Sigma^1_1$ be replaced by $\Sigma^1_n$, or even $\Sigma^2_n$?

• I wasn't sure about the tags, should [computability] be added or something like that? Maybe [general-topology]? Oct 14 '12 at 16:01
• I'm not so sure about general topology, but computability seems reasonable to me. Oct 15 '12 at 0:42
• @Carl: I see. I'll leave it until the morning, and if no arguments in favor of the topology tag are given -- I'll remove it. Oct 15 '12 at 0:50
• Hm. I'm surprised to see a downvote after over two years. I wonder what happened. Jan 25 '15 at 16:53
• Interesting. I'm used to getting arbitrary downvotes and no answer gets upvotes (so the downvotes are really targeted at me as a user). At least whoever did that saw value in your answer! Jan 25 '15 at 17:04

Yes, it is straightforward that there is a lightface $\Sigma^1_1$ class that is not lightface $\Delta^1_1$ but is boldface $\Delta^1_1$. For example just take any set $A \subseteq \mathbb{N}$ that is lightface $\Sigma^1_1$ but not lightface $\Delta^1_1$ and let the class be $X = \{A\}$, i.e. defined by the formula $\phi(B) \equiv B = A$. This is a boldface $\Pi^0_1$ definition of the class $X$ with $A$ as a parameter (because equality between reals is $\Pi^0_1$). One concrete example of such an $A$ is the set of $e \in \mathbb{N}$ such that $\phi_e$ is not a computable well ordering.

By taking $A$ to be of sufficiently high complexity (e.g. not definable in third-order arithmetic, or not in $L$) we can extend the result as in the last part of the question. The point of boldface is that you can use any parameter you want, even if the parameter itself is not definable.

• D'oh. Obviously for singletons it holds! I have no idea how I missed that (and to think that I had this question on my mind for quite some time...) is there a less-trivial example (i.e. a set which has size continuum to begin with)? Oct 15 '12 at 0:42
• Well you could let $X$ be the class of $B$ that are of the form $C \oplus A$ for some $C$ and that fixed $A$. This is a perfect class that is still boldface $\Pi^0_1$. This immediately suggests all other sorts of arithmetical variants of the original $X$. Oct 15 '12 at 0:44
• Ah. Indeed. Is there an inverse example, a lightface $\Sigma^1_1$ which is not boldface $\mathbf\Delta^1_1$? Oct 15 '12 at 0:47
• Yes, the set I mentioned is the classic example. The set $\mathcal{O} \subseteq \mathbb{N}$ of computable well orderings is lightface $\Pi^1_1$ and not boldface $\Sigma^1_1$. So the complement is what you are looking for. Or the set $A \subseteq \omega^\omega$ of graphs of well orderings is also lightface $\Pi^1_1$ and not boldface $\Sigma^1_1$. Oct 15 '12 at 0:49
• Well, I don't really care about the particular class. I just wanted something whose complexity is not simplified when passing to boldface. Either way, many thanks. I have to admit that now I am really embarrassed that I didn't remember that $0^\#$ is a $\Delta^1_3$ and $\mathbf\Pi^0_1$ as an example... Oct 15 '12 at 0:52

For a slightly less trivial answer in the case of $\Sigma^1_2$ notice that $L \cap \mathbb{R}$ is a $\Sigma^1_2$ set that is not $\Delta^1_2$, but if it is countable (e.g., if $0^\sharp$ exists) then it is $\Delta^1_2(x)$ for every real $x$ coding $\omega_1^L$, uniformly in $x$. So ordinal parameters suffice in a sense.

There is a recursion theory characterization of this kind of phenomenon. Just fix a $\Pi^1_1$-set $A$. By Gandy-Spector Theorem, $A$ can be viewed as an r.e. set. If all the reals in $A$ can be enumerated into $A$ below some fixed countable ordinal, then it is Borel. Otherwise, by the boundedness, $A$ is not Borel.

This can be generalized to $\Pi^1_{2n+1}$ under $PD$.