K-trivial sets

The sets whose initial segments have the complexity of their lengths: Chaitin's counting theorem and the Δ⁰₂-ness of K-trivial sets, closure under join, Solovay functions, cost functions and Solovay's construction of a non-computable K-trivial set, lowness for K and for Martin-Löf randomness, bases for randomness and the hungry sets theorem, and the coincidence of all these notions.

Contents

1. 1

   K-trivial sets

   Sets whose initial segments are as simple as their lengths; Chaitin's counting theorem shows that there are countably many K-trivial sets, all of them Δ⁰₂; closure under join; Solovay functions and a characterization of K-triviality by a computable bound.

   1. 1.1 Definition
   2. 1.2 Chaitin's counting theorem
   3. 1.3 Closure under join
   4. 1.4 Solovay functions
   5. 1.5 Exercises
   6. 1.6 Notes and references
   40 min
2. 2

   Cost functions and Solovay's construction

   The standard cost function; a set with a computable approximation obeying it is K-trivial; Solovay's construction of a simple K-trivial set.

   1. 2.1 The standard cost function
   2. 2.2 Obeying the cost function implies K-triviality
   3. 2.3 Solovay's theorem
   4. 2.4 Exercises
   5. 2.5 Notes and references
   35 min
3. 3

   Lowness for randomness

   Sets that are low for K, low for Martin-Löf randomness, and bases for randomness; the three notions coincide by the hungry sets theorem; they also coincide with K-triviality, by a theorem of Nies and Hirschfeldt, admitted here; consequences for the K-trivial sets.

   1. 3.1 Relativized complexity and randomness
   2. 3.2 Three lowness notions
   3. 3.3 The hungry sets theorem
   4. 3.4 K-triviality and lowness
   5. 3.5 Exercises
   6. 3.6 Notes and references
   45 min