MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 4 down vote accepted

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."

share|cite|improve this answer
Concerning Kechris's remark. My fault. Kechris means examples from analysis or topology, I edited my comment appropriately. Thanks. – Konstantin Slutsky Dec 7 '09 at 17:58

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.

share|cite|improve this answer

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.

share|cite|improve this answer

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.

share|cite|improve this answer
I'd say $\mathbb{Q}$ is level 2, as a $\Sigma^{0}_{2}$ set. – sdcvvc Dec 7 '09 at 17:37
whoops good point – Sam Lichtenstein Dec 7 '09 at 17:39

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.