Borel set that is not countable union or intersection of open or closed sets

In this previous question, one can read the following:

It is important to keep in mind, by the way, that Borel sets are more than just countable unions and intersections of open and closed sets.

I tried to find an explicit example of a Borel set $A$ that can't be written only using a finite number of the following operations :

• countable unions of open or closed sets ;
• countable intersections of open or closed sets.

I know that there are examples of Borel sets that are neither $G_{\delta}$ nor $F_{\sigma}$, but I could write them using the two operations above.

According to this article on Borel hierarchy (if I understood it well), a Borel set can be obtained by a countable number of the two operations above.

• When you say "countable union of open or closed sets", do you mean a countable union of sets of which some are open and some are closed? – Henning Makholm Jan 16 '16 at 11:58
• @Henning Makholm : yes, that's it. – Watson Jan 16 '16 at 13:50

Your question isn't entirely clear, because "countable unions of open or closed sets" and "countable intersections of open or closed sets" aren't "operations", they are sets. I suppose you mean "countable unions" and "countable intersections", and what you're asking for is essentially a set that is not at a finite level ($\mathbf{\Sigma}_n^0$ or $\mathbf{\Pi}_n^0$) of the (boldface) Borel hierarchy.

In fact, there is an explicit construction of a set at every level ($\mathbf{\Sigma}_\xi^0$ or $\mathbf{\Pi}_\xi^0$) of the Borel hierarchy that does not belong to any earlier level: this is constructed by considering a "universal" such set, i.e., roughly one whose sections give every possible set of that level. This is done for example in Kechris, Classical Descriptive Set Theory (1995, Springer GTM 156), §22.A, specifically theorems 22.3 and 22.4. The construction is indeed explicit, though it is not very transparent.

Here's how I think I can simplify it slightly. Instead of working in $\mathbb{R}$, it is much better to work in the Cantor space $\mathcal{C} = 2^{\mathbb{N}}$ of binary sequences (note that this is homeomorphic to the standard Cantor set). A crucial fact is that $\mathcal{C}^2$ is homeomorphic to $\mathcal{C}$ (by separating a binary sequence into its even and odd terms), and in fact even $\mathcal{C}^{\mathbb{N}}$ is homeomorphic to $\mathcal{C}$ (using a bijection between $\mathbb{N}^2$ and $\mathbb{N}$).

Start with a universal open set in $\mathcal{C}^2$: to get one, consider an enumeration of finite binary sequences, and consider the set $U$ of those $(x,y) \in \mathcal{C}^2$ such that, for some $i$ for which $y(i)=1$, the sequence $x$ starts with the $i$-th finite binary sequence in the enumeration. Since the set $V_i$ of elements $x\in\mathcal{C}$ which start with the $i$-th finite binary sequence gives an open basis $(V_i)$ of $\mathcal{C}$, this is a "universal" open set in the sense that every open set of $\mathcal{C}$ is $\{x : (x,y) \in U\}$ for some $y \in \mathcal{C}$. The complement $F$ of $U$ gives a universal closed set.

Now we want to construct a universal $F_\sigma$, i.e., $\mathbf{\Sigma}_2^0$ set. To do this, consider the set of $(x,(y_n)) \in \mathcal{C} \times \mathcal{C}^{\mathbb{N}}$ such that $(x,y_n)$ (an element of $\mathcal{C}^2$) belongs to $F$ for some $n$: since every closed set of $\mathcal{C}$ can be obtained as $\{x : (x,y) \in F\}$ for some $y \in \mathcal{C}$, every $F_\sigma$ (=countable union of closed sets) can be obtained as a union of $\{x : (x,y_n) \in F\}$ for some sequence $y_n$ of elements of $\mathcal{C}$, that is, as the set of $x$ for which $(x,(y_n))$ belongs to the set I just described. By using a homeomorphism between $\mathcal{C}^{\mathbb{N}}$ and $\mathcal{C}$ we get a universal $F_\sigma$ set in $\mathcal{C}^2$. Its complement is a universal $G_\delta$ (=$\mathbf{\Pi}_2^0$) set.

Redo the same construction as above, using the universal $G_\delta$ set instead of $F$ to get a universal $\mathbf{\Sigma}_3^0$ set. Then do it again and again: this gives a sequence $U =: B_1, B_2, B_3, B_4,\ldots$ where $B_n$ is a universal $\mathbf{\Sigma}_n^0$ set in $\mathcal{C}^2$.

Finally, do the construction one last time but with $n$ varying: that is, consider the set of $(x,(y_n)) \in \mathcal{C} \times \mathcal{C}^{\mathbb{N}}$ such that, for some $n$, the element $(x,y_n)$ (of $\mathcal{C}^2$) belongs to the complement $B_n$. Bring it to $\mathcal{C}^2$ (or to $\mathcal{C}$) using homeomorphisms: call this $B_\omega$.

Note that this construction is completely explicit: the axiom of choice was never used, for example, and given the choice of a few finistic bijections (between $\mathbb{N}^2$ and $\mathbb{N}$ or finite binary sequences and $\mathbb{N}$), the set is completely specified.

Now why can't the universal $\mathbf{\Sigma}_n^0$ set $B_n$ be $\mathbf{\Pi}_n^0$? This is just a diagonal argument: if $B_n$ were $\mathbf{\Pi}_n^0$ then the complement of its diagonal $\{y : (y,y) \not\in B_n\}$ would be $\mathbf{\Sigma}_n^0$, and this clearly contradicts the universality of $B_n$. So $B_n$ is no earlier than stated in the Borel hierarchy, and $B_\omega$ is a Borel set which cannot be constructed by finitely using countable unions or intersections.