Recursively enumerable sets and degrees : a study of computable functions and computably generate...

introduction .

part a. the fundamental concepts of recursion theory

chapter i. recursive functions

1. an informal description

2. formal definitions of computable functions

2.1. primitive recursive functions

2.2. diagonalization and partial recursive functions

2.3. turing computable functions

3. the basic results

4. recursively enumerable sets and unsolvable problems

5. recursive permutations and myhill's isomorphism theorem

chapter ii. fundamentals of recursively enumerable sets and the recursion theorem

1. equivalent definitions of recursively enumerable sets and their basic properties

2. uniformity and indices for recursive and finite sets

3. the recursion theorem

4. complete sets, productive sets, and creative sets

chapter iii. turing reducibility and the jump operator

1. definitions of relative computability

2. turing degrees and the jump operator

3. the modulus lemma and limit lemma

.chapter iv. the arithmetical hierarchy

1. computing levels in the arithmetical hierarchy

2. post's theorem and the hierarchy theorem

3. εn-complete sets

4. the relativized arithmetical hierarchy and high and low degrees

part b. post's problem, oracle constructions and the finite injury priority method

chapter v. simple sets and post's problem

1. immune sets, simple sets and post's construction

2. hypersimple sets and majorizing functions

3. the permitting method

4. effectively simple sets are complete

5. a completeness criterion for r.e. sets

chapter vi. oracle constructions of non-r.e. degrees

1. a pair of incomparable degrees below 0'

2. avoiding cones of degrees

3. inverting the jump

4. upper and lower bounds for degrees

5.* minimal degrees

chapter vii. the finite injury priority method

1. low simple sets

2. the original friedberg-muchnik theorem

3. splitting theorems

part c. infinitary methods for constructing r.e. sets and degrees

chapter viii. the infinite injury priority method

1. the obstacles in infinite injury and the thickness lemfna

2. the injury and window lemmas and the strong thickness lemma

3. the jump theorem

4. the density theorem and the sacks coding strategy

5.* the pinball machine model for infinite injury
chapter ix. the minimal pair method and embedding lattices into the r.e. degrees

1. minimal pairs and embedding the diamond lattice

2.* embedding distributive lattices

3. the non-diamond theorem

4.* nonbranching degrees

5.* noncappable degrees ..

chapter x. the lattice of r.e. sets under inclusion

1. ideals, filters, and quotient lattices

2. splitting theorems and boolean algebras

3. maximal sets

4. major subsets and r-maximal sets

5. atomless r-maximal sets

6. atomless hh-simple sets

7.* ε3 boolean algebras represented as lattices of supersets

chapter xi. the relationship between the structure and the degree of an r.e. set

1. martin's characterization of high degrees in terms of dominating functions

2. maximal sets and high r.e. degrees

3. low r.e. sets resemble recursive sets

4. non-low2 r.e. degrees contain atomless r.e. sets

5.* low2 r.e. degrees do not contain atomless r.e. sets

chapter xii. classifying index sets of r.e. sets

1. classifying the index set g(a) ={ x: wx ≡t a }

2. classifying the index sets g(≤ a), g(≥ a), and g(