Higher-rank Borel sets

Question

What are interesting, illustrative examples of Borel sets, situated in Borel hierarchy higher than $\Sigma^{0}_{2}$ /$\Pi^{0}_{2}$?

Answer 1

The Borel hierarchy is, of course, strictly increasing at every step, so there will be sets of every countable ordinal rank. Furthermore, all of these sets are relatively concrete, obtained as countable unions of sets having lower rank. But you asked for natural examples, so let me give a few.

1) The collection of true statements of number theory, in the ring of integers Z. This is well known to have complexity Sigma^0_omega, which is a large step up from the complexity you mentioned. This is, of course, a light-face notion. The corresponding bold-face notion would be truth in arbitrary countable structures. That is, the set of pairs (A,phi), where A is a first-order structure and phi is true in A. This has complexity Sigma^0_omega for the same reason as (1). (I regard this as a highly natural example, but Kechris' remark was about natural examples specifically from topology and analysis.)

2) The set of countable graphs with finitely many connected components. This has complexity Sigma^0_3, since you must say: there is a finite set of vertices, for all other vertices, there is a path to one of them.

There are numerous other statements about finiteness that also arise this way.

3) The set of (reals coding) finitely generated groups. This is Sigma^0_3, since you say: there is a finite set in the group, such that for all other elements of the group, there is a generating word.

4) finitely-generated other structures, etc. etc.

5) The set of pairs (A,p), such that A is a real and p is a Turing machine program with oracle A that accepts all but finitely many input strings. Sigma^0_3, since "There is a finite set of strings, for all other strings, there is a computation showing them to be accepted."

Answer 2

This is certainly a standard and very well-known reference, but let me metnion Section 23 of Kechris's Classical Descriptive Set Theory which has lots of examples of $\Pi_3^0, \Sigma_3^0$ and some more complicated Borel sets. Here are some of them

{$x \in \mathbb{N}^\mathbb{N} : \lim x(n) = \infty $} is $\Pi_3^0$ complete.

The set of $A \subset \mathbb{N}$ of density 0 is $\Pi_3^0$ in $2^{\mathbb{N}}$.

If $X$ is a unit ball in $c_0$ then the set of sequence in $X^\mathbb{N}$ that weakly converges (in $c_0$) is $\Pi_4^0$ complete.

In the above reference there are many more natural examples. There is also a comment at the end of the section that natural examples from topology or analysis of Borel sets of complexity level 5 or higher are not known.

Answer 3

My personal favourite is the (F-sigma-delta) set of all real numbers x for which limit as n -> infinity sin(n! pi x) exists. There is a natural way to recursively iterate this construction to get Borel additive subgroups of reals at all finite levels of Borel hierarchy.

Answer 4

A set is $\Sigma^0_2$ iff it is an $F_\sigma$ set, that is, a countable union of closed sets. The standard counterexample is $\mathbb{R}\setminus\mathbb{Q}$. (One can show this using the Baire Category Theorem. See the wonderful book Counterexamples in Analysis by Gelbaum and Olmsted, p. 91.) Dually, it follows that $\mathbb{Q}$ is not $G_\delta$, that is, not $\Pi^0_2$. These seem like illustrative examples, although whether they are interesting seems somewhat subjective.