The Ha-sets

By recursion on the ordinal |a |, we associate with each a e S₁ a set H_a c N so that:

• (H1) H₁ = N,
• (H2) H₂b = Hb, and
• (H3) if a = 3 ? 5^e, then x e H_a (x)₀ e H_e(x)i.

This is exactly the definition in Kleene [19], except that he gave it for a e O C S₁. The earlier Davis [4] gave an almost identical definition (for a e S₁) which differs only in the details of the coding, and Mostowski [39] gave a somewhat different and abbreviated version which seems to avoid ordinal codes, cf. Sect.5.3.3.

Davis [4] proves that for a, b e S₁, |a|, |b| < of²,

so that, in particular,

and asks if every constructive ordinal has this uniqueness property. This turned out to be a difficult problem and led some five years later to one of the first spectacular results in the area¹¹:

Theorem 5.2.2 (Spector [47]) For alia, b e S_1;

In particular, |a| = | =^ d(H_a) = d(H_b) and if we set da = d(H_a), then {d% : % < o₁} is an increasing sequence of Turing degrees of length o₁.

Much more was done with constructive ordinals and the H_a-sets in the fifties and sixties, especially by Kleene who used them as his main tool for studying the hyperarithmetical sets. We will not go much into this here, for good reasons that we will explain in due course; but before we dig into our main topic, we need to discuss briefly some important, early work that we will not cover in detail.