5 Recursion-theoretic forcing

Although historically Cohen introduced forcing for set-theoretic considerations, the method was adapted to study problems in recursion theory soon after by Feferman [25] (indeed, one detects a hint of Cohen forcing in the theorems of Post and Kleene on the structure of the Turing degrees proved in the 1950s). Here we study three classic examples of forcing (due to Cohen, Sacks and Steel respectively) and their applications in recursion theory. It turns out that the ramified analytical hierarchy provides an ideal platform for this purpose.

5.1 Ramified analytical hierarchy

5.1.1 The structure image

The ramified analytical ...

Get Recursion Theory now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.