Mass problems associated with

effectively closed sets, part 2

Stephen G. Simpson

Pennsylvania State University NSF DMS-0600823, DMS-0652637 http://www.math.psu.edu/simpson/

simpson@math.psu.edu

Logic Seminar Department of Mathematics Pennsylvania State University

October 30, 2007 Abstract:

We begin with a brief introduction to mass problems in general. After that, the purpose of the talk is to introduce P_{w}, the lattice of Muchnik degrees of mass problems associated with nonempty effectively closed sets in the Cantor space. We show that P_{w} is a countable distributive lattice with 0 and 1. We show that the top element of P_{w} is the Muchnik degree of the problem of finding a complete consistent theory which extends Peano Arithmetic. The G”odel Incompleteness Theorem tells us that this problem is unsolvable. Instead of Peano Arithmetic we could take any theory which, like Peano Arithmetic, is recursively axiomatizable and effectively essentially undecidable. It turns out that the effectively closed sets associated with all such theories are not only Muchnik equivalent but also recursively homeomorphic to each other. As time permits we shall exhibit some other interesting examples of specific, natural Muchnik degrees in P_{w}.

Let P and Q be subsets of ℕ^{ℕ}.

P is strongly reducible to Q, P ≤_{s} Q, if there exists a partial recursive functional Ψ : ⊆ ℕ^{ℕ} → ℕ^{ℕ} such that Q ⊆ dom (Ψ) and Ψ(g) ∈ P for all g ∈ Q. (Medvedev 1955)

P is weakly reducible to Q, P ≤_{w} Q, if for all g ∈ Q there exists f ∈ P such that f ≤_{T} g. (Muchnik 1963)

Obviously P ≤_{s} Q implies P ≤_{w} Q. The converse does not hold in general.

Note that ≤_{s}, strong reducibility, is the uniform version of ≤_{w}, weak reducibility.

We are interested in the lattices P_{s} and P_{w} of strong and weak degrees of nonempty Π_{1}^{0} subsets of 2^{ℕ}. Note that P_{s} and P_{w} are countable distributive lattices with 0 and 1.

We write 1 for the top degree in P_{s} or P_{w}.

Let P and Q be nonempty Π_{1}^{0} subsets of 2^{ℕ}.

Theorem 1 (Simpson 2000). If deg _{s}(P) = deg _{s}(Q) = 1 then P and Q are recursively homeomorphic, i.e., there exists a partial recursive functional Ψ which maps P one-to-one onto Q. It follows that the inverse functional Ψ^{−1} is also partial recursive.

Theorem 2 (Simpson 2002). If deg _{w}(P) = deg _{w}(Q) = 1 then P and Q are Turing equivalent, i.e.,

{deg _{T} (f) | f ∈ P } = {deg _{T} (g) | g ∈ Q} .

It follows that these sets of Turing degrees are upward closed.

Corollary. If deg _{w}(P) = 1 then {deg _{T} (f) | f ∈ P } is upward closed.

Proof. Let Q = P × 2^{ℕ}. Clearly Q is a Π_{1}^{0} subset of 2^{ℕ} and deg _{w}(Q) = 1 and {deg _{T} (g) | g ∈ Q} is upward closed. It follows by Theorem 2 that this holds for P as well. □

Corollary (Solovay). The set of Turing degrees of completions of PA is upward closed.

Proof. We have seen that C(PA) is a Π_{1}^{0} subset of 2^{ℕ} and deg _{w}(C(PA)) = 1. Hence, by the previous corollary, {deg _{T} (S) | S ∈ C(PA)} is upward closed. □

Let P_{e}, e = 0, 1, 2, … be our standard recursive enumeration of the Π_{1}^{0} subsets of 2^{ℕ}. Let D_{e}, e = 0, 1, 2, … be our standard recursive enumeration of the clopen subsets of 2^{ℕ}. Note that each clopen set in 2^{ℕ} looks like ⋃_{σ∈S} N_{σ} where S is a finite subset of 2^{<ℕ}.

Definition. Let P be a nonempty Π_{1}^{0} subset of 2^{ℕ}. A splitting function for P is a recursive function g : ℕ → ℕ such that for all e, if P_{e} ⊆ P is nonempty, then P_{e} ∩ D_{g(e)} and P_{e} \ D_{g(e)} are nonempty. P is productive if there exists a splitting function for P.

For a recursively axiomatizable theory S, the corresponding property is effective essential undecidability:

Given a recursively axiomatizable extension S′ of S, we can effectively find a sentence F such that neither S′ ⊢ F nor S′ ⊢ ¬ F.

Let P and Q be Π_{1}^{0} subsets of 2^{ℕ}.

Theorem.

1. If P is productive, we can find a recursive functional which maps P onto Q.

2. If P and Q are productive, then P and Q are recursively homeomorphic.

The proof uses the Recursion Theorem and is reminiscent of Myhill’s proof that creative r.e. sets are recursively isomorphic.

Lemma.

1. There exists a productive P.

2. If P is productive and P ≤_{s} Q, then Q is productive.

Theorem. P is productive if and only if deg _{s}(P) = 1.

The “only if” statement follows from part 1 of the previous theorem. The “if” statement follows from the previous lemma.

THE END