MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

I am taking a course in descriptive set theory, and the exam is approaching on Sunday. In the framework of proving that for an uncountable Polish space $X$ the following holds: $\Delta^0_\alpha(X)\subsetneqq\Sigma^0_\alpha(X),\Pi^0_\alpha(X)\subsetneqq\Delta^0_\beta(X)$.

We did not only prove that there is a set which is $\Sigma^0_\alpha\setminus\Pi^0_\alpha$ but also proved that for every uncountable Polish space there are no $\Delta^0_\alpha$-universal sets based on any Polish space.

The proof is very simple that for $X$ there is no universal set based on $X$ itself, as well for $\alpha>2$ the proof is quite simple. For $\alpha=2$ the proof given to us goes through great lengths in a rather complex proof.

Is there a rather general and relatively simple statement which does not separate the cases $\alpha=2$ and $\alpha>2$?

(I could not find the general theorem in either Kechris nor Moschovakis, but only for the case we wish to base the universal set on $X$)

Edit: I am somewhat under the impression that this theorem has not been published before. My teacher claims that it is unlikely that a unified argument will hold for $\alpha\ge 2$ and separation must be made. I'm still not 100% convinced.

share|cite|improve this question

Hi. Here's the proof I've learned. It does not separate the cases $\alpha=2$ and $\alpha>2$. I hope I am not misunderstanding your question.

Theorem: Let $X$ be an uncountable Polish space. Then for any $\alpha<\omega_1$, there is a set $A\in \Sigma^0_{\alpha} \backslash \Pi^0_{\alpha}$. There is also for each $\alpha<\omega_1$ a set in $\Delta^0_{\alpha} \backslash \bigcup_{\beta<\alpha} \Sigma^0_{\beta} $

Proof: Let $X$ be an uncountable Polish space. The theorem is quick in the case $\alpha=1$ since if every open set was also closed then every point and every subset of $X$ is open which gives $X$ the discrete topology. But $X$ was Polish. Let $\alpha>1$. Recall that is $X$ is uncountable Polish then there is an embedding of $2^{\omega}$ into $X$. So there is a subspace $C \subseteq X$ homeomorphic to the Cantor space. $C$ has to be closed in $X$. Since having a universal set implies non-self-duality and by the existence of universal sets, there is a set $A\subseteq C$ which is $ \Sigma^0_{\alpha} $ but not $ \Pi^0_{\alpha} $ in the subspace topology on $C$. So in $X$, $A$ is the intersection of $ \Sigma^0_{\alpha} $ set and a closed set so it is $ \Sigma^0_{\alpha} $. If $A$ were also $\Pi^0_{\alpha} $ then $A=A \cap C$ would also be $ \Pi^0_{\alpha} $ in the subspace topology on $C$ which is a contradiction. For the second part, let $2\leq \alpha$. We show there is an $A \subseteq 2^{\omega}$ which is in $\Delta^0_{\alpha}$ but not in any $\Sigma^0_{\beta}$ for any $\beta<\alpha$. If $\alpha$ is a successor, say $\alpha=\beta+1$ then let $A\subseteq 2^{\omega}$ in $\Sigma^0_{\beta} \backslash \Pi^0_{\beta}$ and let $B \subseteq 2^{\omega}, B\in \Pi^0_{\beta} \backslash \Sigma^0_{\beta} $ . Define $C\subseteq 2^{\omega}$ such that we have $C(x) \leftrightarrow (x(0)=0 \wedge x(i+1)\in A \forall i) \vee (x(0)=1 \wedge x(i+1)\in B \forall i$. Then $C \in \Delta^0_{\alpha}$

share|cite|improve this answer
You meant $\alpha<\omega_1$ in that last part of the theorem statement? Since $\alpha<1\Rightarrow\alpha=0$... :-) – Asaf Karagila Oct 9 '11 at 20:27
Yes, thank you :) – Carlo Von Schnitzel Oct 9 '11 at 21:16
Closely reading your answer it seems that you prove that $\Sigma^0_\alpha\neq\Pi^0_\alpha$ and for $\beta<\alpha$ we have $\Sigma^0_\alpha\subsetneq\Delta^0_\beta$. This is not what I asked about. My question is why for $\alpha>1$ there is no $\Delta^0_\alpha$ subset $A\subseteq X\times X$ such that for every $x\in X$ the cut $\lbrace y\mid (x,y)\in A\rbrace$ is a $\Delta^0_\alpha$ set, and for every $\Delta^0_\alpha$ set $Y\subseteq X$ there is some $x\in X$ such that $\lbrace x\rbrace\times Y\subseteq A$. – Asaf Karagila Oct 9 '11 at 22:36

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.