HYP as Recursive in 2E
Starting with his [23], Kleene developed a theory of absolute and relative recursion for functions with arguments in the objects of finite type over N, i.e., members of the sets T where
This is a technically difficult but fascinating topic, with some important applications to Descriptive Set Theory but especially to the foundations of the theory of recursion: it was the first example where there is no natural notion of machine computable function that can be defined independently of “recursiveness”, and so it forces an examination of the meaning of recursive definitions in and of themselves. We cannot go into it here, but it is worth stating one of Kleene’s basic results which relate it to HYP29:
In Kleene’s words, the following type-2 object “embodies” the operation of quantification over N:
Theorem 5.3.16 (Kleene [23]) A set A c N is hyperarithmetical if and only if it is recursive in2 E. [1]
In fact, for A c N,
which bolsters the understanding of П as an analog of ? in recursion in2E.[2]
- [1] Cf. Kechris and Moschovakis [12] for a relatively simple introduction to recursion in higher typesand Sacks [46] for a full development.
- [2] Kleene [23] does not mention this and I recall him saying (much later) that he was not certain thatthe notion of a recursive partial function in higher type recursion was natural, but I cannot point toa reference for this.
