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

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.

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

• Any reason for downvoting this question? – LE Anh Dung Feb 22 '19 at 8:12
• I don't think the result is true, I think each step in the hierarchy up to $\omega_1$ adds new Borel sets. $\lambda=\omega_1$ certainly works, but it's not $<\omega_1$. (I don't understand the downvote either) – Maxime Ramzi Feb 22 '19 at 9:02
• The claim as written is false: the Borel hierarchy goes all the way to $\omega_1$. Here's a quick explanation of why you might expect this to be true. Suppose $\lambda<\omega_1$ is a limit ordinal and for every $\alpha<\lambda$ there is an $X_\alpha\in\bf\Sigma^0_\alpha\setminus\Pi^0_\alpha$. Then let $(\alpha_i)_{i<\omega}$ be cofinal in $\lambda$ (since $\lambda<\omega_1$), let $Y_n$ by $X_{\alpha_n}$ "ported onto" the open interval $(n, n+1)$ (via some homeomorphism $\mathbb{R}\cong(n,n+1)$), and think about $Y=\bigcup_{n\in\omega} Y_n$. Of course that's not a proof, but it should help. – Noah Schweber Feb 22 '19 at 13:23
• (As to why it stops at $\omega_1$: think about cofinality ...) – Noah Schweber Feb 22 '19 at 13:26
• @NoahSchweber : I was aware that it didn't stop before $\omega_1$ but I had never seen the heuristic you just gave, thank you for that ! – Maxime Ramzi Feb 22 '19 at 14:11

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.

• I am really grateful for your dedicated help @Stefan! – LE Anh Dung Feb 25 '19 at 2:08
• @LeAnhDung You're very welcome! – Stefan Mesken Feb 25 '19 at 2:08

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