# Lebesgue [28] and Mostowski [39]

The situation is actually quite similar to one that came up in classical analysis at the turn of the last century. Recall the definition of Borel subsets of N in (2) of Sect. 5.1.4. In modern notation, the Borel hierarchy { ? 0 : S< ?21} (on N) is defined by setting

and then by recursion on the countable ordinals,

These definitions were first given (for the reals) by Lebesgue [28] who proved (among many other fascinating and much deeper things) that

As it happens, most of the important applications of the Borel sets to analysis (including measure theory and integration) use only the definitions and (5.28), which is easy and handy for proving properties of Borel sets by ordinal induction. The fine structure of the Borel hierarchy is a very interesting and much-studied topic but not as fundamental as B.

The definition of hyperarithmetical sets in Mostowski [39] is inspired by the classical theory of Borel sets, although he does not cite Lebesgue [28] or any other “classical” work. It is a difficult paper to read, basically an outline: he appears to define his hierarchy directly on ordinals rather than notations (which is not possible with the tools he uses) and he refers cryptically to (what must be) effective grounded recursion as “a rather developed technique which we do not wish to presuppose here”. Section9 of Kleene [19] supplies the details which are needed to make Mostowski’s construction rigorous and comes up with a precise characterization of the intended hierarchy: in modern notation

It is immediate from the definition that

Moreover, ?a depends only on the ordinal a by the Spector Uniqueness Theorem 5.2.2 and

The hierarchy {?a : a e 51} has been studied even less that the Borel hierarchy { ? j j < ^}, partly because the topic is not easy. It is obvious that it is a hierarchy, since every ?a has a complete set (H2a); but to prove (for example) that every ?a is closed under conjunction you must use effective grounded recursion, and for more difficult questions these proofs become very complex. In any case, we will not work with it here: for what we will do, the identification HYP = B suffices and yields simpler proofs.