Almost Everywhere Domination
Natasha L.
Dobrinen^{1}
Stephen G. Simpson^{2}
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
with respect to the
``fair coin'' probability measure on
,
and for all
Turing reducible to
X, there exists
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.
In this paper
denotes the set of natural numbers, denotes the set of total functions from
to ,
and
denotes the set of total functions from
to
.
The ``fair coin'' probability measure
on is given by
for all
and
.
A property P is said to
hold almost everywhere (abbreviated a.e.) or for almost
all
(abbreviated a.a.) if
has property
.
For
we say that f dominates g if
.
A well known theorem of axiomatic set theory reads as follows.
Theorem 1.1
Let
M be a countable transitive model of
.
Then for almost
all
we have
Here M[X] denotes the set of all sets constructible from finitely
many elements of
by ordinals belonging to M. It is
known that, for almost all
,
M[X] is a model of
.
This leads to a forcingfree proof of the independence of the
Continuum Hypothesis. See the exposition of Sacks [8].
The purpose of this paper is to investigate recursiontheoretic
analogs of Theorem 1.1, replacing the settheoretic ground
model M by the recursiontheoretic ground model
is recursive
,
and replacing M[X] by
.
Here
denotes Turing reducibility, i.e., Turing computability
relative to an oracle. Thus
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
and all
there exists
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
there exists
such that
g is not dominated by any
.
Motivated by Theorem 1.2, we make the following
definition.
Definition 2.1
We say that
is
almost everywhere dominating if
for almost all
and all
there exists
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
is almost everywhere uniformly
dominating if for almost all
there exists
such that for all
,
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
such that for almost all
and all
,
f dominates g. This
additional uniformity follows from the ZeroOne Law of probability
theory, plus countability of
REC[A].
Theorem 2.3 (Kurtz [][Theorem 4.3)
kurtzphd]
The Turing degree
0' is uniformly almost everywhere
dominating. In other words, we can find a fixed function
recursive in the Halting Problem, such that f dominates all
recursive in X for almost all
.
It follows from Theorem 2.3 that all Turing degrees
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.

.
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
be a partial function from
to .
We write
to mean that
is defined, i.e.,
domain of .
Let us say that
dominates
if
.
Definition 2.5
We say that
is
almost everywhere strongly
dominating if for almost all
and all
partial recursive in
X there exists
f recursive in
A such that
f dominates
.
We say that
is
almost
everywhere uniformly strongly dominating if for almost all
there exists
f recursive in
A such that, for all
partial recursive in
X,
f dominates
.
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.

.
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
is 2random if X is not
approximable, i.e., if there is no uniformly
sequence of sets
,
,
such that
and
for all n. Note that
X is 2random for almost all X. Our proof of Theorem
2.6 actually gives a fixed
which
dominates all functions partial recursive in X for all 2random
X. (This is because the sets U_{e,n} are uniformly
,
hence uniformly
.)
Similarly, the proof of Martin's Theorem 1.2 shows
that for all 2random 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
is weakly
2random [4, Definition II.3.1] if
for all
sets
with .
We do not
know whether there exists a function recursive in some weakly
2random 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.

.
Toward Conjecture 2.9, the following theorem of Martin
[6] is well known. Say that A is uniformly
dominating if there exists
such that f dominates
every
.
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
.
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
is regular. This means that measurable sets are
approximable from within by
sets and from without by
sets. Recall that an
is the union of countably
many closed sets, and a
is the intersection of countably
many open sets. Regularity of
means: For every measurable
set
there exist an
set S and a
set P such that
and
. See for example the classic textbook of
Halmos [2].
Attempting to reverse this measuretheoretic 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
and sets. We make the following conjecture.
Toward Conjecture 3.1, it is already known that
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
over
.
In this direction we have the following results.
Remark 3.4
Recall that
and
sets are recursiontheoretic
analogs of
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
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
model
M of
has
.
It follows by
[
12, Corollary VIII.2.18] (a consequence of the Low Basis
Theorem) that there exists an
model of
in which
fails. We thank the referee for suggesting this
observation. Furthermore, using Theorem III.2.1 of Kautz
[
4], we can build an
model
M of
such
that
is
random
relative to
X), and
is
generic relative to
X), yet
,
hence
fails in
M.
 1

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

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

Peter G. Hinman.
RecursionTheoretic Hierarchies.
Perspectives in Mathematical Logic. SpringerVerlag, 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 UrbanaChampaign, 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:295310, 1966.
 7

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

Gerald E. Sacks.
Measuretheoretic uniformity in recursion theory and set theory.
Transactions of the American Mathematical Society,
142:381420, 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.
sets and models of
.
In [10].
Preprint, April 2000, 29 pages, to appear.
 12

Stephen G. Simpson.
Subsystems of Second Order Arithmetic.
Perspectives in Mathematical Logic. SpringerVerlag, 1999.
XIV + 445 pages.
 13

Robert I. Soare.
Recursively Enumerable Sets and Degrees.
Perspectives in Mathematical Logic. SpringerVerlag, 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.
RadonNikodym theorem is equivalent to arithmetical comprehension.
In [9], pages 289297, 1990.
 16

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

Xiaokang Yu.
Lebesgue convergence theorems and reverse mathematics.
Mathematical Logic Quarterly, 40:113, 1994.
 18

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

Xiaokang Yu and Stephen G. Simpson.
Measure theory and weak König's lemma.
Archive for Mathematical Logic, 30:171180, 1990.
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 20040518
Footnotes
 ... Dobrinen^{1}
 http://www.math.psu.edu/dobrinen/.
Dobrinen's research was partially supported by NSF VIGRE
Grant DMS9810759.
 ... Simpson^{2}
 http://www.personal.psu.edu/t20/.
Simpson's research was partially supported by NSF Grant
DMS0070718.
Stephen G Simpson
20040518