3 Admissibility and constructibility
This chapter introduces the basic notions of effective computability from the set- theoretic perspective. While somewhat abstract at first sight, they are natural when viewed from the standpoint of definability.
An admissible structure is essentially an inner model of computation. The constructible universe L is defined via a transfinite iteration of the Gödel operators. By considering an appropriate initial segment of L which forms an admissible structure, we will see how a -set assumes the role of an r.e. set in higher recursion theory.
3.1 Kripke–Platek set theory
The Kripke–Platek (KP) theory of sets was ...