Mass problems associated with

effectively closed sets

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 23, 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}.

The simplest proof that P_{w} has a top element is based on the following considerations.

For functions f ∈ ℕ^{ℕ} define (f)_{i}(j) = f(3^{i}5^{j}). Instead of 3^{i}5^{j} we could use any recursive pairing function on ℕ. Note that (f)_{i} ∈ ℕ^{ℕ} and f encodes the sequence (f)_{i}, i = 0, 1, 2, . . ..

For strings τ ∈ ℕ^{<ℕ} define (τ)_{i}(j) ≃ τ(3^{i}5^{j}). Note that (τ)_{i} ∈ ℕ^{<ℕ} and |(τ)_{i}| ≤ |τ|.

If T_{i}, i = 0, 1, 2, … is a sequence of trees, define

T = ∞ ; ∏ ; i=0 T_{i} = {τ | (∀i ≤ |τ|) ((τ)_{i} ∈ T_{i})} .

Note that (1) T is a tree, (2) if the T_{i} for i = 0, 1, 2, … are uniformly recursive, then T is recursive, (3) f is a path through T if and only if ∀i ((f)_{i} is a path through T_{i}).

To prove that P_{w} has a top element.

Define P_{e} = {X ∈ 2^{ℕ} | φ_{e}^{(1),X} (0) ↑}. Note that P_{e}, e = 0, 1, 2, … is our standard recursive enumeration of the Π_{1}^{0} subsets of 2^{ℕ}. Define T_{e} = {τ ∈ 2^{<ℕ} | φ_{e,|τ|}^{(1),τ} (0) ↑}. Note that T_{e} for e = 0, 1, 2, … is a uniformly recursive sequence of trees, and P_{e} = {paths through T_{e}}.

The idea now is to define

T = 2^{<ℕ} ∩ ∞ ; ∏ ; e=0 T_{e}

and P = {paths through T }. Then P is a Π_{1}^{0} subset of 2^{ℕ} and

P = ∞ ; ∏ ; e=0 P_{e} = {X ∈ 2^{ℕ} | ∀e ((X)_{e} ∈ P_{e})}

so for all X ∈ P we have (X)_{e} ∈ P_{e} for all e. Thus P_{e} ≤_{w} P for all e.

The only difficulty here is that P = ∅, because P_{e} = ∅ for some e’s.

We now repair the construction.

By König’s Lemma, P_{e} = ∅ if and only if T_{e} is finite. Define

h(T_{e}) = the height of T_{e} = sup {|τ| | τ ∈ T_{e}}

and

T_{e}^{+} = T_{e}∪{τ ∈ 2^{<ℕ} | h(T_{e}) ≤ |τ|∧τ ↾ h(T_{e}) ∈ T_{e}}

and

P_{e}^{+} = {paths through T_{e}^{+} }.

Note that T_{e}^{+} is a uniformly recursive sequence of infinite recursive trees, and T_{e}^{+} = T_{e} whenever T_{e} is infinite. Hence the sets P_{e}^{+} , e = 0, 1, 2, … are uniformly Π_{1}^{0} and nonempty, and P_{e}^{+} = P_{e} whenever P_{e} is nonempty.

We now define

T^{+} = 2^{<ℕ} ∩ ∞ ; ∏ ; e=0 T_{e}^{+}

and

P^{+} = ∞ ; ∏ ; e=0 P_{e}^{+} = {paths through T^{+} } .

Then P^{+} is a nonempty Π_{1}^{0} subset of 2^{ℕ}. Moreover, for all X ∈ P and all e we have (X)_{e} ∈ P_{e}^{+} , hence (X)_{e} ∈ P_{e} whenever P_{e} is nonempty.

Thus P^{+} represents the top element of P_{w}.

This completes the proof that P_{w} has a top element.

Let L be a language, i.e., a set of predicates. We usually assume that L is finite, or at worst recursive. We consider the first-order predicate calculus over L.

A theory is an ordered pair (L, S) where L is a language and S is a set of L-sentences which is consistent and closed under logical consequence, i.e., S ⊢ F if and only if F ∈ S. We usually write S instead of (L, S).

The theory S is said to be complete if for all L-sentences F either F ∈ S or ¬ F ∈ S.

A completion of S is a complete L-theory extending S.

Lindenbaum’s Lemma says that every theory has at least one completion. Hence, S is complete if and only if S has exactly one completion.

The theory S is said to be decidable if the set of Gödel numbers #(S) = {#(F) | F ∈ S} is recursive.

The theory S is said to be recursively axiomatizable if S is the closure under logical consequence of a recursive set of L-sentences, called the axioms of S.

Easy facts:

1. S is recursively axiomatizable if and only if S is recursively enumerable.

2. If S is decidable, then S is recursively axiomatizable.

3. If S is complete and recursively axiomatizable, then S is decidable.

4. If S is decidable, then S has a decidable completion.

A theory S is said to be essentially undecidable if there is no decidable L-theory extending S. Equivalently, S has no decidable completion.

Peano Arithmetic or PA is the theory in the language of arithmetic {+, ×, 0, 1, =} containing the basic axioms plus the induction scheme.

By Tarski/Mostowski/Robinson, PA is essentially undecidable.

(In fact, Q is essentially undecidable. Note that Q is a very weak, finitely axiomatizable subtheory of PA.)

It follows that every recursively axiomatizable theory extending PA (or even, extending Q) is incomplete. This is the Gödel/Rosser Incompleteness Theorem.

Given a recursively axiomatizable theory S, let C(S) be the set of characteristic functions of sets of the form #(S_{1}) where S_{1} is a completion of S.

Note that C(S) is a nonempty Π_{1}^{0} subset of 2^{ℕ}.

There is a converse theorem due to Hanf and Peretyatkin:

Given a nonempty Π_{1}^{0} set P ⊆ 2^{ℕ}, we can find a finitely axiomatizable theory S such that C(S) is recursively homeomorphic to P.

Hence, C(S) and P have the same Muchnik degree.

We wish to show that the Muchnik degree of C(PA) is 1, the top degree in P_{w}.

Let S be a completion of PA.

We say that X ∈ 2^{ℕ} is representable in S if there exists a formula F (x) with one free variable such that for all n, X(n) = 1 if S ⊢ F (n), and X(n) = 0 if S ⊢ ¬ F (n). Since S is complete, it follows that X ≤_{T} #(S).

We shall show that for every nonempty Π_{1}^{0} set P ⊆ 2^{ℕ} there exists X ∈ P such that X is representable in S.

The idea is that P = P_{e} = {paths through T_{e}} where T_{e} is a recursive subtree of 2^{<ℕ}. Let T_{e}^{∗} be T_{e} according to S. We define X = X_{e}^{∗} ↾ ℕ where X_{e}^{∗} is the leftmost path through T_{e}^{∗} according to S.

The difficulty is that, even though T_{e} is infinite, we may have S ⊢“T_{e} is finite”, hence S ⊢“T_{e} has no paths”, so X_{e}^{∗} does not make sense.

The solution is to use T_{e}^{+} instead of T_{e}. Clearly PA ⊢“T_{e}^{+} is infinite”, hence S ⊢“T_{e}^{+} is infinite”, hence we can let X_{e}^{∗} be the leftmost path in (T_{e}^{+} )^{∗}. We need to show that X = X_{e}^{∗} ↾ ℕ is actually a path through T_{e}. This holds because T_{e} = (T_{e}^{+} )^{∗} ∩ 2^{<ℕ}.

To make this clearer, consider M(S), the term model of S. To define M(S) we consider μ-terms, i.e., terms of the form

t = μx (F (x) ∨ ¬ ∃x F (x))

where μ is the least number operator and F (x) is a formula with one free variable. Two μ-terms t_{1} and t_{2} are said to be equivalent if S ⊢ t_{1} = t_{2}. The elements of M(S) are the equivalence classes of μ-terms.

For all sentences F, we have S ⊢ F if and only if M(S) ⊧ F. In other words, M(S) is a model of S. Moreover, M(S) is the smallest model of S. In model-theoretic terms, M(S) is what is called the prime model of S.

For example, if S is true arithmetic, then M(S) is just ℕ, the standard model of arithmetic. In general, M(S) is a nonstandard model of arithmetic.

We identify n ∈ ℕ with the equivalence class of the μ-term

μx (x = n ∨ ¬ ∃x (x = n))

where n = \underbrace{1 + ⋯ + 1}_{n}. Thus ℕ is a submodel

of M(S) and an initial segment of M(S).

Now, as above, let e ∈ ℕ be such that T_{e} is an infinite recursive subtree of 2^{<ℕ}. The difficulty is that M(S) may think T_{e} is finite, i.e., we may have M(S) ⊧ “T_{e} is finite”.

The solution to this difficulty is to consider T_{e}^{+} instead of T_{e}. Clearly M(S) ⊧ “T_{e}^{+} is infinite”, so let (T_{e}^{+} )^{∗} be T_{e}^{+} as understood in M(S).

Note that T_{e} is an initial segment of (T_{e}^{+} )^{∗}, namely T_{e} = (T_{e}^{+} )^{∗} ∩ 2^{<ℕ}.

Let X_{e}^{∗} be the leftmost path through (T_{e}^{+} )^{∗} as understood in M(S). Then X_{e}^{∗} ↾ ℕ is a path through T_{e}. Moreover, X_{e}^{∗} ↾ ℕ is representable in S. Thus we have a path through T_{e} which is representable in S. This completes the proof.

THE END