# Endnotes – Recursion Theory

## Endnotes

### The construction of -sets

 1 Attempts were made by several authors to inductively define these sets (see, for example, [100]). In [17] a solution in this direction was given via a recursion-theoretic approach. 2 See [13] for a higher level analysis of Martin’s conjecture.

### B An interview with Gerald E. Sacks

 3 Department of Mathematics, National University of Singapore, Singapore 119076 4 The Downward Löwenheim–Skolem Theorem states that every model of a countable theory has an elementary countable submodel. 5 Now known as the Sacks Splitting Theorem. 6 The Jump Theorem states that every degree that is r.e. in and above 0′ is the jump of an r.e. degree. 7 An object of type 0 is a nonnegative integer. An object of type n + 1 is a set of objects of type n. n+1E is the characteristic function of the set of objects of type n. In Kleene’s theory of recursion in objects of finite type, n+1E is recursive if and only if n = 0. He defined the 1-section of n+1E to be the set of type 1 objects recursive in n+1E. He proved that the 1-section of 2E is HYP. 8 Kleene developed a computation theory of higher type objects generated by n-th iterates of the power set operation on ℕ. A unified approach from the set-theoretic point of view, E-recursion, was introduced by Dag Normann in 1967. 9 Yiannis Moschovakis. 10 The problem asks if there is a minimal α-degree for every admissible ordinal α.