Take the 2-minute tour ×
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.

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

share|improve this question
    
I wasn't sure about the tags, should [computability] be added or something like that? Maybe [general-topology]? –  Asaf Karagila Oct 14 '12 at 16:01
    
I'm not so sure about general topology, but computability seems reasonable to me. –  Carl Mummert 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. –  Asaf Karagila Oct 15 '12 at 0:50
add comment

3 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
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)? –  Asaf Karagila 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$. –  Carl Mummert 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$? –  Asaf Karagila 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$. –  Carl Mummert 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... –  Asaf Karagila Oct 15 '12 at 0:52
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

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.