Recursion Theory

6 Set theory

This chapter reviews results in set theory that have recursion-theoretic applications. Some of these will be stated without proof for future reference.

6.1 Set-theoretic forcing

The technique of forcing was discussed in the context of recursion theory in Chapter 5. The original version of the method as presented in Cohen [18] was very similar to that developed in § 5.2. Here we follow the approach of unramified forcing introduced by Shoenfield [130] (see Kunen [78] for an excellent exposition of the subject).

6.1.1 Forcing and genericity

Let M = 〈M, ∈〉 be a countable transitive model of ZFC and let ℙ = 〈P, ≤〉 be a partial ordering in M. An element p ∈ P is called a condition. Given two conditions p, q ∈ P, we say that q is stronger ...