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

567 Views Asked by At

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

3

There are 3 best solutions below

5
On BEST ANSWER

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
On

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.

0
On

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