Higher randomness

Randomness notions obtained by replacing computability with hyperarithmetic definability: Δ¹₁-randomness, Martin-Löf tests with Π¹₁ components and their universal test, and Π¹₁-randomness, with no classical analogue. The course proves the characterization of Π¹₁-randomness by Chong, Nies and Yu, the coincidence of Σ¹₁- and Δ¹₁-randomness, and the null cone theorem for hyperarithmetic reducibility, from explicitly admitted facts on the measure of Δ¹₁ classes and the Sacks–Tanaka theorem.

Contents

1. 1

   Δ¹₁-randomness and higher Martin-Löf tests

   Randomness defined by hyperarithmetic null classes and by Martin-Löf tests whose components are Π¹₁ open classes; open Π¹₁ classes are generated by Π¹₁ sets of strings; a universal higher test, built by trimming along stages; higher Martin-Löf randomness implies Δ¹₁-randomness, which implies arithmetic randomness.

   1. 1.1 Δ¹₁ classes and the facts we admit
   2. 1.2 Two notions of higher randomness
   3. 1.3 A universal higher test
   4. 1.4 Exercises
   5. 1.5 Notes and references
   40 min
2. 2

   Π¹₁-randomness

   Randomness with respect to all null Π¹₁ classes; the Sacks–Tanaka theorem that almost no sequence computes a non-computable ordinal; the characterization of Π¹₁-randomness by Chong, Nies and Yu; Σ¹₁-randomness coincides with Δ¹₁-randomness; the largest null Π¹₁ class.

   1. 2.1 Definitions and the Sacks–Tanaka theorem
   2. 2.2 The characterization of Chong, Nies and Yu
   3. 2.3 Σ¹₁-randomness
   4. 2.4 Exercises
   5. 2.5 Notes and references
   40 min
3. 3

   Randomness and hyperarithmetic reducibility

   Hyperarithmetic reducibility; the higher analogue of Sacks' theorem, that the upper hyperarithmetic cone of a non-hyperarithmetic set is null; the hierarchy of higher randomness notions and its relation with arithmetic randomness.

   1. 3.1 Hyperarithmetic reducibility
   2. 3.2 The upper cone of a non-hyperarithmetic set
   3. 3.3 The hierarchy of higher randomness
   4. 3.4 Exercises
   5. 3.5 Notes and references
   30 min