Given the transfinite hierarchy of Borel sets, prove that ${\bf \Sigma}_\alpha^0 \subseteq {\bf \Sigma}_{\alpha+1}^0$ for all ordinal $\alpha < \beta$

Question

We define the transfinite hierarchy of Borel sets $\langle {\bf \Sigma}^0_\alpha, {\bf \Pi}^0_\alpha \rangle_{\alpha \in \rm{Ord}}$ as follows:

$$\begin{aligned} &\begin{cases} {\bf \Sigma}^0_1 &= \{B \subseteq \mathbb R \mid B\text{ is open}\}\\ {\bf \Pi}^0_1 &= \{B \subseteq \mathbb R \mid B\text{ is closed}\}\end{cases}\\ &\begin{cases} {\bf \Sigma}^0_{\alpha + 1} &= \{\bigcup_{n \in \mathbb N}B_n \mid \forall n \in \mathbb N: B_n \in {\bf \Pi}^0_\alpha\}\\ {\bf \Pi}^0_{\alpha + 1} &= \{\bigcap_{n \in \mathbb N}B_n \mid \forall n \in \mathbb N: B_n \in {\bf \Sigma}^0_\alpha\}\end{cases} \text{ for all ordinal } \alpha\\ &\begin{cases} {\bf \Sigma}^0_\alpha &= \{\bigcup_{n \in \mathbb N}B_n \mid \forall n \in \mathbb N: B_n \in \bigcup^0_{\xi < \alpha}{\bf \Pi}^0_\xi\}\\ {\bf \Pi}^0_\alpha &= \{\bigcap_{n \in \mathbb N}B_n \mid \forall n \in \mathbb N: B_n \in \bigcup^0_{\xi < \alpha}{\bf \Sigma}^0_\xi\} \end{cases} \text{ for all limit ordinal } \alpha \end{aligned}$$

Prove that ${\bf \Sigma}_\alpha^0 \subseteq {\bf \Sigma}_\beta^0 \quad {\bf \Sigma}_\alpha^0 \subseteq {\bf \Pi}_\beta^0 \quad {\bf \Pi}_\alpha^0 \subseteq {\bf \Pi}_\beta^0 \quad {\bf \Pi}_\alpha^0 \subseteq {\bf \Sigma}_\beta^0$ for all ordinals $\alpha < \beta$

---

Is my proof correct? Or have I missed something that makes an inductive argument necessary? Any suggestion is greatly appreciated. Thank you for your help!

---

My attempt:

It follows directly from the construction of ${\bf \Sigma}^0_{\alpha + 1}$ and ${\bf \Pi}^0_{\alpha + 1}$ that ${\bf \Pi}^0_\alpha \subseteq {\bf \Sigma}^0_{\alpha + 1}$ and ${\bf \Sigma}^0_\alpha \subseteq {\bf \Pi}^0_{\alpha + 1}$. Hence ${\bf \Pi}_\alpha^0 \subseteq {\bf \Sigma}_\beta^0$ and ${\bf \Sigma}_\alpha^0 \subseteq {\bf \Pi}_\beta^0$ for all $\alpha < \beta$.

We know that every open set is a countable union of open intervals with rational endpoints and that every open interval is a countable union of closed intervals. Hence every open set is a countable union of closed intervals (and thus closed sets). It follows by De Morgan's laws that every closed set is a countable intersection of open set. Thus ${\bf \Sigma}_1^0 \subseteq {\bf \Sigma}_2^0$ and ${\bf \Pi}_1^0 \subseteq {\bf \Pi}_2^0$.

We proceed to prove that ${\bf \Sigma}_\alpha^0 \subseteq {\bf \Sigma}_{\alpha+1}^0$ and ${\bf \Pi}_\alpha^0 \subseteq {\bf \Pi}_{\alpha+1}^0$ for all $\alpha$ by transfinite induction. We previously prove it for $\alpha=1$. Let the assertion hold for $\alpha$, i.e. ${\bf \Sigma}_\alpha^0 \subseteq {\bf \Sigma}_{\alpha+1}^0$ and ${\bf \Pi}_\alpha^0 \subseteq {\bf \Pi}_{\alpha+1}^0$. It follows that $\{\bigcap_{n \in \mathbb N}B_n \mid \forall n \in \mathbb N: B_n \in {\bf \Sigma}^0_\alpha\} \subseteq \{\bigcap_{n \in \mathbb N}B_n \mid \forall n \in \mathbb N: B_n \in {\bf \Sigma}^0_{\alpha+1}\}$ and thus ${\bf \Pi}_{\alpha+1}^0 \subseteq {\bf \Pi}_{\alpha+2}^0$.

Similarly, $\{\bigcup_{n \in \mathbb N}B_n \mid \forall n \in \mathbb N: B_n \in {\bf \Pi}^0_\alpha\} \subseteq \{\bigcup_{n \in \mathbb N}B_n \mid \forall n \in \mathbb N: B_n \in {\bf \Pi}^0_{\alpha+1}\}$ and thus ${\bf \Sigma}_{\alpha+1}^0 \subseteq {\bf \Sigma}_{\alpha+2}^0$. This completes the proof.

Answer 1

You didn't prove that $\Sigma^0_\alpha$ $\subseteq$ $\Sigma^0_{\alpha + 1}$, $\Pi^0_\alpha$ $\subseteq$ $\Pi^0_{\alpha+1}$ for all ordinal $\alpha$ since what you have done is mere induction for all natural numbers, not transfinite induction. To prove this statement by transfinite induction, you need to show that if $\alpha$ is a limit ordianl and it holds for all $\xi \lt \alpha$, then it holds for $\alpha$.(and the argument you have given above cannot be applied to this case)

Instead of seperating the orignal statement into two parts and proving them independently of each oher, one can prove the whole statement at once and I personally find it easier. I give my proof below.

we proceed by induction on $\beta$

1) $\beta$ = 2

trivial

2) $\beta$ = $\xi$ + 1

and $\Sigma^0_\alpha$ $\subseteq$ $\Sigma^0_\xi$, $\Sigma^0_\alpha$ $\subseteq$ $\Pi^0_\xi$, $\Pi^0_\alpha$ $\subseteq$ $\Sigma^0_\xi$, $\Pi^0_\alpha$ $\subseteq$ $\Pi^0_\xi$ holds for all $\alpha$ $\lt$ $\xi$

$\alpha$ $\lt$ $\beta$ implies $\alpha$ $\le$ $\xi$

i) $\alpha$ $\lt$ $\xi$

$\Sigma^0_\alpha$ $\subseteq$ $\Sigma^0_\xi$ $\subseteq$ $\Pi^0_\beta$

$\Sigma^0_\alpha$ $\subseteq$ $\Pi^0_\xi$ $\subseteq$ $\Sigma^0_\beta$

$\Pi^0_\alpha$ $\subseteq$ $\Sigma^0_\xi$ $\subseteq$ $\Pi^0_\beta$

$\Pi^0_\alpha$ $\subseteq$ $\Pi^0_\xi$ $\subseteq$ $\Sigma^0_\beta$

ii) $\alpha$ = $\xi$

$\Sigma^0_\alpha$ $\subseteq$ $\Pi^0_\beta$

$\Pi^0_\alpha$ $\subseteq$ $\Sigma^0_\beta$

ii-1) $\xi$ = $\gamma$ +1 (succesor ordinal)

$\Sigma^0_\xi$ = {$\bigcup_{n\in\omega}B_n$ : $B_n \in \Pi^0_\gamma$} $\subseteq$ {$\bigcup_{n\in\omega}B_n$ : $B_n \in \Pi^0_\xi$} = $\Sigma^0_{\xi +1}$

$\Pi^0_\xi$ = {$\bigcap_{n\in\omega}B_n$ : $B_n \in \Sigma^0_\gamma$} $\subseteq$ {$\bigcap_{n\in\omega}B_n$ : $B_n \in \Sigma^0_\xi$} = $\Pi^0_{\xi +1}$

ii-2) $\xi$ : limit ordinal

$\Sigma^0_\xi$ = {$\bigcup_{n\in\omega}B_n$ : $B_n \in \Pi^0_\gamma$ for some $\gamma \lt \xi$} $\subseteq$ {$\bigcup_{n\in\omega}B_n$ : $B_n \in \Pi^0_\xi$} = $\Sigma^0_{\xi +1}$

$\Pi^0_\xi$ = {$\bigcap_{n\in\omega}B_n$ : $B_n \in \Sigma^0_\gamma$ for some $\gamma \lt \xi$} $\subseteq$ {$\bigcap_{n\in\omega}B_n$ : $B_n \in \Sigma^0_\xi$} = $\Pi^0_{\xi +1}$

hence

$\Sigma^0_\alpha$ $\subseteq$ $\Sigma^0_\beta$ and

$\Pi^0_\alpha$ $\subseteq$ $\Pi^0_\beta$

3) $\beta$ : limit ordinal (not zero)

and $\Sigma^0_\alpha$ $\subseteq$ $\Sigma^0_\xi$, $\Sigma^0_\alpha$ $\subseteq$ $\Pi^0_\xi$, $\Pi^0_\alpha$ $\subseteq$ $\Sigma^0_\xi$, $\Pi^0_\alpha$ $\subseteq$ $\Pi^0_\xi$ holds for all $\alpha$ $\lt$ $\xi$, $\xi$ $\lt$ $\beta$

then

$\alpha$ $\lt$ $\beta$ ($\alpha$ $\lt$ $\xi$ for some $\xi$ $\lt$ $\beta$) implies

$\Sigma^0_\alpha$ $\subseteq$ $\Pi^0_\beta$

$\Sigma^0_\alpha$ $\subseteq$ $\Pi^0_\xi$ $\subseteq$ $\Sigma^0_\beta$

$\Pi^0_\alpha$ $\subseteq$ $\Sigma^0_\xi$ $\subseteq$ $\Pi^0_\beta$

$\Pi^0_\alpha$ $\subseteq$ $\Sigma^0_\beta$

the induction step is now completed.

$\therefore$ $\Sigma^0_\alpha \subseteq \Sigma^0_\beta$, $\Sigma^0_\alpha$ $\subseteq \Pi^0_\beta$, $\Pi^0_\alpha \subseteq \Sigma^0_\beta$, $\Pi^0_\alpha \subseteq \Pi^0_\beta$ for all ordinals $\alpha \lt \beta$