# Is every element of $\omega_1$ the rank of some Borel set?

It is well known that we can obtain the $$\sigma$$-algebra of Borel subsets of $$2^{\omega}$$ in the following way: Let $$B_0$$ be the collection of all open subsets of $$2^{\omega}$$. For $$\alpha=\beta+1$$, let $$B_{\alpha}$$ be the collection of complements of elements and unions of countable sequences of $$B_{\beta}$$. For $$\lambda$$ a limit ordinal, let $$B_{\lambda}=\bigcup_{\alpha<\lambda}B_{\alpha}$$. Then $$B_{\omega_1}$$ is the Borel-$$\sigma$$-algebra on $$2^{\omega}$$. This motivates the definition of the "Borel rank" of a Borel set by $$\operatorname{rk}_B(x)=\min\{\alpha\;|\;x\in B_{\alpha}\}$$ My question now is the following: Does there exist, for any successor $$\beta+1<\omega_1$$, a Borel set with Borel rank $$\beta+1$$? I am also interested in the resolution of this question in models of ZF.

• – Wojowu Nov 12 '20 at 13:58
• This is equivalent to asking whether no $B_\alpha$ equals $B_{\omega_1}$ for any $\alpha<\omega_1$. The answer is known to be positive (at least for ZFC) but I'm not aware of the argument. – YCor Nov 12 '20 at 13:58
• Actually that $B_{\omega_1}$ is a $\sigma$-algebra seems to use some countable choice (DC or AC, I'm not sure): indeed according to A. Caicedo's answer to the linked question ZF is consistent with "$B_{\omega_1}$ is not a $\sigma$-algebra". – YCor Nov 12 '20 at 14:01
• In $\mathsf{ZF}$ it is consistent that every set of Reals is the countable union of countable sets, each such set is a countable union of singletons, so every set in $\Bbb R$ is $F_{\sigma\sigma}$ and we get $P(\Bbb R)=\mathbf{\Sigma^0_4}=\mathbf{\Pi}^0_4$.It is also possible to have longer Borel hierarchies in $\mathsf{ZF}$, for example of length $\omega_2$ – Alessandro Codenotti Nov 12 '20 at 14:07
• In $\mathsf{ZFC}$ the standard way of showing that the Borel hierarchy has length $\omega_1$ is through the construction of so called "universal sets" for the various levels of the Borel hierarchy, see chapter 22 of Kechris Classical Descriptive Set Theory – Alessandro Codenotti Nov 12 '20 at 14:16

In $$\mathsf{ZFC}$$ the Borel hierarchy of an uncountable Polish space $$X$$ has length exactly $$\omega_1$$, meaning that $$\mathbf{\Sigma}^0_\xi(X)\neq\mathbf{\Pi}^0_\xi(X)$$ for all $$\xi<\omega_1$$.

The standard way of proving this is through the construction of so called $$\mathcal C$$-universal sets for $$\mathbf{\Sigma}^0_\xi(X)$$ and $$\mathbf{\Pi}^0_\xi(X)$$, where $$\mathcal C$$ is the Cantor space and a set $$A\subseteq \mathcal C\times X$$ is $$\mathcal C$$-universal for $$\mathbf{\Sigma}^0_\xi(X)$$ if:

1. $$A\in\mathbf{\Sigma}^0_\xi(\mathcal C\times X)$$.
2. Every $$\mathbf{\Sigma}^0_\xi$$ set in $$X$$ can be written as $$\{x\in X\mid (y,x)\in A\}$$ for some $$y\in \mathcal C$$.

Assuming such sets exists consider $$X=\mathcal C$$ (wlog, since $$\mathcal C$$ embeds in all uncountable Polish spaces) and suppose for a contradiction that for some $$\xi<\omega_1$$,$$\mathbf{\Sigma}^0_\xi(X)=\mathbf{\Pi}^0_\xi(X)$$. Let $$A$$ be a $$\mathcal C$$-universal set for $$\mathbf{\Sigma}^0_\xi(\mathcal C)$$ and consider $$B\subseteq\mathcal C$$ defined by $$c\in B\iff (c,c)\not\in A$$. Then $$B$$ is the complement of a $$\mathbf{\Sigma}^0_\xi$$ set, which makes $$B$$ a $$\mathbf\Pi^0_\xi$$ set, but since $$\mathbf{\Sigma}^0_\xi(X)=\mathbf{\Pi}^0_\xi(X)$$, $$B$$ is also a $$\mathbf\Sigma^0_\xi$$ set. So for some $$y\in \mathcal C$$, $$B=\{x\mid (y,x)\in A\}$$, by universality of $$A$$, which is a contradiction since now $$y\in B\iff y\not\in B$$.

For a construction of such universal sets see 22.3 in Kechris book Classical Descriptive Set Theory.

In $$\mathsf{ZF}$$, as it often happens, the situation is awful. It is consistent with $$\mathsf{ZF}$$ that every set of reals is the countable union of countable sets, and since every countable set is the union of its (closed) singletons, this means that every set of reals is consistently $$F_{\sigma\sigma}$$, so unless I'm off by one converting between notations this means that $$\mathbf\Sigma^0_4$$ and $$\mathbf\Pi^0_4$$ are consistently equal. But the opposite can also happen, Miller proved that the Borel hierarchy on the reals can have length $$\omega_2$$ in $$\mathsf{ZF}$$ for example.

• Also, from the last sentence of Miller's abstract: "We also show that assuming a large cardinal hypothesis there are models of ZF in which the Borel hierarchy is arbitrarily long." Amazing! I wasn't aware of this until today. – Will Brian Nov 12 '20 at 14:42
• @Will: And there you went through life thinking that ZF can really put an upper bound on stuff? Ha! :-) – Asaf Karagila Nov 12 '20 at 14:48
• Is there a reason you link to Miller's personal page instead of providing a proper citation, by the way? – Asaf Karagila Nov 12 '20 at 20:32