Prove that transfinite hierarchy of Borel sets will eventually stabilize at some $\lambda < \omega_1$

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 there exists $\lambda < \omega_1$ such that ${\bf \Sigma}_\alpha^0 = {\bf \Sigma}_{\alpha + 1}^0 = {\bf \Pi}_\alpha^0 = {\bf \Pi}_{\alpha + 1}$ for all $\alpha \ge \lambda$.

In below attempt, I successfully proved that there exist ordinals $\alpha,\beta,\gamma$ such that

$$\begin{cases} {\bf \Sigma}_\alpha^0 = {\bf \Sigma}_{\alpha + 1}^0\\ {\bf \Pi}_\beta^0 = {\bf \Pi}_{\beta + 1}^0\\ {\bf \Pi}_\gamma^0 = {\bf \Sigma}_{\gamma + 1}^0 \end{cases}$$

Next, I try to prove that there exists ordinal $\delta$ such that ${\bf \Sigma}_\delta^0 = {\bf \Sigma}_{\delta+ 1}^0 = {\bf \Pi}_\delta^0 = {\bf \Pi}_{\delta+ 1}$ by showing that $\forall \xi \ge \alpha:{\bf \Sigma}_\xi^0 = {\bf \Sigma}_{\alpha}^0$ and $\forall \xi \ge \beta:{\bf \Pi}_\xi^0 = {\bf \Pi}_{\beta}^0$ and $\forall \xi > \gamma:{\bf \Sigma}_\xi^0 = {\bf \Pi}_{\gamma}^0$. But I am stuck at this step.

Please shed me some light!

---

My attempt:

Lemma: ${\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$

It follows directly from our Lemma that $\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}$ for all ordinal $\alpha > 1$.

Assume the contrary that there is no ordinal $\alpha$ such that ${\bf \Sigma}_\alpha^0 = {\bf \Sigma}_{\alpha + 1}^0$. Then ${\bf \Sigma}_\alpha^0 \subsetneq {\bf \Sigma}_{\alpha + 1}^0$ for all ordinal $\alpha$. Let $\Theta$ be the Hartogs number of $\mathcal P(\mathcal P(\Bbb R))$. We define a function $\phi:\Theta \to \mathcal P(\mathcal P(\Bbb R))$ by $\phi(\alpha)={\bf \Sigma}_{\alpha + 1}^0 - {\bf \Sigma}_{\alpha}^0$. Clearly, $\phi$ is injective, leading to a contradiction. Hence there exists an ordinal $\alpha$ such that ${\bf \Sigma}_\alpha^0 = {\bf \Sigma}_{\alpha + 1}^0$. Similarly, there exists an ordinal $\beta$ such that ${\bf \Pi}_\beta^0 = {\bf \Pi}_{\beta + 1}^0$ and ${\bf \Sigma}_{\gamma + 1}^0 = {\bf \Pi}_\gamma^0$.

Answer 1

There is a much simpler proof that the Borel hierarchy stabilizes at $\omega_1$ (and a slightly more complicated argument gives that it doesn't stabilize at any $\alpha < \omega_1$). Here's the outline:

Prove that, since $\mathrm{cof}(\omega_1) = \omega_1$, $\boldsymbol{\Sigma}_{\omega_1}$ is a $\sigma$-algebra, i.e. closed under complements and countable unions.

Now prove that if $\boldsymbol{\Sigma}^0_{\alpha}$ is contained in a $\sigma$-algebra $\Sigma$, then $\boldsymbol{\Sigma}^0_{\alpha+1} \subseteq \Sigma$ as well.

Conclude that $\boldsymbol{\Sigma}^0_{\omega_1+1} = \boldsymbol{\Pi}^0_{\omega_1+1} = \boldsymbol{\Sigma}^0_{\omega_1} = \boldsymbol{\Pi}^0_{\omega_1}$.

---

Let's now turn to the question whether it could stabilize at $\alpha < \omega_1$.

Definition. Let $X \subseteq \mathbb{R} \times \mathbb{R}$. For $y \in \mathbb{R}$ we let $$ X_y := \{ x \in \mathbb{R} \mid (x,y) \in X \} $$

Definition. Let $\alpha < \omega_1$. $U \subseteq \mathbb{R} \times \mathbb{R}$ is universally $\boldsymbol{\Sigma}^0_{\alpha}$ if it is $\boldsymbol{\Sigma}^0_\alpha$ (as a subset of the Polish space $\mathbb{R} \times \mathbb{R}$ -- which is homeomorphic to $\mathbb{R}$) and for every $X \subseteq \mathbb{R}$ which is $\boldsymbol{\Sigma}^0_\alpha$ there is some $y \in \mathbb{R}$ such that $$ X = U_y. $$ Likewise for $\Pi^0_\alpha$.

Lemma. For every $\alpha < \omega_1$ there is some universally $\boldsymbol{\Sigma}^0_\alpha$ set $U$ and some universally $\boldsymbol{\Pi}^0_\alpha$ set $V$.

Proof (Hint). By an induction on $\alpha$. If $\alpha$ is a limit ordinal, pick $(\alpha_n \mid n < \omega)$ cofinal in $\alpha$ and use $y$ to code countable unions of elements that appear in $\boldsymbol{\Sigma}^0_{\alpha_n}$ for some $n$.

Lemma. Let $\alpha < \omega$. Then $\boldsymbol{\Sigma}^0_\alpha \neq \boldsymbol{\Pi}^0_\alpha$.

Proof. Let $U$ be universally $\boldsymbol{\Sigma}^0_\alpha$. Let $$ X =\{ x \in \mathbb{R} \mid (x,x) \not \in U \}. $$ Let $$ \rho \colon \mathbb R \to \mathbb R \times \mathbb R, x \mapsto (x,x). $$ $\rho$ is continuous and hence $$ X = \{ x \in \mathbb{R} \mid \rho(x) \in \mathbb{R} \times \mathbb{R} \setminus U \} = \rho^{1}[\mathbb{R} \times \mathbb{R} \setminus U] $$ is $\boldsymbol{\Pi}^0_{\alpha}$. (Use that $\boldsymbol{\Pi}^0_{\alpha}$ is closed under continuous substitution and that $\mathbb{R}$ is homeomorhpic to $\mathbb{R} \times \mathbb{R}$.)

By a diagonal argument, conclude that $X$ is not $\boldsymbol{\Sigma}^0_{\alpha}$. Q.E.D.

Answer 2

After three days of thinking, I have figured out an incomplete proof and posted it here.

---

Lemma 1: ${\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$

It follows directly from our Lemma 1 that $\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}$ for all ordinal $\alpha > 1$.

Assume the contrary that there is no ordinal $\alpha$ such that ${\bf \Sigma}_\alpha^0 = {\bf \Sigma}_{\alpha + 1}^0$. Then ${\bf \Sigma}_\alpha^0 \subsetneq {\bf \Sigma}_{\alpha + 1}^0$ for all ordinal $\alpha$. Let $\Theta$ be the Hartogs number of $\mathcal P(\mathcal P(\Bbb R))$. We define a function $\phi:\Theta \to \mathcal P(\mathcal P(\Bbb R))$ by $\phi(\alpha)={\bf \Sigma}_{\alpha + 1}^0 - {\bf \Sigma}_{\alpha}^0$. Clearly, $\phi$ is injective, leading to a contradiction. Hence there exists an ordinal $\alpha$ such that ${\bf \Sigma}_\alpha^0 = {\bf \Sigma}_{\alpha + 1}^0$. Similarly, there exists an ordinal $\beta$ such that ${\bf \Pi}_\beta^0 = {\bf \Pi}_{\beta + 1}^0$ and ${\bf \Sigma}_{\gamma + 1}^0 = {\bf \Pi}_\gamma^0$.

Lemma 2: $B \in {\bf \Sigma}_\alpha^0 \implies \Bbb R-B \in {\bf \Pi}_\alpha^0$ and $B \in {\bf \Pi}_\alpha^0 \implies \Bbb R-B \in {\bf \Sigma}_\alpha^0$ for all ordinal $\alpha$.

The assertion is trivially true for $\alpha=1$.

Let it hold for $\alpha$. We have $B \in {\bf \Sigma}_{\alpha+1}^0 \implies B=\bigcup_{n \in \mathbb N}B_n$ where $\forall n \in \mathbb N: B_n \in {\bf \Pi}^0_\alpha$ $\implies \Bbb R-B=\bigcap_{n \in \mathbb N}(\Bbb R-B_n)$ where $\forall n \in \mathbb N: \Bbb R-B_n \in {\bf \Sigma}^0_\alpha$. Hence $\Bbb R-B \in {\bf \Pi}_{\alpha+1}^0$. Similarly, $B \in {\bf \Pi}_{\alpha+1}^0 \implies \Bbb R-B \in {\bf \Sigma}_{\alpha+1}^0$.

Let it hold for all $\xi < \alpha$ where $\alpha$ is a limit ordinal. We have $B \in {\bf \Sigma}_{\alpha}^0 \implies B=\bigcup_{n \in \mathbb N}B_n$ where $\forall n \in \mathbb N: B_n \in \bigcup^0_{\xi < \alpha}{\bf \Pi}^0_\xi \implies \Bbb R-B=\bigcap_{n \in \mathbb N}(\Bbb R-B_n)$ where $\forall n \in \mathbb N:\Bbb R- B_n \in \bigcup^0_{\xi < \alpha}{\bf \Sigma}^0_\xi$. Hence $\Bbb R-B \in {\bf \Pi}_{\alpha}^0$. Similarly, $B \in {\bf \Pi}_{\alpha}^0 \implies \Bbb R-B \in {\bf \Sigma}_{\alpha}^0$.

As a consequence, $B \in {\bf \Sigma}_\alpha^0 \iff \Bbb R-B \in {\bf \Pi}_\alpha^0$ for all ordinal $\alpha$.

Lemma 3: ${\bf \Sigma}_\alpha^0 = {\bf \Sigma}_\beta^0 \iff {\bf \Pi}_\alpha^0 = {\bf \Pi}_\beta^0$.

• Case 1:$\Longrightarrow$

$B \in {\bf \Pi}_\alpha^0 \implies \Bbb R-B \in {\bf \Sigma}_{\alpha}^0 \implies \Bbb R-B \in {\bf \Sigma}_{\beta}^0 \implies \Bbb R-(\Bbb R-B) \in {\bf \Pi}_\beta^0 \implies B \in {\bf \Pi}_\beta^0$. Similarly, $B \in {\bf \Pi}_\beta^0 \implies B \in {\bf \Pi}_\alpha^0$. Hence ${\bf \Pi}_\alpha^0 = {\bf \Pi}_\beta^0$.

• Case 2:$\Longleftarrow$

The proof is similar to above reasoning.

Lemma 4: ${\bf \Sigma}_\alpha^0 = {\bf \Sigma}_{\alpha + 1}^0 \implies \forall \beta \ge \alpha: {\bf \Sigma}_\beta^0 = {\bf \Sigma}_{\alpha}^0$.

${\bf \Sigma}_{\alpha}^0 = {\bf \Sigma}_{\alpha}^0$ trivially holds.

Let ${\bf \Sigma}_\beta^0 = {\bf \Sigma}_{\alpha}^0$ holds. Then ${\bf \Pi}_{\beta+1}^0 = {\bf \Pi}_{\alpha+1}^0$ and thus ${\bf \Sigma}_{\beta+1}^0 = {\bf \Sigma}_{\alpha+1}^0={\bf \Sigma}_\alpha^0$.

Let ${\bf \Sigma}_\xi^0 = {\bf \Sigma}_{\alpha}^0$ holds for all $\alpha \le \xi <\beta$ where $\beta$ is a limit ordinal. It follows that ${\bf \Pi}_\xi^0 = {\bf \Pi}_{\alpha}^0$ holds for all $\alpha \le \xi <\beta$ and thus $\bigcup^0_{\xi < \beta}{\bf \Pi}^0_\xi=\bigcup^0_{\xi \le \alpha}{\bf \Pi}^0_\xi=\bigcup^0_{\xi < \alpha+1}{\bf \Pi}^0_\xi$. As a result, ${\bf \Sigma}^0_\beta =$ $\{\bigcup_{n \in \mathbb N}B_n \mid \forall n \in \mathbb N: B_n \in \bigcup^0_{\xi < \beta}{\bf \Pi}^0_\xi\} = \{\bigcup_{n \in \mathbb N}B_n \mid \forall n \in \mathbb N: B_n \in \bigcup^0_{\xi < \alpha +1}{\bf \Pi}^0_\xi\}={\bf \Sigma}^0_{\alpha + 1}.$

On the other hand, ${\bf \Sigma}_\alpha^0 = {\bf \Sigma}_{\alpha + 1}^0$. Hence, ${\bf \Sigma}_\beta^0 = {\bf \Sigma}_{\alpha}^0$.

Lemma 5: ${\bf \Sigma}_\alpha^0 = {\bf \Sigma}_{\alpha + 1}^0 \implies {\bf \Sigma}_\alpha^0 = {\bf \Pi}_\alpha^0$.

First, ${\bf \Sigma}_\alpha^0 = {\bf \Sigma}_{\alpha + 1}^0 \implies {\bf \Pi}_\alpha^0 = {\bf \Pi}_{\alpha+1}^0$.

Second, ${\bf \Sigma}_\alpha^0 \subseteq {\bf \Pi}_{\alpha +1}^0$ and ${\bf \Pi}_\alpha^0 \subseteq {\bf \Sigma}_{\alpha +1}^0$.

It follows that ${\bf \Sigma}_\alpha^0 \subseteq {\bf \Pi}_{\alpha +1}^0 = {\bf \Pi}_\alpha^0 \subseteq {\bf \Sigma}_{\alpha +1}^0$. On the other hand, ${\bf \Sigma}_\alpha^0 = {\bf \Sigma}_{\alpha + 1}^0$. Hence ${\bf \Sigma}_\alpha^0 = {\bf \Pi}_{\alpha +1}^0 = {\bf \Pi}_\alpha^0 = {\bf \Sigma}_{\alpha +1}^0$ and thus ${\bf \Sigma}_\alpha^0 = {\bf \Pi}_\alpha^0$.