Show that the Borel Hierarchy on $\mathbb{R}$ doesn't end at the first infinite ordinal?

Question

I know that there is a transfinite construction of the Borel sets, and, more generally, of the $\sigma$-algebra generated by a subset of $P(X)$ for any set $X$. This construction ends at the first uncountable ordinal, if I am not mistaken.

A mistake I have noticed in some of my peers is (perhaps through association with the much easier case for topological space generated by a subset) the assumption that one can make such a process terminating at the first countable ordinal. Of course, it is easy to shake and question this assumption, but I would like to have a practical example to show that it is irredeemably wrong.

To be more precise, it would be perhaps reasonable at first glance to assume the following:

Let $\mathcal{B}$ be the Borel $\sigma$-algebra on $\mathbb{R}$. Furthermore, define $B_0$ as the set of opens on $\mathbb{R}$, and define $B_{n+1}$ as $B_n$, plus the set of countable intersections of elements in $B_n$, plus the set of countable unions, plus the complementaries. It could be conjectured that $\mathcal{B} = \bigcup_{n=0}^\infty B_n$.

What I'm looking for is a proof that this conjecture is wrong, if possible by an example of a Borel set that isn't in any $B_n$.

Note: I think that there might be standardized notation to what I have called $B_n$, something to do with the Borel hierarchy, but I couldn't figure out what the correct notation would be, so I made up my own.

Answer 1

Asaf's answer exemplifies the point of departure from $\sigma$-algebras —and “universal” algebras with infinitary operations in general— from the customary realm of finitary operations: The union of an increasing sequence of infinitary algebras is not necessarily closed under the operations. And the fact that the first uncountable ordinal $\omega_1$ is regular (closed under limits of sequences, in this particular case) is what ensures that the union of an increasing transfinite sequence of $\sigma$-algebras with length $\omega_1$ is a $\sigma$-algebra. The same holds for any infinitary algebra with operations with countable arity.

A particular example of Borel subset not belonging to any of the $B_n$ would necessarily be contrived (all natural examples from analysis are in $B_5$ or so, and then jump into analytic sets). Such examples can be found in Kechris' Classical Descriptive Set Theory, Sect. 23.G.

For describing one of them, consider the Cantor ternary set $\mathcal{C}\subset\mathbb{R}$. There is a natural map (a homeomorphism, in fact) from $G :\{0,1\}^{\mathbb{N}}\to \mathcal{C}$ by using binary-to-ternary expansions. Now we can code total orders $R$ on $\mathbb{N}$ by functions $f_R:\mathbb{N}\to \{0,1\}$: $$ n \mathrel{R} m \iff f_R(2^n\cdot 3^m) = 1, $$ where $f_R(k) = 0$ for every $k$ such that $6\nmid k$. Finally, our set can be defined as $$ G\bigl(\{f_R\in 2^{\mathbb{N}} : R \text{ is a well-order of } \mathbb{N} \text{ in type}<\omega^\omega\}\bigr). $$

Answer 2

If you proved that $B_n$ is a proper subset of $B_{n+1}$, then this is easy. Let's start with a naive approach, and then fix it if it breaks down.

Let $X_n\in B_{n+1}\setminus B_n$, then $X=\bigcup X_n$ is a Borel set, as a countable union of Borel sets, and it is not in any of the $B_n$'s.

But why isn't $X$ in any of the $B_n$'s? What if we took, by pure chance, a descending sequence of sets, so that $X=B_0$?

Well, in that case, add the assumption that each $X_n$ is chosen to be pairwise disjoint from $X_k$ for $k<n$. This is not hard to arrange: simply require that $X_n\subseteq (n,n+1)$.

So why is it that $X$ is not in $B_n$ for any $n$? Well, because $(n,n+1)$ are all open sets, if $X\in B_n$, then $X\cap (n+1,n+2)\in B_n$ as well, but this is just $X_{n+1}$ which we assume is not in $B_n$.