Nontrivial Borel Sets

We are covering Measure Theory and the Borel Algebra $$B(\mathbb{R})$$ and I am trying to find a nontrivial example of a Borel Set. With the notions of $$F_\sigma$$ and $$G_\delta$$ sets, I am wondering if we can find a borel set which is not the countable union or countable intersection of $$F_\sigma$$ or $$G_\delta$$ sets.

Mainly, I want to know how "bad" can a set in $$B(\mathbb{R})$$ be?

• Very. Constructing non Borel sets is nontrivial, and by en.wikipedia.org/wiki/Solovay_model, constructing non measurable sets requires AoC. Aug 21, 2019 at 17:08
• The situation is better described at en.wikipedia.org/wiki/Borel_hierarchy but I don't have the ability to decipher much of what is written there. Aug 21, 2019 at 17:13
• @MrigankaBasuRoyChowdhury To be fair, the OP is asking about complicated Borel sets, and these exist provably in ZF alone. Indeed, ZF + a tiny fragment of choice proves that there are non-Borel sets, even providing an explicit example of such! Aug 21, 2019 at 18:09

The relevant topic here is descriptive set theory. The standard texts on the subject are Moschovakis and Kechris; I tend to prefer the latter, especially as a first introduction unless you're already dead-set on becoming a logician, but the former is freely available on the author's website.

The class of Borel sets is vastly more complicated than that. The key point is the Borel hierarchy (and the fact that it doesn't collapse).

The finite levels of the Borel hierarchy are more or less what one would expect:

• A set is $$\Sigma^0_1$$ iff it is open, and a set is $$\Pi^0_1$$ iff it is closed.

• A set is $$\Sigma^0_{n+1}$$ iff it is the union of countably many $$\Pi^0_n$$ sets, and a set is $$\Pi^0_{n+1}$$ iff it is the intersection of countably many $$\Sigma^0_n$$ sets.

At this point it's a good exercise to check that a set is $$\Sigma^0_n$$ iff its complement is $$\Pi^0_n$$.

This notation extends the "F/G" notation you're used to - for example, the $$F_\sigma$$ sets are exactly the $$\Sigma^0_2$$ sets, and the $$G_\delta$$ sets are exactly the $$\Pi^0_2$$ sets. As we go further you'll see why this notation is much better.

It turns out that this hierarchy is nontrivial:

$$(*)\quad$$ For each $$n\in\mathbb{N}$$, there is a $$\Sigma^0_n$$ set which is not $$\Pi^0_n$$ (and conversely).

This isn't easy to prove, though, and relies on the notion of a universal set for these complexity classes (see e.g. this old answer of mine for a summary of this notion).

But it gets worse - there are Borel sets which are not $$\Sigma^0_n$$ or $$\Pi^0_n$$ for any $$n\in\mathbb{N}$$! This follows quickly from $$(*)$$. Basically, for each $$n\in\mathbb{N}$$ let $$A_n$$ be a $$\Sigma^0_{n+1}$$ set which is not $$\Sigma^0_n$$ with $$A_n\subseteq [2n, 2n+1]$$ (note that $$\mathbb{R}\cong (2n,2n+1)$$), and let $$A=\bigcup_{n\in\mathbb{N}}A_n.$$ If $$A$$ were $$\Sigma^0_n$$, then $$A_n$$ would also be $$\Sigma^0_n$$ (since the "pieces" of $$A$$ are "nicely separated"), which isn't the case.

So we need to keep going:

• A set is $$\Sigma^0_\omega$$ iff it is a union of countably many sets each of which is $$\Pi^0_n$$ for some $$n\in\mathbb{N}$$, and a set is $$\Pi^0_\omega$$ iff it is an intersection of countably many sets each of which is $$\Sigma^0_n$$ for some $$n\in\mathbb{N}$$.

We can keep on going like this, and e.g. define $$\Sigma^0_{\omega+17}$$, $$\Pi^0_{\omega\cdot 2+43}$$, $$\Sigma^0_{\omega^2+\omega+1}$$, and so on. That is, we can define the Borel hierarchy through the countable ordinals. And it turns out that we need all of these:

For every countable ordinal $$\alpha$$, there is a $$\Sigma^0_\alpha$$ set which is not $$\Pi^0_\alpha$$ (and conversely).

At the same time it's a good exercise to check that any countable union of sets, each of which is $$\Sigma^0_\alpha$$ for some countable $$\alpha$$, is also $$\Sigma^0_\alpha$$ for some countable $$\alpha$$. So we get:

The Borel sets are exactly those sets which are $$\Sigma^0_\alpha$$ (or $$\Pi^0_\alpha$$) for some countable ordinal $$\alpha$$.

That is, the Borel hierarchy stops at $$\omega_1$$. Note that we can define levels of the Borel hierarchy past the countable ordinals, the point is just that we don't get anything new: the pointclass $$\Sigma^0_{\omega_1+17}$$ is the same as the pointclass $$\Sigma^0_{\omega_1}$$. (A "pointclass" is basically a complexity class of sets of reals - "open," "closed," "$$F_\sigma$$," and so on are examples of pointclasses.)

• Incidentally, you might be wondering about that superscript. There are indeed such things as $\Sigma^m_n$ sets for general $m$ and $n$, but they get quite complicated. Roughly speaking, you can think of them in terms of definability, with $n$ measuring the number of quantifiers in the definition of the set and $m$ measuring the type of quantifiers in the definition of the set, and $\Sigma$ corresponding to $\exists$ and $\Pi$ corresponding to $\forall$ as far as the first quantifier goes. But this is rather difficult to make precise, so let's ignore it for now. Aug 21, 2019 at 18:07
• So this hierarchy that you are describing is or is similar to repeatedly taking unions of intersections of unions of intersections, etc. a finite number of times. Then all borel sets can be written in this union of intersections of unions of intersections... ? Is that at least the main idea of it? Aug 21, 2019 at 18:18
• @AndrewShedlock "So this hierarchy that you are describing is or is similar to repeatedly taking unions of intersections of unions of intersections, etc. a finite number of times" No, not a finite number of times - that's the whole point of the second section of my answer! The Borel sets aren't exhausted until we continue through all the countable ordinals. Aug 21, 2019 at 18:27
• Ahhh, thank you for highlighting that! Aug 21, 2019 at 18:31
• I am confused about the following: you mention that $F_\sigma = \Sigma_2^0$. However, sets in $\Sigma_2^0$ are countable unions of $\Sigma_1^0$ (open) sets, but $F_\sigma$ is the collection of countable unions of closed sets. What have I misunderstood? Jul 12, 2020 at 14:35

As an addendum to Noah Schweber's answer, here's a concrete example of a set that is in both $$\Sigma_3^0$$ and $$\Pi_3^0$$ (and hence in $$\Delta_3^0$$) but neither in $$\Sigma_2^0$$ nor in $$\Pi_2^0$$. The set of all real numbers in $$[0,1]$$ whose base-$$10$$ representations contain (a) infinitely many $$1$$'s and (b) finitely many digits that are not in $$\{1,2\}$$.

Requirement (a) gives a set in $$\Pi_2^0$$ that is not in $$\Sigma_2^0$$, while requirement (b) gives a set in $$\Sigma_2^0$$ that is not in $$\Pi_2^0$$. Finite unions and intersections of sets in $$\Sigma_n^0$$ and $$\Pi_n^0$$ produce sets that are provably in $$\Delta_{n+1}^0 = \Sigma_{n+1}^0 \cap \Pi_{n+1}^0$$.