Immunity and growth of functions

Weakness and strength measured by the growth of functions: immune, hyperimmune and hypersimple sets, computably dominated degrees and truth-table reducibility, diagonally non-computable and fixed-point free functions with Arslanov's completeness criterion, and Martin's characterization of the high degrees by dominant functions.

Contents

1. 1

   Immune and hyperimmune sets

   Immune sets contain no infinite c.e. subset; hyperimmune sets escape every computable array of disjoint finite sets, equivalently their principal function is not computably dominated; Dekker's deficiency sets give hypersimple sets in every non-zero c.e. degree.

   1. 1.1 Immune sets
   2. 1.2 Hyperimmune sets
   3. 1.3 Hypersimple sets
   4. 1.4 Exercises
   5. 1.5 Notes and references
   40 min
2. 2

   Computably dominated degrees

   Sets all of whose functions are dominated by computable functions; a construction by computable function trees; truth-table reducibility, and the characterization of computably dominated sets by the coincidence of Turing and truth-table reducibility below them.

   1. 2.1 Function trees
   2. 2.2 Truth-table reducibility
   3. 2.3 Exercises
   4. 2.4 Notes and references
   45 min
3. 3

   Diagonally non-computable functions

   DNC and fixed-point free functions compute each other; the DNC degrees are the degrees of effectively immune sets; Arslanov's completeness criterion shows that a c.e. set computing a DNC function is complete.

   1. 3.1 DNC and fixed-point free functions
   2. 3.2 Effectively immune sets
   3. 3.3 Arslanov's completeness criterion
   4. 3.4 Exercises
   5. 3.5 Notes and references
   45 min
4. 4

   Martin's domination theorem

   A set is high if and only if it computes a function that eventually dominates every computable function; high sets list the computable functions; maximal sets are high; a set is high or DNC if and only if it computes a function that differs almost everywhere from every computable function.

   1. 4.1 Martin's theorem
   2. 4.2 Lists of computable functions
   3. 4.3 Maximal sets
   4. 4.4 High or DNC
   5. 4.5 Exercises
   6. 4.6 Notes and references
   40 min