1
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Any reason for downvoting this question? $\endgroup$ – Abstract Analysis Feb 22 at 8:12
  • 2
    $\begingroup$ 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) $\endgroup$ – Max Feb 22 at 9:02
  • 3
    $\begingroup$ 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. $\endgroup$ – Noah Schweber Feb 22 at 13:23
  • 1
    $\begingroup$ (As to why it stops at $\omega_1$: think about cofinality ...) $\endgroup$ – Noah Schweber Feb 22 at 13:26
  • 1
    $\begingroup$ @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 ! $\endgroup$ – Max Feb 22 at 14:11
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I am really grateful for your dedicated help @Stefan! $\endgroup$ – Abstract Analysis Feb 25 at 2:08
  • $\begingroup$ @LeAnhDung You're very welcome! $\endgroup$ – Stefan Mesken Feb 25 at 2:08
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.