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

13 More on hyperarithmetic theory

13.1 Hyperarithmetic measure theory

The application of measure theory in recursion theory was initiated by Spector [155], Sacks [117] and Leeuw, Moore, Shannon, and Shapiro [19]. Randomness theory on the natural numbers may be viewed as such an application, while higher randomness theory is the union of measure theory with hyperarithmetic theory. In this chapter we discuss these connections to set the stage for higher randomness in the next chapter.

13.1.1 The measure of image-sets

Lemma 13.1.1 (Sacks [120]). The set

is .

Proof. By the Spector–Gandy Theorem (3.7.1) it is sufficient to prove that the set

is Σ1 over ...

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