8
$\begingroup$

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$?

  • 0
    Interesting. I'm used to getting arbitrary downvotes and no answer gets upvotes (so the downvotes are really targeted at me as a user). $A$t least whoever did that saw value in your answer!2015-01-25

3 Answers 3

5

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.

  • 0
    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...2012-10-15
2

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.

1

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$.