# The Kleene [22] HYP hierarchy

This is perhaps the deepest and certainly the most difficult technical work of Kleene on hyperarithmetical sets.[1]

Theorem 5.3.12 (Kleene [22]) If the monotone operator A on P(N) is defined by (5.52) below, then

i

Even without the definition of A, a hierarchy of the form A '? 4 < A on HYP is more satisfactory than hierarchies like (5.29), because it is constructed without reference to any codings: there is no need for results like Spector’s Uniqueness Theorem to establish coding invariance. The specific operator A that we define next also gives a novel understanding of HYP and yields many interesting applications.

Definitions with Range and Basis F

with в = P1,---,Pm ^ F and an arithmetical Q; it is ^1 with basis F if

with в e F and an arithmetical Q; and it is A1 with range or basis F if both P and its negation - P are SJ with range or basis F respectively.

If P (x) is SJ with basis F, then it is also SJ with range F, clearly. The converse is not true: because every nj relation is Sj with range HYP by the Spector-Gandy Theorem 5.3.11, while

by Kleene’s HYP-Quantiflcation Theorem 5.3.10 (1)—and Theorem 5.3.4, of course, the inclusion A1 c HYP being basic to all this work. We let[2]

It is clear from (5.51) that A(HYP) = HYP, and so the least fixed point A of A is included in HYP. For the rest of (5.48), Kleene needs to show that

• (1) HYP c A, and
• (2) if n < % < «1, then An C A%.

For (1), he proves (in effect) that

with Sa defined in (5.29). The key idea for (2) is to use the ramified analytical hierarchy comprising the iterates of the monotone operator

on P(N). Kleene shows that if % < m1, then An % c HYP; and so if k(A) < m1, then HYP = A would be a fixed point of An which contradicts the Spector-Gandy Theorem. Both proofs are by effective grounded recursion and require more detailed, delicate formulations of (1) and (2) to go through.

To formulate one of the simplest and most elegant characterizations of HYP that comes out of Theorem 5.3.12, recall the two-sorted structure of analysis N2 = (N, N, 0, 1, +, •, ap) we used in Sect. 5.3.4. Its formal language A2 has variables x, y,...,s, t,over N and а, в,... over N andsymbolsO, 1, +, ?, ap.Its standard interpretation is N2. We are interested in general, m-models of A2-theories in which the number variables range over N and the function variables over some F c N, and for any formula ф we will write

where W p is the universal closure of p. As usual, we identify sets with their representing functions in such models,

An A2-formula p is arithmetical if no function quantifiers occur in it. As usual, by p(x, y, в, y) we will denote any formula in which the variables x, y, в, y may occur free but do not necessarily include all the variables which occur free in p. We consider three axiom schemes in A2:

Arithmetical comprehension. With arithmetical p(s) (in which a does not occur free),

A1 -comprehension. With arithmetical p(s, y), f(s, y) (in which a does not occur free),

S^-Choice. With arithmetical p(s, a, y),[3]

Clearly, (Aj-Comp) (A^-Comp), and Kreisel [26] verified that[4]

Theorem 5.3.13 (1) (Kleene [22], Kreisel [26]) HYP is the least model of (Aj- Comp).

(2) (Kreisel [26]) HYP satisfies (S-Choice).

Proof (1) If A is Sj1 with range HYP, then it is nj by the HYP-Quantification Theorem 5.3.10 (1); and if A is also nj with range HYP, then it is Aj and hence HYP. This proves that HYP satisfies (A 1-Comp), if we apply it to the set A = {s : (3y)p(s, y)} and then take a = xA. To see that it is the least model of (A 1-Comp), assume that F satisfies (A 1-Comp) and prove by induction on f that A c F using Theorem 5.3.12.

(2) Suppose that (У,у)(Эа e HYP)(3y e HYP)p(s, y, a) with an arithmetical p and set

This is in П, so by the Kreisel Uniformization Theorem 5.3.9, it is uniformized by a П1 relation P*(s, i); we check easily that some a e HYP satisfies

and then this a also satisfies the right-hand-side of (?} - Choice). ?

Another relevant and important result that we will not discuss here in detail is the following:

Theorem 5.3.14 (Gandy et al. [9]) A set A c N is HYP if and only if its characteristic function xa belongs to every F c P (N) which satisfies the axiom scheme of full comprehension, i.e.,for every formula p(s) in which a does not occur free,

Beyond these (and many other) applications, however, the importance of Theorem 5.3.12 is primarily foundational. To quote Kleene [22],

the definition [with basis F] means the same to persons with various universes of functions, so long as each person’s universe includes at least F (of which he may have no exact conception).

One can argue that it presents HYP as a potential totality which can be comprehended by mathematicians with varying views of “the continuum”, much like N can be understood as xza potential totality within classical and constructive mathematics alike.

• [1] It is also his last paper on the subject.
• [2] We need to include all arithmetical sets in A(F), ow. A(0) = 0 and A would close at 0 and buildup the empty set.
• [3] 24We assume some formal treatment of recursive substitutions into A2 formulas. In this case, therelevant recursive function is (a, s) ^ (a)s, and we use the equivalences These are satisfied by every model F of (A^-Comp).
• [4] 25The converse fails, cf. Steel [51].