Oval 1

Undecidability of the exponential time degrees

and effective algebra

André Nies

Outline

Goal: find a uniform method to

• prove undecidability of, or even

• interpret Th(ℕ) in

theories of seemingly “smooth” structures. The structures are from computability theory and complexity theory. The method consists in

1. identifying a very complex lattice of ideals of certain boolean algebras

2. finding such lattices in all structures under consideration.

E:= lattice of c.e. sets under inclusion We consider intervals of E and of E^{∗} := E/=^{∗}

I. Computability theory

Theorem 1 Suppose D ⊆ A, where D, A ∈ E. If [D, A]_{E} is not a boolean algebra, then Th(ℕ) can be interpreted in Th([D, A]). Similarly for E^{∗}.

II. Complexity theory

Joint with R. Downey

Consider subsets X, Y of {0, 1}^{<ω} X ≤_{m}^{p} Y ⇔ (∃f ∈ Ptime[X = f^{−1}(Y)]) X ≤_{T}^{p} Y ⇔ ∃ polynomial time bounded oracle TM which computes X if the oracle is Y. (Rec_{r}^{p}, ≤_{r}^{p}): polynomial time r–degrees of computable sets. Here ≤_{r}^{p} is a polynomial time reducibility “between” ≤_{m}^{p} and ≤_{T}^{p}.

1975 Ladner: Rec_{r}^{p} is dense. 1989 Slaman, Shinoda: Th(ℕ)

can be interpreted in Th(Rec_{T}^{p})

1992 Ambos-Spies, N : Th(Rec_{m}^{p})

is undecidable.

Classes low down

Both undecidability proofs use computable sets of very high complexity (nonelementary sets) DTIME(h) := {X ⊆ {0, 1}^{<ω}:

X can be computed in time O(h)}.

Theorem 2 Th(DTIME(2^{n}), ≤_{r}^{p}) is undecidable.

This holds in fact for any time constructible hyperpolynomial h(n) in place of 2^{n} (e.g., n^{log n}).

Complex initial segments

Theorem 3 If A ⊆ {0}^{∗} is strongly supersparse and A ∉ PTIME, then Th([0, a]Rec_{r}^{p}) interprets Th(ℕ).

A is strongly supersparse if, roughly speaking, • ∃ strictly increasing f : ℕ ↦ ℕ A ⊆ {0^{f(k)} : k ∈ ℕ}

• “0^{f(n)} ∈ A ?” can be determined in time O(f(n + 1)).

Each class DTIME(h), h as above, contains such a strongly supersparse set.

Complexity classes under inclusion

Theorem 4 The theory of e.g. the boolean pair

(DTIME(n^{2}), DTIME(n), ⊆))

interprets Th(ℕ).

In fact can show this for

(DTIME(g), DTIME(h), ⊆)),

if g, h satisfy the hypotheses of the Time Hierarchy Theorem.

Q: elementary arithmetic T: recursively axiomatizable, consistent the-

C.e. extensions of Q

ory containing Q

L_{T}: lattice of c.e. extensions of T closed under “⊢”

Theorem 5 Th(ℕ) ≤_{m} Th(L_{T})

Effective algebra

Investigates the effective content of constructions in algebra. Studies lattices of c.e. substructures:

• c.e. subspaces of ℚ^{(∞)}

• c.e. ideals of the recursive dense boolean algebra D

•...

C.e. boolean algebras

One way: D/I, I c.e. ideal of D More concrete:

(ℕ, ⪯, ∧, ∨)

is c.e. boolean algebra if:

• ∨, ∧ are computable

• ⪯ is c.e. (let x ≡ y if x ⪯ y ⪯ x)

• B = (ℕ, ⪯, ∧, ∨)/≡ is a boolean algebra

To define Σ_{k}^{0}-boolean algebras, require that ⪯ be Σ_{k}^{0} and that ∧, ∨ be recursive in ∅^{(k−1)}.

3 Examples

Σ_{1}^{0}: T consistent recursively axiomatizable theory, B = B(T) Lindenbaum algebra of sentences over T

Σ_{2}^{0}: The complemented elements in [0, a]Rec_{r}^{p}, where a is the degree of a supersparse set

Σ_{3}^{0}: The complemented elements in [D^{∗}, A^{∗}]_{E^{∗}}, where D ⊂_{∞} A

I(B)

For a Σ_{k}^{0}–boolean algebra B, let I(B) := lattice of Σ_{k}^{0}–ideals of B.

• I(B) is a distributive lattice with least and greatest elements

• I(B) has the reduction property

• All principal ideals [0, b]_{B} are in I(B)

• An ideal is principal iff complemented • I(B) can also be viewed as a lattice of effectively open sets in a Stone space.

Possibly for a dense c.e. B: I(B) ≅ B because every c.e. ideal is principal (Martin, Pour-El 1970).

Effective density

A c.e. boolean algebra B is called effectively dense if there is a computable F such that ∀x [F (x) ⪯ x] and

∀x ≢ 0 [0 ≺ F (x) ≺ x].

For Σ_{k}^{0} B require that F ≤_{T} ∅^{(k−1)}.

(All effectively dense BA’s are ≅ D, but not necessarily effectively.)

Examples, continued

Σ_{1}^{0}: T recursively axiomatizable theory containing Q, B = B(T) is effectively dense by Rosser’s Theorem

Σ_{2}^{0}: The complemented elements in [0, a]Rec_{r}^{p} form an effectively dense Σ_{2}^{0} boolean algebra by Ladner’s method

Σ_{3}^{0}: If D ⊂_{m} A, then the complemented elements in [D^{∗}, A^{∗}]_{E^{∗}} form an effectively dense Σ_{3}^{0} boolean algebra by the “Owings splitting theorem” (which is effective).

A⊂_{m}B⇔ A⊂_{∞}B ∧

(∀W c.e. )[B∪W =ℕ⇒A∪W =^{∗}ℕ].

I(B) is complex

Theorem 6 Suppose B is effectively dense. Then Th(ℕ) can be interpreted in Th(I(B)).

T as in Example 1. L_{T}: lattice of c.e. extensions of T closed under “⊢” Recall: Theorem 5 Th(ℕ) ≤_{m} Th(L_{T}) To see this, notice that elements of L_{T} are just the c.e. filters in B(T) So L_{T} ≅ I(B) For the proof of Th(ℕ) ≤_{m} Th(I(B)), use an analogy between E and I(B):

E  I(B)
numbers  elements of B
c.e. sets  c.e. ideals
computable sets  principal ideals
Friedberg Splitting  ∀A nonpr.
Theorem  ∃A_{0}, A_{1} nonpr.

A = A_{0} ∨ A_{1} ∧ A_{0} ∩ A_{1} = {0}

Give an interpretation without params of (Σ_{5}^{0}, ⊆) in I(B). All together we have the following interpretations:

Th(ℕ) ⇒^{Harrington} Th(Σ_{5}^{0}, ⊆) ⇒^{Nies} Th(I(B)).

Intervals of E^{∗}

Some known results Let L^{∗}(A) = [A^{∗}, ω^{∗}]

• (Lachlan 68) All Σ_{3}^{0} boolean algebras can be represented as L^{∗}(A) for suitable A

• (Cholak, N ta) There are infinitely many nonisomorphic L^{∗}(A) such that A is r-maximal (no nontrivial element of L^{∗}(A) is complemented).

• (Maass, Stob 83) There is only one isomorphism type [D^{∗}, A^{∗}], for D ⊆_{m} A. This structure is called M^{∗}.

Proving Thm 1

Theorem 1 If [D, A]_{E} is not a boolean algebra, then Th(ℕ) can be interpreted in Th([D, A]). Similarly for E^{∗}.

1. Enough to prove it for D ⊆_{m} A

2. Sufficient to do it for E^{∗} Recall from Example 3: B = complemented elements in [D^{∗}, A^{∗}].

Defining Σ_{3}^{0}-ideals of B

Lemma 1 If I ∈ I(B), ∃C_{I} ∀X ∈ B

X ∈ I ⇔ X ∩ C_{I} =^{∗} D.

Conversely, if C_{I} determines I in this way, then I is Σ_{3}^{0}. Now I(B) can be interpreted in [D^{∗}, A^{∗}] without parameters: represent I by some C_{I}^{∗}. The following expresses inclusion in terms of elements of [D^{∗}, A^{∗}] representing ideals 0f B. φ_{⊆}(c_{1}, c_{2}) = ∀x complemented

[x ∧ c_{1} = 0 ⇒ x ∧ c_{2} = 0]. Idea to prove the lemma: B is small compared to the whole interval [D^{∗}, A^{∗}], and we have good control over the splittings.

Proving Thm 2

Theorem 2[with Downey] Th(DTIME(h), ≤_{r}^{p} )) is undecidable, for any time constructible hyperpolynomial h.

• h is time constructible if h(n) can be computed in time O(h(n)).

• A is supersparse if ∃ strictly increasing, time constructible f : ℕ ↦ ℕ such that

– A ⊆ {0^{f(k)} : k ∈ ℕ}

– “0^{f(n)} ∈ A ?” can be determined in

time O(f(n + 1)).

• A is strongly supersparse if, in addition, for all k inℕ

(a.e. n)[ f(n)^{k} < f(n + 1)].

Auxiliary results

Lemma 2 If h is as above, then there is a strongly supersparse

A ∈ DTIME(h) − PTIME. Let a be the degree of A. Lemma 3 The complemented elements below a are the degrees of sets A ∩ R, R ∈ PTIME.

So the complemented elements form indeed a Σ_{2}^{0} boolean algebra B, as already stated in Example 2.

Defining Σ_{2}^{0}–ideals

Lemma 4 If I ∈ I(B), then ∃c_{I} ∈ DTIME(h) ∀x ∈ B

x ∈ I ⇔ x ≤ c_{I}.

Conversely, each ideal defined in this way must be Σ_{2}^{0}. □

In the preceding lemma, using strong supersparseness of a , can in fact achieve c_{I} ≤ a. This gives the parameterless interpretations needed for Thm 3: Th(ℕ) ⇒ Th(Σ_{6}^{0}, ⊆) ⇒

Th(I(B)) ⇒ Th([0, a]).