O'Reilly logo

Recursion Theory by Liang Yu, Chi Tat Chong

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required