A survey of basis theorems

Stephen G. Simpson Pennsylvania State University

http://www.math.psu.edu/simpson/ simpson@math.psu.edu

Computability Theory and Foundations of Mathematics Tokyo Institute of Technology

February 18–20, 2013 Basis theorems.

A basis theorem is a theorem of the form:

For any nonempty effectively closed set in Euclidean space, at least one member of the set is “close to being computable ”.

Some well known basis theorems are:

• the Low Basis Theorem,

• the R.E. Basis Theorem,

• the Hyperimmune-Free Basis Theorem,

• the Cone Avoidance Basis Theorem,

• the Randomness Preservation Basis Thm.

Less well known is a basis theorem of Higuchi/Hudelson/Simpson/Yokoyama on preservation of partial randomness.

We shall state these basis theorems, discuss some of their applications, and discuss the possibilities for combining them.

Three basis theorems.

Let ≤_{T} denote Turing reducibility. Let ′ denote the Turing jump operator.

The Low Basis Theorem : For any nonempty effectively closed set Q, there exists Z ∈ Q such that Z′ ≤_{T} 0′.

The R.E. Basis Theorem : For any nonempty effectively closed set Q, there exists Z ∈ Q such that Z is of recursively enumerable Turing degree.

We say that Z is hyperimmune-free if (∀ functions f ≤_{T} Z) (∃ recursive function g) ∀n (f(n) < g(n)).

The Hyperimmune-Free Basis Theorem : For any nonempty effectively closed set Q, (∃Z ∈ Q) (Z is hyperimmune-free).

These three basis theorems are due to Jockusch/Soare 1972.

Some applications.

Basis theorems are applicable to the study of models of first- and second-order arithmetic.

Namely, there is a nonempty effectively closed set Q_{ω} such that each Z ∈ Q_{ω} encodes a countable ω-model of WKL_{0} (subsystems of second-order arithmetic), or equivalently, a Scott set (models of first-order arithmetic).

Thus, there exist Z_{1}, Z_{2}, Z_{3} ∈ Q_{ω} such that Z_{1} is low, Z_{2} is of r.e. Turing degree, and Z_{3} is hyperimmune-free.

Question: Does there exist Z ∈ Q_{ω} with two or more of these properties?

Answer: See the next slide.

Conversely, for any ω-model M of WKL_{0} and any nonempty effectively closed set Q, we have M ∩ Q ≠ ∅.

Thus Q_{ω} is in a sense universal . For many purposes, we may assume Q = Q_{ω}.

Can we combine these basis theorems?

No. The Jockusch/Soare basis theorems are known to be “pairwise incompatible.”

1. The Arslanov Completeness Criterion provides a nonempty effectively closed Q such that for all r.e. sets A, if (∃Z ∈ Q) (Z ≤_{T} A) then 0′ ≤_{T} A.

Therefore, the Low Basis Theorem and the R.E. Basis Theorem cannot be combined into one basis theorem.

2. It is known that for hyperimmune-free Z one cannot have 0 <_{T} Z ≤_{T} 0′.

Therefore, the Hyperimmune-Free Basis Theorem cannot be combined with the Low Basis Theorem or with the R.E. Basis Theorem.

Two more basis theorems.

The Cone Avoidance Basis Theorem : For any nonempty effectively closed set Q, if A ≰_{T} 0 then (∃Z ∈ Q) (A ≰_{T} Z). More generally, if ∀i (A_{i} ≰_{T} 0) then (∃Z ∈ Q) ∀i (A_{i} ≰_{T} Z).

Gandy/Kreisel/Tait, 1960.

Let MLR = {X | X is Martin-Löf random}. Let MLR ^{Z} = {X | X is Martin-Löf random relative to Z}.

The Randomness Preservation Basis Theorem : For any nonempty effectively closed set Q, if X ∈ MLR then (∃Z ∈ Q) (X ∈ MLR ^{Z}).

Reimann/Slaman, not yet published. Downey/Hirschfeldt/Miller/Nies, 2005. Simpson/Yokoyama, 2011.

More applications.

An application of Cone Avoidance :

Let T be a recursively axiomatizable consistent theory extending first-order arithmetic PA (or even Robinson’s Q). Define the hard core of T as HC(T) = ⋂{M | M is the Scott set of some model of T }. Then HC(T) = REC = {A ⊆ ℕ | A is recursive}.

In particular, REC is the intersection of all ω-models of WKL_{0}.

The use of the term “hard core” in this context was suggested by Kreisel.

More applications.

Applications of Randomness Preservation :

1. (Reimann/Slaman) X ≰_{T} 0 implies X is non-atomically random with respect to some Borel probability measure.

2. (Simpson/Yokoyama) Given a countable ω-model M of WWKL_{0}, we can extend M to a countable ω-model M_{1} of WKL_{0} such that C ∩ M ≠ ∅ for every M_{1}-coded closed set C of positive measure. This has consequences for the reverse mathematics of non-standard measure theory.

3. (Brattka/Miller/Nies) A real number x is computably random if and only if every computably continuous function of bounded variation is differentiable at x.

More combinations of basis theorems?

It is known that Cone Avoidance can be combined with the Low Basis Theorem, or with the Hyperimmune-free Basis Theorem, but not with the R.E. Basis Theorem. (See for instance Downey/Hirschfeldt §2.19.3.)

Also, Randomness Preservation cannot be combined with the Low or the R.E. or the Hyperimmune-Free Basis Theorem.

A leading question: Can Cone Avoidance be combined with Randomness Preservation?

The answer to this question involves LR-reducibility .

Define A ≤_{LR} B ⟺ MLR ^{B} ⊆ MLR ^{A}. Clearly A ≤_{T} B implies A ≤_{LR} B, and it is known that A ≤_{LR} 0 implies A′ ≤_{T} 0′. A major theorem of Nies is that A ≤_{LR} 0 ⟺ A is K-trivial. See Nies 2009 or Downey/Hirschfeldt 2010.

A theorem which combines Cone Avoidance and Randomness Preservation:

Theorem 1 (Simpson/Stephan, 2013). For any nonempty effectively closed set Q, if X ∈ MLR and ∀i (A_{i} ≰_{LR} 0 or A_{i} ≰_{T} X), then (∃Z ∈ Q) (X ∈ MLR ^{Z} and ∀i (A_{i} ≰_{T} Z)).

On the other hand, let Ω ∈ MLR be such that Ω ≡_{T} 0′. It is well known that such reals exist (Chaitin, Kučera/Gács).

Theorem 2 (Simpson/Stephan, 2013). ∃ nonempty effectively closed set Q such that (∀A ≤_{LR} 0) (∀Z ∈ Q) (Ω ∈ MLR ^{Z} ⇒ A ≤_{T} Z).

The proof uses a result of Miller 2010.

Summary of Theorems 1 and 2: Randomness Preservation cannot be combined with Cone Avoidance, but only because A ≰_{T} 0 does not imply A ≰_{LR} 0.

Another application.

WKL_{0} is a subsystem of Z_{2} which is good for the reverse mathematics of compactness (Heine-Borel, Arzela-Ascoli, Hahn-Banach, fixed points, prime ideals, etc.).

WWKL_{0} is a subsystem of WKL_{0} which is good for the reverse mathematics of measure theory (countable additivity, Monotone and Dominated Convergence theorems, Vitali Covering Lemma, etc.).

Let M be a countable ω-model of WWKL_{0}.

By Simpson/Yokoyama 2011, we get a countable ω-model M_{1} ⊇ M of WKL_{0} such that C ∩ M ≠ ∅ for every M_{1}-coded closed set C of positive measure.

This is called a good extension of M.

As an application of Theorem 1, we get two good extensions M_{1}, M_{2} ⊇ M such that M = M_{1} ∩ M_{2}.

Preservation of partial randomness.

Let f : {0, 1}∗ → [−∞, ∞] be an arbitrary recursive function.

For S ⊆ {0, 1}∗ let wt_{f}(S) = ∑_{σ∈S} 2^{−f(σ)}, pwt_{f}(S) = sup {wt_{f}(P) | P ⊆ S prefix-free}, and ⟦S⟧ = {X ∈ {0, 1}^{ℕ} | (∃σ ∈ S) (σ ⊂ X)}. We say that X is strongly f-random if X ∉ ⋂_{n}⟦S_{n}⟧ for all uniformly r.e. S_{n} ⊆ {0, 1}∗ such that ∀n (pwt_{f}(S_{n}) ≤ 2^{−n}).

Martin-Löf randomness is the special case f(σ) = |σ|. In this case pwt_{f}(S) = μ(⟦S⟧) where μ is the fair coin measure on {0, 1}^{ℕ}.

Partial Randomness Preservation : For any nonempty effectively closed set Q, if X is strongly f-random then (∃Z ∈ Q) (X is strongly f-random relative to Z).

More generally, if ∀i (X_{i} is strongly f_{i}-random) then (∃Z ∈ Q) ∀i (X_{i} is strongly f_{i}-random relative to Z).

Higuchi/Hudelson/Simpson/Yokoyama, 2012.

To what extent can we combine Partial Randomness Preservation with Cone Avoidance?

Theorem 3 (implicit in H/H/S/Y 2012). For any nonempty effectively closed set Q, if ∀i (A_{i} ≰_{LR} 0 and X_{i} is strongly f_{i}-random), then (∃Z ∈ Q) ∀i (A_{i} ≰_{LR} Z and X_{i} is strongly f_{i}-random relative to Z).

On the other hand, because of Theorem 2, we cannot always replace ≤_{LR} by ≤_{T}.

Can we sometimes replace ≤_{LR} by ≤_{T}?

A typical open question :

Define X to be strongly half-random ⟺ X is strongly f-random where f(σ) = |σ|/2.

If Q is nonempty effectively closed, and if A ≰_{T} 0 and X is strongly half-random, does there exist Z ∈ Q such that A ≰_{T} Z and X is strongly half-random relative to Z?

Proofs of Theorems 1 and 2.

To prove Theorem 1, we use the Cone Avoidance Basis Theorem, relativized to X.

To prove Theorem 2, we use K = prefix-free Kolmogorov complexity.

(1) If Ω ∈ MLR ^{Z} then |K(n) − K^{Z}(n)| ≤ O(1) for infinitely many n. (Miller 2010.)

(2) If Ω ∈ MLR ^{Z} and Z ∈ Q_{ω} then ∃ an infinite Z-recursive set A and a Z-recursive function K̃ such that |K(n) − K̃(n)| ≤ O(1) for all n ∈ A.

(3) Let C = plain Kolmogorov complexity. Chaitin 1976 proved: every C-trivial real is computable. Using K̃ and A as in (2), we similarly prove: every K-trivial real is ≤_{T} Z.

References.

Rodney G. Downey and Denis R. Hirschfeldt, Algorithmic Randomness and Complexity, Springer, 2010, Theory and Applications of Computability, XXVIII + 855 pages.

André Nies, Computability and Randomness, Oxford University Press, 2009, XV + 433 pages.

Jan Reimann and Theodore A. Slaman, Measures and their random reals, February 2008, 15 pages, arXiv:0802.2705v1.

Rod Downey, Denis R. Hirschfeldt, Joseph S. Miller, and André Nies, Relativizing Chaitin’s halting probability, Jounal of Mathematical Logic, 2005, 5, 167–192.

Vasco Brattka, Joseph S. Miller, and André Nies, Randomness and differentiability, 2011, 39 pages, submitted for publication.

Stephen G. Simpson and Keita Yokoyama, A nonstandard counterpart of WWKL, Notre Dame Journal of Formal Logic, 2011, 52, 229–243.

Kojiro Higuchi, W. M. Phillip Hudelson, Stephen G. Simpson, and Keita Yokoyama, Propagation of partial randomness, 2012, 26 pages, submitted for publication.

Stephen G. Simpson and Frank Stephan, Propagation of randomness and cone avoidance, 2013, in preparation.

Thank you for your attention!