Cohen genericity

Cohen forcing in its effective form: dense sets of strings and Baire category, weakly 1-generic sets and Kurtz's characterization of the hyperimmune degrees, forcing of Σ⁰₁ properties and the degrees of 1-generic sets, coding into generic sets (the Posner–Robinson and Friedberg jump inversion theorems), and n-generic sets with their jumps.

Contents

1. 1

   Genericity and Baire category

   Dense sets of strings and generic sets; meager and co-meager classes of Cantor space; the Baire category theorem; properties of sufficiently generic sets.

   1. 1.1 Generic sets
   2. 1.2 Meager and co-meager classes
   3. 1.3 The Baire category theorem
   4. 1.4 Exercises
   5. 1.5 Notes and references
   40 min
2. 2

   Weakly 1-generic sets

   Sets meeting every dense c.e. set of strings; Kurtz's theorem identifies their degrees with the hyperimmune degrees; weak n-genericity.

   1. 2.1 Definition
   2. 2.2 Hyperimmune functions
   3. 2.3 Kurtz's theorem
   4. 2.4 Exercises
   5. 2.5 Notes and references
   40 min
3. 3

   1-generic sets

   Forcing Σ⁰₁ and Π⁰₁ properties with strings; 1-generic sets decide them by a prefix; no 1-generic set is DNC; relativized cone avoidance; meager classes of degrees.

   1. 3.1 Forcing Σ⁰₁ properties
   2. 3.2 1-generic sets are not DNC
   3. 3.3 Genericity and cones
   4. 3.4 Meager classes of degrees
   5. 3.5 Exercises
   6. 3.6 Notes and references
   45 min
4. 4

   The Posner–Robinson theorem

   Coding a set into a 1-generic set so that it can be decoded with any non-computable set; the Posner–Robinson join theorem and Friedberg's jump inversion theorem.

   1. 4.1 The construction
   2. 4.2 Consequences
   3. 4.3 Exercises
   4. 4.4 Notes and references
   35 min
5. 5

   Arithmetic genericity

   n-generic sets meet or avoid every Σ⁰ₙ set of strings; their n-th jump is computed from the set and the n-th jump of the empty set; they decide every Σ⁰ₙ property by a prefix; the hierarchy of genericity notions.

   1. 5.1 Comparison of the notions
   2. 5.2 The jumps of an n-generic set
   3. 5.3 Deciding Σ⁰ₙ properties
   4. 5.4 n-generic sets below the n-th jump
   5. 5.5 Exercises
   6. 5.6 Notes and references
   35 min