Descriptive set theory: Borel hierarchy

In 1905 Henri Lebesgue asked whether the projection of a Borel subset of R^2 onto R must be Borel. In 1916 the 19-year-old Mikhail Suslin found a counterexample -- and opened an entire universe of projective sets studied to this day.

• Borel hierarchies appear in program verification: Sigma^0_2 (safety) and Pi^0_2 (liveness) are precise classes in temporal logic specification hierarchies.
• TLA+ (Microsoft, Lamport) works with these notions for distributed system correctness.

Borel hierarchy

Emile Borel in 1898 defined Borel sets as the smallest sigma-algebra containing open sets. The hierarchy of classes Sigma^0_alpha, Pi^0_alpha, Delta^0_alpha for countable ordinals alpha < omega_1 classifies complexity: Sigma^0_1 = open, Pi^0_1 = closed, Sigma^0_2 = F_sigma, Pi^0_2 = G_delta. This hierarchy is the foundation of descriptive set theory and mirrors the Kleene hierarchy in computability.

Analytic sets and projective hierarchy

Analytic sets Sigma^1_1 are continuous images of Borel sets. Suslin (1916) showed that the projection of a Borel subset of R^2 onto R need not be Borel. This opened the projective hierarchy: Sigma^1_n, Pi^1_n, Delta^1_n. Determinacy of projective games (Martin, Steel, Woodin) was a central result of the 1980s.

Key results

• Borel hierarchy: Sigma^0_alpha = countable unions of Pi^0_<alpha sets.
• Suslin's theorem: Delta^1_1 = Borel sets.
• Sigma^1_1 = analytic = projections of Borel. All are Lebesgue measurable.
• Regularity of Sigma^1_2 and above depends on axioms (PD, large cardinals).