# How to show $\Sigma_{\omega}^{0}$ (not ) exhaust the Borel sets?

Let$(X,\mathscr{T})$ be a topological space. The collection of Borel sets in $X$ is the smallest $\sigma$-algebra containing the open sets in $\mathscr{T}$.

$\Sigma_{\omega}^{0}$ is inductively defined by the following collection of subsets of $X$. $$\Sigma_{1}^{0} = \{U : U \subseteq X \text{ is open}\}$$ $$\Pi^{0}_n = \{\lnot{A}: A \in \Sigma_{n}^{0} \}= \lnot{\Sigma_{n}^{0}}$$ $$\Sigma_{\alpha}^{0} = \{\bigcup_{k < \omega} A_k: A_k \in \Pi_{\beta}^{0}, \text{for some } \beta < \alpha \}$$

My first question is: Does $\Sigma_{\omega}^{0}$ exhaust the Borel sets?

My second question is: If the answer of the first question is positive, is $\Sigma_{\omega}^{0} = \Sigma_{\alpha}^{0}$, for any $\alpha > \omega$?

• You didn't define $\Sigma_{\alpha}^{0}$ for a limit ordinal $\alpha$. What exactly do you mean by $\Sigma_{\omega}^{0}$? Do you mean $\Sigma_{\omega}^{0}=\{\bigcup_{k}A_{k}:A_{k}\in\Pi_{n}^{0}\,\,\text{for}\,\, \text{some}\,\,n\in\omega\}$? – T. Eskin Feb 24 '13 at 11:23
• @ThomasE.：Yes. Frankly speaking, I'm just beginning to touch on these things, and I thought it is a convention, or at least there exists one. Please correct me, if I got it wrong. – Metta World Peace Feb 24 '13 at 11:28
• Answer to the second question is trivial: $P(\mathbb{R})$ has cardinality $2^\omega$, so if the hierarchy doesn't stabilizes at some point, then after $(2^\omega)^+$ steps you would have more than $2^\omega$ subsets of $\mathbb{R}$. – Damian Sobota Feb 24 '13 at 12:25
• @DamianSobota: You're right. Thank you. Indeed, it's a non-decreasing transfinite sequence and bounded from above. – Metta World Peace Feb 24 '13 at 12:30
• And if the space is uncountable, all classes in hierarchy under $\omega_1$-level are distinct. – Damian Sobota Feb 24 '13 at 12:44

If $X$ is an uncountable Polish space, then $\Sigma_\alpha^0\subsetneq\Sigma_{\alpha+1}$ for all $0<\alpha<\omega_1$, thus the hierarchy cannot stabilize under the $\omega_1$ level. This inequality can be shown using so-called universal sets: $\mathcal{U}\subset2^\omega\times X$ is universal for $\Sigma_\alpha^0$ if $\mathcal{U}\in\Sigma_\alpha^0(2^\omega\times X)$ and $\Sigma_\alpha^0(X)=\{\mathcal{U}_t: t\in2^\omega\}$, where $\mathcal{U}_t=\{x\in X: (t,x)\in\mathcal{U}\}$ for $t\in2^\omega$. Similarly for the class $\Pi_\alpha^0$.

The theorem states that given $X$ being an uncountable Polish space for all $0<\alpha<\omega_1$ there exist universal sets for $\Sigma_\alpha^0(X)$ and $\Pi_\alpha^0(X)$.

Now, as the corollary we obtain the following: if $X$ is an uncountable Polish space and $0<\alpha<\omega_1$, then $\Sigma_\alpha^0(X)\neq\Pi_\alpha^0(X)$, hence $\Delta_\alpha^0(X)\subsetneq\Sigma_\alpha^0(X)\subsetneq\Delta_{\alpha+1}^0(X)$ and similarly for $\Pi_\alpha^0$. The proof goes as follows (a contrario):

Wlog we can assume $2^\omega\subset X$ (X is an uncountable Polish space!). If $\Sigma_\alpha^0(X)=\Pi_\alpha^0(X)$, then $\Sigma_\alpha^0(2^\omega)=\Sigma_\alpha^0(X)|2^\omega=\Pi_\alpha^0(X)|2^\omega=\Pi_\alpha^0(2^\omega)$. Let $\mathcal{U}$ be universal for $\Sigma_\alpha^0(2^\omega)$. Put $A=\{t\in2^\omega: (t,t)\not\in\mathcal{U}\}$. We have: $A\in\Pi_\alpha^0(2^\omega)=\Sigma_\alpha^0(2^\omega)$, so for some $t\in2^\omega$: $A=\mathcal{U}_t$, which is a contradiction.

(This is kind of Cantor diagonalization argument.)

You can easily show that if $X$ is a Polish space, then $\text{Borel}(X)=\Sigma_{\omega_1}^0(X)$ (just show that $\Sigma_{\omega_1}^0(X)$ is a $\sigma$-algebra).