Almost Everywhere Domination

Natasha L. Dobrinen¹
Stephen G. Simpson²

Department of Mathematics
Pennsylvania State University

May 18, 2004

to appear in the Journal of Symbolic Logic
originally submitted March 17, 2004

Abstract:

A Turing degree a is said to be almost everywhere dominating if, for almost all $X\in2^\omega$ with respect to the ``fair coin'' probability measure on $2^\omega$, and for all $g:\omega\to\omega$ Turing reducible to X, there exists $f:\omega\to\omega$ of Turing degree a which dominates g. We study the problem of characterizing the almost everywhere dominating Turing degrees and other, similarly defined classes of Turing degrees. We relate this problem to some questions in the reverse mathematics of measure theory.

Introduction

In this paper $\omega$ denotes the set of natural numbers, $2^\omega$denotes the set of total functions from $\omega$ to $\{0,1\}$, and $\omega^\omega$ denotes the set of total functions from $\omega$ to $\omega$. The ``fair coin'' probability measure $\mu$ on $2^\omega$is given by

$\mu(\{X\in2^\omega\mid X(n)=i\})=1/2$

for all $n\in\omega$ and $i\in\{0,1\}$. A property P is said to hold almost everywhere (abbreviated a.e.) or for almost all $X\in2^\omega$ (abbreviated a.a.) if

$\mu(\{X\in2^\omega\mid X$ has property $P\})=1$.

For $f,g\in\omega^\omega$ we say that f dominates g if

$\exists m\,\forall n\,(n\ge m\Rightarrow f(n)>g(n))$.

A well known theorem of axiomatic set theory reads as follows.

Theorem 1.1   Let M be a countable transitive model of $\mathsf{ZFC}$. Then for almost all $X\in2^\omega$ we have

$$( \forall g\in M[X]\cap\omega^\omega)\,(\exists f\in M\cap\omega^\omega)\,(f\mbox{ dominates }g)\,.$$

Here M[X] denotes the set of all sets constructible from finitely many elements of $M\cup\{X\}$ by ordinals belonging to M. It is known that, for almost all $X\in2^\omega$, M[X] is a model of $\mathsf{ZFC}$. This leads to a forcing-free proof of the independence of the Continuum Hypothesis. See the exposition of Sacks [8].

The purpose of this paper is to investigate recursion-theoretic analogs of Theorem 1.1, replacing the set-theoretic ground model M by the recursion-theoretic ground model

$\mathrm{REC}=\{f\in\omega^\omega\mid f$ is recursive$\}\,$,

and replacing M[X] by

$\mathrm{REC}[X]=\{g\in\omega^\omega\mid g\le_TX\}\,$.

Here $\le_T$ denotes Turing reducibility, i.e., Turing computability relative to an oracle. Thus $g\le_TX$ if and only if g is recursive in X, i.e., g is Turing computable using an oracle for X.

In analogy with Theorem 1.1, it would be natural to conjecture that for almost all $X\in2^\omega$ and all $g\in\mathrm{REC}[X]$there exists $f\in\mathrm{REC}$ such that f dominates g. However, this is not the case, as shown by the following result of Martin [7]. Since the proof of Theorem 1.2 has not been published, we present it below.

Theorem 1.2 (Martin [7])   For almost all $X\in2^\omega$ there exists $g\in\mathrm{REC}[X]$ such that g is not dominated by any $f\in\mathrm{REC}$.

Almost everywhere domination

Motivated by Theorem 1.2, we make the following definition.

Definition 2.1   We say that $A\in2^\omega$ is almost everywhere dominating if for almost all $X\in2^\omega$ and all $g\in\mathrm{REC}[X]$ there exists $f\in\mathrm{REC}[A]$ such that f dominates g.

Note that this property of A depends only on the Turing degree of A. In these terms, Theorem 1.2 says that , the Turing degree of recursive functions, is not almost everywhere dominating. In this paper we raise the problem of characterizing the Turing degrees which are almost everywhere dominating.

The following theorem of Kurtz [5] implies that 0', the Turing degree of the Halting Problem, is almost everywhere dominating. We consider an apparently more restrictive property.

Definition 2.2   We say that $A\in2^\omega$ is almost everywhere uniformly dominating if for almost all $X\in2^\omega$ there exists $f\in\mathrm{REC}[A]$ such that for all $g\in\mathrm{REC}[X]$, f dominates g.

Again, this property of A depends only on the Turing degree of A. Note also that, if A is almost everywhere uniformly dominating, then A is uniformly almost everywhere dominating, i.e., there exists a fixed function $f\in\mathrm{REC}[A]$ such that for almost all $X\in2^\omega$ and all $g\in\mathrm{REC}[X]$, f dominates g. This additional uniformity follows from the Zero-One Law of probability theory, plus countability of REC[A].

Theorem 2.3 (Kurtz [][Theorem 4.3)   kurtz-phd]   The Turing degree 0' is uniformly almost everywhere dominating. In other words, we can find a fixed function $f\in\omega^\omega$ recursive in the Halting Problem, such that f dominates all $g\in\omega^\omega$ recursive in X for almost all $X\in2^\omega$.

It follows from Theorem 2.3 that all Turing degrees $\ge\mathbf{0'}$ are uniformly almost everywhere dominating. We make the following conjecture.

Conjecture 2.4   Let a be a Turing degree. The following are pairwise equivalent.

1.

a is almost everywhere dominating.

2.

a is uniformly almost everywhere dominating.

3.

$\mathbf{a}\ge\mathbf{0'}$.

Conjecture 2.4 is perhaps too good to be true. However, we have the following result, Theorem 2.6, which improves Theorem 2.3 and provides a kind of converse to it. Let $\psi$ be a partial function from $\omega$ to $\omega$. We write $\psi(n)\downarrow$ to mean that $\psi(n)$ is defined, i.e., $n\in$ domain of $\psi$. Let us say that $f\in\omega^\omega$dominates $\psi$ if

$\exists m\,\forall n\,((n\ge m\land\psi(n)\downarrow)\Rightarrow f(n)>\psi(n))\,$.

Definition 2.5   We say that $A\in2^\omega$ is almost everywhere strongly dominating if for almost all $X\in2^\omega$ and all $\psi$ partial recursive in X there exists f recursive in A such that f dominates $\psi$. We say that $A\in2^\omega$ is almost everywhere uniformly strongly dominating if for almost all $X\in2^\omega$ there exists f recursive in A such that, for all $\psi$ partial recursive in X, f dominates $\psi$.

Again, if A is almost everywhere uniformly strongly dominating, then A is uniformly almost everywhere strongly dominating, and all of these notions depend only on the Turing degree of A. We have the following new result.

Theorem 2.6   Let a be a Turing degree. The following are pairwise equivalent.

1.

a is almost everywhere strongly dominating.

2.

a is uniformly almost everywhere strongly dominating.

3.

$\mathbf{a}\ge\mathbf{0'}$.

 

Remark 2.7   Our proof of Theorem 2.6 actually gives a more precise result. Following Kautz [4, Definition II.1.2], let us say that $X\in2^\omega$ is 2-random if X is not $\Sigma^0_2$-approximable, i.e., if there is no uniformly $\Sigma^0_2$ sequence of sets $V_n\subseteq2^\omega$, $n\in\omega$, such that $\mu(V_n)<1/2^n$ and $X\in V_n$ for all n. Note that X is 2-random for almost all X. Our proof of Theorem 2.6 actually gives a fixed $g\le_T\mathbf{0'}$ which dominates all functions partial recursive in X for all 2-random X. (This is because the sets U_e,n are uniformly $\Sigma^{0,\mathbf{0'}}_1$, hence uniformly $\Sigma^0_2$.) Similarly, the proof of Martin's Theorem 1.2 shows that for all 2-random X there exists a total function recursive in X which is not dominated by any recursive function. (See also Kautz [4, Theorem IV.2.4, part (iv)].) On the other hand, let us say that $X\in2^\omega$ is weakly 2-random [4, Definition II.3.1] if $X\in V$ for all $\Sigma^0_2$ sets $V\subseteq2^\omega$ with $\mu(V)=1$. We do not know whether there exists a function recursive in some weakly 2-random X which is not dominated by any function recursive in 0'.

An alternative to Conjecture 2.4 is the following, where a' denotes the Turing jump of a.

Conjecture 2.8   Let a be a Turing degree. The following are pairwise equivalent.

1.

a is almost everywhere dominating.

2.

a is uniformly almost everywhere dominating.

3.

$\mathbf{a'}\ge\mathbf{0''}$.

Toward Conjecture 2.9, the following theorem of Martin [6] is well known. Say that A is uniformly dominating if there exists $f\in\mathrm{REC}[A]$ such that f dominates every $g\in\mathrm{REC}$. Again, this is a property of the Turing degree of A.

Theorem 2.9 (Martin [6])   A Turing degree a is uniformly dominating if and only if $\mathbf{a'}\ge\mathbf{0''}$.

Corollary 2.10   If a is almost everywhere uniformly dominating, then $\mathbf{a'}\ge\mathbf{0''}$.

Connection to reverse mathematics

In this section we exhibit a relationship between almost everywhere domination and the reverse mathematics of measure theory.

Reverse mathematics is a well known program of determining the weakest set existence axioms needed to prove specific mathematical theorems. This is carried out in the context of subsystems of second order arithmetic. For general background, see Simpson [12]. Other results on the reverse mathematics of measure theory are in the papers of Yu [14,15,16,17,18], Yu/Simpson [19], and Brown/Giusto/Simpson [1].

A well known result in measure theory asserts that the fair coin measure $\mu$ is regular. This means that measurable sets are approximable from within by $F_\sigma$ sets and from without by $G_\delta$ sets. Recall that an $F_\sigma$ is the union of countably many closed sets, and a $G_\delta$ is the intersection of countably many open sets. Regularity of $\mu$ means: For every measurable set $Q\subseteq2^\omega$ there exist an $F_\sigma$ set S and a $G_\delta$ set P such that $S\subseteq Q\subseteq P$ and $\mu(S)=\mu(Q)=\mu(P)$. See for example the classic textbook of Halmos [2].

Attempting to reverse this measure-theoretic result, we encounter the difficulty that arbitrary measurable sets cannot be discussed in the language of second order arithmetic. However, we can discuss sets defined by arithmetical formulas, including $F_\sigma$ and $G_\delta$sets. We make the following conjecture.

Conjecture 3.1   The following are pairwise equivalent over $\mathsf{RCA}_0$.

1.

$\mathsf{ACA}_0$.

2.

Given a $G_\delta$ set $Q\subseteq2^\omega$, we can find an $F_\sigma$ set $S\subseteq Q$ such that $\mu(S)=\mu(Q)$.

3.

Given a $G_\delta$ set $Q\subseteq2^\omega$, and given $\epsilon>0$, we can find a closed set $F\subseteq Q$ such that $\mu(F)\ge\mu(Q)-\epsilon$.

4.

Given a $G_\delta$ set $Q\subseteq2^\omega$ with $\mu(Q)>0$, we can find a closed set $F\subseteq Q$ such that $\mu(F)>0$.

Toward Conjecture 3.1, it is already known that $\mathsf{ACA}_0$implies statement 2. See for example Hinman [3, Lemma III.4.20] and Kautz [4, Lemma II.1.4]. And clearly 2 implies 3, which implies 4. Thus, we would like to prove that any or all of statements 2, 3, 4 imply $\mathsf{ACA}_0$ over $\mathsf{RCA}_0$.

In this direction we have the following results.

Theorem 3.2   For $A\in2^\omega$ the following are equivalent.

1.

A is uniformly almost everywhere dominating.

2.

Given a $\Pi^0_2$ set $Q\subseteq2^\omega$, we can find a $\Sigma^{0,A}_2$ set $S\subseteq Q$ such that $\mu(S)=\mu(Q)$.

Theorem 3.3   For $A\in2^\omega$ the following are equivalent.

1.

A is almost everywhere dominating.

2.

Given a $\Pi^0_2$ set $Q\subseteq2^\omega$, and given $\epsilon>0$, we can find a $\Pi^{0,A}_1$ set $F\subseteq Q$ such that $\mu(F)\ge\mu(Q)-\epsilon$.

Remark 3.4   Recall that $\Pi^0_2$ and $\Pi^0_1$ sets are recursion-theoretic analogs of $G_\delta$ sets and closed sets, respectively. See for example Hinman [3, Theorem III.1.16]. From this viewpoint, the properties mentioned in Theorems 3.2 and 3.3 are analogous to statements 2 and 3 in Conjecture 3.1, respectively. Thus, it seems reasonable to think that progress on Conjecture 2.4 in recursion theory may lead to progress on Conjecture 3.1 in reverse mathematics.

Remark 3.5   In particular, let $(\star)$ be statement 2 of Conjecture 3.1. By relativizing and formalizing the proofs of Corollary 2.11 and Theorem 3.2, we can show that any $\omega$-model M of $\mathsf{WKL}_0+(\star)$ has $(\forall X{\in}M)(\exists Y{\in}M)(Y'\ge_TX'')$. It follows by [12, Corollary VIII.2.18] (a consequence of the Low Basis Theorem) that there exists an $\omega$-model of $\mathsf{WKL}_0$ in which $(\star)$ fails. We thank the referee for suggesting this observation. Furthermore, using Theorem III.2.1 of Kautz [4], we can build an $\omega$-model M of $\mathsf{WKL}_0$ such that $(\forall X{\in}M)(\exists Y{\in}M)(Y$ is $\omega$-random relative to X), and $(\forall X{\in}M)(\exists Y{\in}M)(Y$ is $\omega$-generic relative to X), yet $(\forall Y{\in}M)(Y'\not\ge_T0'')$, hence $(\star)$ fails in M.

Bibliography

1

Douglas K. Brown, Mariagnese Giusto, and Stephen G. Simpson.
Vitali's theorem and WWKL.
Archive for Mathematical Logic, 41:191-206, 2002.

2

Paul R. Halmos.
Measure Theory.
Van Nostrand, 1950.
XI + 304 pages.

3

Peter G. Hinman.
Recursion-Theoretic Hierarchies.
Perspectives in Mathematical Logic. Springer-Verlag, 1978.
XII + 480 pages.

4

Steven M. Kautz.
Degrees of Random Sets.
PhD thesis, Cornell University, 1991.
X + 89 pages.

5

Stuart A. Kurtz.
Randomness and Genericity in the Degrees of Unsolvability.
PhD thesis, University of Illinois at Urbana-Champaign, 1981.
VII + 131 pages.

6

Donald A. Martin.
Classes of recursively enumerable sets and degrees of unsolvability.
Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 12:295-310, 1966.

7

Donald A. Martin.
Measure, category, and degrees of unsolvability.
Unpublished, typewritten, 16 pages, 1967.

8

Gerald E. Sacks.
Measure-theoretic uniformity in recursion theory and set theory.
Transactions of the American Mathematical Society, 142:381-420, 1969.

9

W. Sieg, editor.
Logic and Computation.
Contemporary Mathematics. American Mathematical Society, 1990.
XIV + 297 pages.

10

S. G. Simpson, editor.
Reverse Mathematics 2001.
Lecture Notes in Logic. Association for Symbolic Logic, 2004.
To appear.

11

Stephen G. Simpson.
$\Pi^0_1$ sets and models of $\mathsf{WKL}_0$.
In [10].
Preprint, April 2000, 29 pages, to appear.

12

Stephen G. Simpson.
Subsystems of Second Order Arithmetic.
Perspectives in Mathematical Logic. Springer-Verlag, 1999.
XIV + 445 pages.

13

Robert I. Soare.
Recursively Enumerable Sets and Degrees.
Perspectives in Mathematical Logic. Springer-Verlag, 1987.
XVIII + 437 pages.

14

Xiaokang Yu.
Measure Theory in Weak Subsystems of Second Order Arithmetic.
PhD thesis, Pennsylvania State University, 1987.
VII + 73 pages.

15

Xiaokang Yu.
Radon-Nikodym theorem is equivalent to arithmetical comprehension.
In [9], pages 289-297, 1990.

16

Xiaokang Yu.
Riesz representation theorem, Borel measures, and subsystems of second order arithmetic.
Annals of Pure and Applied Logic, 59:65-78, 1993.

17

Xiaokang Yu.
Lebesgue convergence theorems and reverse mathematics.
Mathematical Logic Quarterly, 40:1-13, 1994.

18

Xiaokang Yu.
A study of singular points and supports of measures in reverse mathematics.
Annals of Pure and Applied Logic, 79:211-219, 1996.

19

Xiaokang Yu and Stephen G. Simpson.
Measure theory and weak König's lemma.
Archive for Mathematical Logic, 30:171-180, 1990.

About this document ...

Almost Everywhere Domination

This document was generated using the LaTeX2HTML translator Version 98.1p1 release (March 2nd, 1998)

Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -split 0 aedom.

The translation was initiated by Stephen G Simpson on 2004-05-18

Footnotes

... Dobrinen¹

http://www.math.psu.edu/dobrinen/. Dobrinen's research was partially supported by NSF VIGRE Grant DMS-9810759.

... Simpson²

http://www.math.psu.edu/simpson/. Simpson's research was partially supported by NSF Grant DMS-0070718.