# The Basic Facts About HYP (1950-1960)

A set A c N, relation *R* c N^{n} or (total) function *f :* N^{n} ^ N is *hyperarithmetical *if it is recursive in some *H _{a}*; HYP is the set of all hyperarithmetical sets, and

To express succinctly (and prove) the basic properties of HYP-sets, it is useful to think of them as “bundled” with their codes by the following general notion:

## Codings and Uniformities

A (surjective) *coding* of a set *X* is a pair *(C, n),* where *n : C X* is a surjection of the *codeset C* onto *X*, and we call any *c e C* a *code* (or name) of the object *n(c) e X*. If *C c* N, we say that *the coding is in* N. These are the only codings we will need for a while.

So (S), ||) is a coding of the constructive ordinals; (S), *a* ^ *H _{a}*) is a coding of the

*H*-sets; (S),

_{a}*a*^

*L*is a coding of Davis’

_{a})*L*-sets; and for a very elementary example, (N,

_{a}*e*^

*y*is a coding of the set of unary recursive partial functions. The coding of HYP we introduced by (5.23) is formally the pair

_{e})

In practice we will never be so formal, in fact we will sometimes use codings which are “specified by the context” without a formal definition of *C* and *n*.

Codings are useful for expressing succinctly *uniform properties* of *coded sets. *Their general theory is technically messy, not very interesting mathematically and certainly not worth putting here.^{[1]} ^{[2]} We will confine ourselves to these remarks and “detail” sufficiently many claims to make the ideas clear. For example:

Lemma 5.3.1 HYP *is uniformly closed under complements and relative recursion. In detail, there are recursive partial functions u (c) and v(c, e) such that:*

- (1)
*If A is*HYP*with code c, then u(c) l and is a*HYP-code*of*(N A). - (2)
*Ifc is a*HYP-code*of a set B and*A*B, then v(c, e) l and is a*HYP-code*of A.*

This is a simple lemma, as are the similar claims of uniform closure of the hyperarithmetical relations (with their natural coding) under all first-order operations on N. There is no use of effective effective grounded recursion in these proofs, we only need appeal to uniform properties of the jump operation like (5.15). The next result is also quite easy, but its proof requires effective grounded recursion and some auxiliary definitions on the constructive ordinals:

Lemma 5.3.2 HYP *is uniformly closed under recursive unions.*

*In detail, there is a recursive partial function u(e) such that if y _{e} is total and for each t, v_{e}(t) is a* HYP-code

*of a set A*c N,

_{t}*then u(e) l and is a*HYP-code

*of*Lb

*At.*

Coding invariance

Two codings (Ci*,n _{1}), (C_{2},n_{2})* in N of the same set

*X = n*= n

_{1}[C_{1}]_{2}[C

_{2}] are

*equivalent*if there are recursive partial functions

*u*such that

_{1}(a), u_{2}(b)

and similarly with 1 and 2 interchanged. It is clear that propositions like Lemmas 5.3.1 and 5.3.2 which hold uniformly for a certain coding also hold uniformly for every equivalent coding—and for some of them the proof might be easier.^{[3]} We exploit this idea by establishing an elegant characterization of HYP which produces a coding for it equivalent to the classical one in (5.23) but much simpler.

- [1] Cf. Moschovakis [36, 37] for a discussion (and many examples), and 7A.4 of Moschovakis [35]for a specific result which codifies many of the applications of effective grounded recursion inDescriptive Set Theory.
- [2] The interested reader may want to look at Moschovakis [36] where it was necessary to developthis generalized abstract nonsense in some detail.
- [3] For a classical example, consider the coding of recursive partial functions specified by the NormalForm Theorem in App 5. Its precise definition depends on the choice of computation model thatwe use, Turing machines, systems of recursive equations or whatever, but all these codings areequivalent and so uniform propositions about them are coding invariant. §4.3-§4.5 of Rogers [45]considers this situation in some detail and formulates stronger notions of equivalence than the onewe use.