Computability, Unsolvability, Randomness Math 497A: Homework #3

Stephen G. Simpson

Due Monday, September 17, 2007

Recall that W_{x} = dom(φ_{x}^{(1)}). Note that W_{x}, x = 0, 1, 2, …, is the standard recursive enumeration of the recursively enumerable subsets of ℕ.

1. Which many-one reducibility relations hold or do not hold among the following sets and their complements?

K = {x | x ∈ W_{x}}
H = {x | 0 ∈ W_{x}}
T = {x | W_{x} = ℕ}
E = {x | W_{x} = ∅}
S = {x | W_{x} is infinite}

Prove your answers.

Hint: Each of these sets is many-one complete within an appropriate level of the arithmetical hierarchy.

2. A set P ⊆ ℕ is said to be productive if there exists a total recursive function h(x) such that for all x, if W_{x} ⊆ P then h(x) ∉ W_{x} and h(x) ∈ P. Such a function is called a productive function for P.

A creative set is a recursively enumerable set whose complement is productive.

Prove the following.

(a) K is creative.

(b) If A and B are recursively enumerable sets and A ≤_{m} B and A is creative, then B is creative.

(c) If B is recursively enumerable and many-one complete, then B is creative.

(d) (Extra Credit) If B is creative, then B is many-one complete.

(e) (Extra Credit) If A and B are creative, then A and B are recursively isomorphic. This means that there exists a recursive permutation of ℕ, call it g, such that x ∈ A if and only if g(x) ∈ B, for all x.

3. A set I ⊆ ℕ is said to be immune if I is infinite yet includes no infinite recursively enumerable set.

A simple set is a recursively enumerable set whose complement is immune.

Prove the following.

(a) If A is simple, then A is not recursive.

(b) If A is simple, then A is not creative.

4. Let f : ℕ ⟶^{1−1} ℕ be a one-to-one total recursive function such that the range of f is nonrecursive. The deficiency set of f is defined as

D_{f} = {x | ∃y (x < y ∧ f(x) > f(y))} .

Prove that D_{f} is a simple set.

Conclude that there exist recursively enumerable sets which are neither recursive nor many-one complete.

5. (Extra Credit) Generalize Exercises 2, 3, 4 to higher levels of the arithmetical hierarchy. Conclude that for each n ≥ 1 there exist Σ_{n}^{0} sets which are neither Δ_{n}^{0} nor many-one complete within the class of Σ_{n}^{0} sets.