Endnotes – Recursion Theory


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 α.