Remark 7.10
By Jockusch [
25, Theorem 5] each
is weakly
complete, i.e., of weak degree
. Let
be the strong degree of
. It is
well known (see also the proof of Corollary
7.6 above)
that
is strongly complete, i.e.,
in
. By Jockusch [
25, Theorem
6] we have
in
. See also Simpson [
54, Remark 3.21].
We have the following new result.
Corollary 7.11
Let and be subsets of . Assume that
is of positive measure. Let
be the strong
degrees of respectively. For each , if
, then
. In particular we have
.
Remark 7.12
In Corollary
7.11, we do not know whether it is
necessarily the case that
, or
for all
.
sets of random reals
In this section we exhibit a particular degree
and
note some of its degreetheoretic properties.
As in Section 7, let denote the fair coin
probability measure on .
Definition 8.1
An
effective null is a set
of
the form
where
is
a recursive sequence of
subsets of
with
for all
. A point
is said to
be
random if
for all effective null
sets
.
Remark 8.2
The notion of randomness in Definition
8.1 is due to
MartinLøf [
39] and has been studied extensively.
It appears to be the most general and natural notion of algorithmic
randomness for infinite sequences of
's and
's. It has also
been called
MartinLøf randomness (Li/Vitányi
[
37, Section 2.5]),
1randomness (Kurtz
[
28], Kautz [
27]), and
the NAP
property (Kucera
[
29,
30,
31,
32,
33,
34,
35]).
It is closely related to Kolmogorov complexity (see Li/Vitányi
[
37]).
The following theorem is well known. It says that the union of all
effective null sets is an effective null set.
Notation 8.5
We use the following notation for shifts:
. Note
that
is a mapping of
into
.
Lemma 8.6
For all and , is random if and only
if is random.
The next lemma is an effective version of the ZeroOne Law of
probability theory.
Lemma 8.7
Let be random. Let
be with
. Then
.
Lemma 8.8
Let be random. Then for all sets
, if then .
Theorem 8.10
Let
where
is
random. Then can be characterized as the unique
largest weak degree of a set
such
that .
Remark 8.11
Theorem
8.10 tells us that, among all weak degrees of
sets of positive measure, there exists a unique largest
degree. Simpson/Slaman [
55] and independently Terwijn
[
58] have shown that, among all strong degrees of
sets of positive measure, there is no largest or even
maximal degree.
We end this section by noting some additional properties of the
particular weak degree which was defined in Theorem
8.10.
Theorem 8.12
Let be the weak degree of
is
random. Then:

, and
.
 For all
, if
then
.
 For all
, if
then either
or
.
 There is no separating
such that
.
Corollary 8.13
The weak degree
is meet irreducible and does not
join to in .
Thin subsets of
In this section we discuss an interesting class of degrees in ,
each of which is incomparable with the particular degree
of Section 8.
We begin with some generalities concerning thin sets.
Definition 9.1
A
set
is said to be
thin
if, for all
sets
, the settheoretic
difference
is
.
Lemma 9.2
Let be a recursively bounded set. Then is thin if
and only if all subsets of are trivial, i.e.,
they are of the form
for some finite set of strings
.
Theorem 9.3
Let be a nonempty thin recursively bounded set. Then
is isolated if and only if is recursive. In
particular, is perfect if and only if and only if has no
recursive members, i.e.,
.
Lemma 9.4
Let be a thin recursively bounded set. Then:
 Every subset of is thin and recursively bounded.
 Let
be the image of under a
recursive functional
. Then is a thin
recursively bounded set.
Theorem 9.5
If is a thin recursively bounded set, then is
recursively homeomorphic to a thin set
. Moreover, is perfect if and only if
is perfect.
Remark 9.6
There is a large literature on thin perfect
subsets of
going back to Martin/PourEl [
38]. See
Downey/Jockusch/Stob [
15,
16]
and Cholak et al [
11]. Typically, thin perfect
subsets of
are constructed by means of priority
arguments. In this sense, thin perfect
subsets of
and their weak and strong degrees are artificial or
unnatural. In particular, thin perfect
subsets of
have been used by Binns/Simpson [
6] to
embed countable distributive lattices into
and
.
Remark 9.7
Let
where
is any nonempty thin perfect
recursively bounded
set. Obviously
.
Let
where
is
random
. We have seen in Theorem
8.10 that
. Our goal in this section is to prove Theorem
9.15, which says that
and
are
incomparable, i.e.,
and
. By Theorem
9.5, it
suffices to prove this in the special case when
is a nonempty
thin perfect
subset of
.
Remark 9.9
We do not know the answer to the following question. If
is a
thin perfect
subset of
, does it follow that the
Turing upward closure
is of measure 0?
Lemma 9.10
Let be a nonempty thin subset of . If
is random, and if is almost recursive, then .
In particular, .
Lemma 9.11
Let be random. If is nonrecursive, then
there exists
such that
and is random.
Lemma 9.12
Let be random and almost recursive. If is
nonrecursive, then there exists
such that
and is random.
Lemma 9.13
Let be a nonempty thin perfect subset of .
If , and if is random and almost recursive,
then . In particular , and
for all sets
of positive measure.
Summarizing, we have:
Lemma 9.14
Let
be almost recursive. Assume that is
random, and assume that where is a thin perfect
subset of . Then and
, i.e., the Turing degrees of and are
incomparable.
Theorem 9.15
Let
where is a nonempty thin perfect
subset of . Let
where
is random. Then and
are incomparable weak degrees in .
Corollary 9.16
There exist
in such
that is separating and
is not
separating. Indeed, every separating
which is
is .
Some additional natural examples in
In this section we present some additional natural examples in ,
including a hierarchy of weak degrees in corresponding to the
transfinite Ackermann hierarchy from proof theory.
Definition 10.1
Put
,
the set of
diagonally nonrecursive functions. The set of
Turing degrees of members of
has been studied by Jockusch
[
25]. Note that
is nonempty and
.
If
is a recursive function such that
for all
, put
,
the set of
bounded
functions. In addition, put
is recursive
, the set of
recursively bounded
functions.
Remark 10.2
Trivially
hence
, hence
. According to AmbosSpies et al
[
2, Theorems 1.8 and 1.9], we have strict inequalities
As in Section
8, let
be the set of random reals. An
argument of Kurtz (see Jockusch [
25, Proposition 3])
shows that
provided
is such that
, for example
.
Remark 10.3
Since
is nonempty, recursively bounded, and
, we
have
and
. Although
and
are not recursively bounded, it will be shown
in Simpson [
48] that
and
. We do not know whether
, or whether
. Put
,
,
,
. Summarizing,
we have the following result.
Theorem 10.4
In we have
for all sufficiently fastgrowing recursive functions
.
Remark 10.5
Some of our natural weak degrees are closely related to certain
formal systems which arise naturally in the foundations of
mathematics. Namely, the weak degrees
,
,
correspond to the systems
,
,
respectively. Each of these subsystems of second order
arithmetic is of interest in connection with the well known
foundational program of reverse mathematics. See Simpson
[
52, Chapter IV and Section X.1], Yu/Simpson
[
61], Brown/Giusto/Simpson [
7], and
Giusto/Simpson [
23]. The standard reference for reverse
mathematics is Simpson [
52].
Remark 10.6
From the recursiontheoretic viewpoint, there are some subtle issues
concerning naturalness of the mass problems
,
,
and of their weak degrees
,
,
. First,
,
,
are not
invariant under recursive permutations of
, and on this
basis it is possible to question their recursiontheoretic
naturalness. (See also the discussion of the recursiontheoretic
Erlanger Programm in Rogers [
45, Chapter 4].) On the other
hand, this objection clearly does not apply to the weak degrees
,
,
, because all weak
and strong degrees are invariant under recursive permutations of
. Second, one may note that our definitions of
,
,
and their weak degrees
,
,
depend upon a particular choice of
Gödel numbering of Turing machines, because the function
is defined in terms of such a Gödel numbering.
(See also the discussion of acceptable Gödel numberings in Rogers
[
45].) We shall now present a method of overcoming this
objection. Our idea is to replace the particular partial recursive
function
by an arbitrary partial recursive
function
. This will answer the objection, because
the extensional concept ``partial recursive function'' is
independent of the choice of Gödel numbering.
Definition 10.7
Let
be the set of
such that for all
partial recursive functions
there exists
such that
. Let
be the set of
such that for all partial recursive functions
there exists
such that
and
for some recursive function
.
Remark 10.8
Using the Smn Theorem, it is easy to see that
and
.
(See also the proof of Theorem
10.10 below.) Thus the weak
degrees
and
are natural in the sense
that they can be defined in a way that does not depend on the choice
of Gödel numbering. What about
where
is a
fixed recursive function? Let
be the set of
such that for all partial recursive functions
there exists
such that
and
. It is not clear that
for a fixed recursive function
, but
we have the following definition and theorem for classes of
recursive functions.
Definition 10.9
If
is a class of recursive functions, put
. Let
be the set of
such that for all partial recursive functions
there exists
such that
and
for some
.
Theorem 10.10
If is closed under composition with primitive recursive
functions, then
. If there exists a
uniform recursive enumeration of , then
.
Theorem 10.11
Let be a subset of . Then we can find a
set
such that is Turing degree
isomorphic to .
Remark 10.12
In the proof of Theorem
10.11, note that
, where
and
. Thus the proof shows that
is
closed under effective infima.
Remark 10.13
If
is a class of recursive functions satisfying the hypotheses
of Theorem
10.10, put
. We
have seen that
and that
is
natural in the sense that it can be defined in a way which does not
depend on the choice of Gödel numbering. Moreover, if
is another such class, then
, and according to AmbosSpies
et al [
2, Theorem 1.9] we have strict inequality
provided
contains a
function which ``grows much faster than'' all functions in
.
There are many examples and problems here.
Example 10.14
For each constructive ordinal
, let
be the class
of recursive functions obtained at levels
of the transfinite Ackermann hierarchy. (See for instance Wainer
[
60].) Thus
is the class of primitive
recursive functions,
is the class of functions which are
primitive recursive relative to the Ackermann function, etc.
Putting
we have a
transfinite descending sequence
in
. Moreover, if
is a limit ordinal, then
. Thus we
see a rich set of natural degrees in
which are related to
subrecursive hierarchies of the kind that arise in Gentzenstyle
proof theory.
Remark 10.15
Let us assume that we are using one of the standard Gödel
numberings of Turing machines which appear in the literature. Then
the function
in the proof of Theorem
10.10 can be
chosen to be bounded by a linear function. Therefore, instead of
assuming that
is closed under composition with primitive
recursive functions, we could assume merely that for all
and
there exists
such that
for all
. In particular, we can take
to
be various well known computational complexity classes such as
PTIME, EXPTIME, etc. For each such class, Theorem
10.10
shows that the weak degree
is natural in that
its definition does not depend on the choice of a standard Gödel
numbering.
Example 10.16
In
we have
etc. Thus we see a rich set of natural degrees in
which are
related to computational complexity.
 1

K. AmbosSpies, G. H. Müller, and G. E. Sacks, editors.
Recursion Theory Week.
Number 1432 in Lecture Notes in Mathematics. SpringerVerlag,
1990.
IX + 393 pages.
 2

Klaus AmbosSpies, Bjørn KjosHanssen, Steffen Lempp, and Theodore A.
Slaman.
Comparing DNR and WWKL.
Journal of Symbolic Logic, 69:10891104, 2004.
 3

Stephen Binns.
The Medvedev and Muchnik Lattices of
Classes.
PhD thesis, Pennsylvania State University, August 2003.
VII + 80 pages.
 4

Stephen Binns.
A splitting theorem for the Medvedev and Muchnik lattices.
Mathematical Logic Quarterly, 49:327335, 2003.
 5

Stephen Binns.
Small classes.
Archive for Mathematical Logic, 45:393410, 2006.
 6

Stephen Binns and Stephen G. Simpson.
Embeddings into the Medvedev and Muchnik lattices of
classes.
Archive for Mathematical Logic, 43:399414, 2004.
 7

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

P. Bruscoli and A. Guglielmi, editors.
Summer School and Workshop on Proof Theory, Computation and
Complexity, Dresden, 2003.
Electronic Notes in Theoretical Computer Science. Elsevier,
2004.
To appear.
 9

Douglas Cenzer and Peter G. Hinman.
Density of the Medvedev lattice of classes.
Archive for Mathematical Logic, 42:583600, 2003.
 10

Douglas Cenzer and Jeffrey B. Remmel.
classes in mathematics.
In [20], pages 623821, 1998.
 11

Peter Cholak, Richard Coles, Rod Downey, and Eberhard Herrmann.
Automorphisms of the lattice of classes; perfect thin
classes and ANC degrees.
Transactions of the American Mathematical Society,
353:48994924, 2001.
 12

COMPTHY email list.
http://listserv.nd.edu/archives/compthy.html, September
1995 to the present.
 13

S. B. Cooper, T. A. Slaman, and S. S. Wainer, editors.
Computability, Enumerability, Unsolvability: Directions in
Recursion Theory.
Number 224 in London Mathematical Society Lecture Notes.
Cambridge University Press, 1996.
VII + 347 pages.
 14

Oswald Demuth.
A notion of semigenericity.
Commentationes Mathematicae Universitatis Carolinae, 28:7184,
1987.
 15

Rodney G. Downey, Carl G. Jockusch, Jr., and Michael Stob.
Array nonrecursive sets and multiple permitting arguments.
In [1], pages 141174, 1990.
 16

Rodney G. Downey, Carl G. Jockusch, Jr., and Michael Stob.
Array nonrecursive degrees and genericity.
In [13], pages 93105, 1996.
 17

F. R. Drake and J. K. Truss, editors.
Logic Colloquium '86.
Studies in Logic and the Foundations of Mathematics.
NorthHolland, 1988.
X + 342 pages.
 18

H.D. Ebbinghaus, J. FernandezPrida, M. Garrido, D. Lascar, and M. Rodriguez
Artalejo, editors.
Logic Colloquium '87.
Studies in Logic and the Foundations of Mathematics.
NorthHolland, 1989.
X + 375 pages.
 19

H.D. Ebbinghaus, G. H. Müller, and G. E. Sacks, editors.
Recursion Theory Week.
Number 1141 in Lecture Notes in Mathematics. SpringerVerlag,
1985.
IX + 418 pages.
 20

Y. L. Ershov, S. S. Goncharov, A. Nerode, and J. B. Remmel, editors.
Handbook of Recursive Mathematics.
Studies in Logic and the Foundations of Mathematics.
NorthHolland, 1998.
Volumes 1 and 2, XLVI + 1372 pages.
 21

J.E. Fenstad, I. T. Frolov, and R. Hilpinen, editors.
Logic, Methodology and Philosophy of Science VIII.
Studies in Logic and the Foundations of Mathematics.
NorthHolland, 1989.
XVII + 702 pages.
 22

FOM email list.
http://www.cs.nyu.edu/mailman/listinfo/fom/, September 1997
to the present.
 23

Mariagnese Giusto and Stephen G. Simpson.
Located sets and reverse mathematics.
Journal of Symbolic Logic, 65:14511480, 2000.
 24

J. Gruska, B. Rovan, and J. Wiedermann, editors.
Mathematical Foundations of Computer Science.
Number 233 in Lecture Notes in Computer Science.
SpringerVerlag, 1986.
IX + 650 pages.
 25

Carl G. Jockusch, Jr.
Degrees of functions with no fixed points.
In [21], pages 191201, 1989.
 26

Carl G. Jockusch, Jr. and Robert I. Soare.
classes and degrees of theories.
Transactions of the American Mathematical Society, 173:3556,
1972.
 27

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

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

Antonín Kucera.
Measure, classes and complete extensions of PA.
In [19], pages 245259, 1985.
 30

Antonín Kucera.
An alternative, priorityfree, solution to Post's problem.
In [24], pages 493500, 1986.
 31

Antonín Kucera.
On the role of in recursion theory.
In [17], pages 133141, 1988.
 32

Antonín Kucera.
On the use of diagonally nonrecursive functions.
In [18], pages 219239, 1989.
 33

Antonín Kucera.
Randomness and generalizations of fixed point free functions.
In [1], pages 245254, 1990.
 34

Antonín Kucera.
On relative randomness.
Annals of Pure and Applied Logic, 63:6167, 1993.
 35

Antonín Kucera and Sebastiaan A. Terwijn.
Lowness for the class of random sets.
Journal of Symbolic Logic, 64:13961402, 1999.
 36

Manuel Lerman.
Degrees of Unsolvability.
Perspectives in Mathematical Logic. SpringerVerlag, 1983.
XIII + 307 pages.
 37

Ming Li and Paul Vitányi.
An Introduction to Kolmogorov Complexity and its
Applications.
Graduate Texts in Computer Science. SpringerVerlag, 2nd
edition, 1997.
XX + 637 pages.
 38

Donald A. Martin and Marian B. PourEl.
Axiomatizable theories with few axiomatizable extensions.
Journal of Symbolic Logic, 35:205209, 1970.
 39

Per MartinLöf.
The definition of random sequences.
Information and Control, 9:602619, 1966.
 40

Yuri T. Medvedev.
Degrees of difficulty of mass problems.
Doklady Akademii Nauk SSSR, n.s., 104:501504, 1955.
In Russian.
 41

A. A. Muchnik.
On strong and weak reducibilities of algorithmic problems.
Sibirskii Matematicheskii Zhurnal, 4:13281341, 1963.
In Russian.
 42

Piergiorgio Odifreddi.
Classical Recursion Theory.
Number 125 in Studies in Logic and the Foundations of
Mathematics. NorthHolland, 1989.
XVII + 668 pages.
 43

Piergiorgio Odifreddi.
Classical Recursion Theory, Volume 2.
Number 143 in Studies in Logic and the Foundations of
Mathematics. NorthHolland, 1999.
XVI + 949 pages.
 44

Emil L. Post.
Recursively enumerable sets of positive integers and their decision
problems.
Bulletin of the American Mathematical Society, 50:284316,
1944.
 45

Hartley Rogers, Jr.
Theory of Recursive Functions and Effective
Computability.
McGrawHill, 1967.
XIX + 482 pages.
 46

Gerald E. Sacks.
Degrees of Unsolvability.
Number 55 in Annals of Mathematics Studies. Princeton University
Press, 1963.
IX + 174 pages.
 47

S. G. Simpson, editor.
Reverse Mathematics 2001, volume 21 of Lecture Notes
in Logic.
Association for Symbolic Logic, 2005.
X + 401 pages.
 48

Stephen G. Simpson.
An extension of the recursively enumerable Turing degrees.
Journal of the London Mathematical Society.
Preprint, August 2004, 15 pages, accepted for publication.
 49

Stephen G. Simpson.
Mass problems.
Preprint, May 24, 2004, 24 pages, submitted for publication.
 50

Stephen G. Simpson.
FOM: natural r.e. degrees; Pi01 classes.
FOM email list [22], August 13, 1999.
 51

Stephen G. Simpson.
FOM: priority arguments; Kleener.e. degrees; Pi01 classes.
FOM email list [22], August 16, 1999.
 52

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

Stephen G. Simpson.
Medvedev degrees of nonempty Pi01 subsets of
2omega.
COMPTHY email list [12], June 9, 2000.
 54

Stephen G. Simpson.
sets and models of
.
In [47], pages 352378. 2005.
 55

Stephen G. Simpson and Theodore A. Slaman.
Medvedev degrees of subsets of .
Preprint, July 2001, 4 pages, in preparation.
 56

Robert I. Soare.
Recursively Enumerable Sets and Degrees.
Perspectives in Mathematical Logic. SpringerVerlag, 1987.
XVIII + 437 pages.
 57

Andrea Sorbi.
The Medvedev lattice of degrees of difficulty.
In [13], pages 289312, 1996.
 58

Sebastiaan A. Terwijn.
The Medvedev lattice of computably closed sets.
Archive for Mathematical Logic.
Preprint, June 2004, 22 pages, accepted for publication.
 59

Alan M. Turing.
On computable numbers, with an application to the
Entscheidungsproblem.
Proceedings of the London Mathematical Society, 42:230265,
1936.
 60

Stanley S. Wainer.
A classification of the ordinal recursive functions.
Archiv für Mathematische Logik und Grundlagenforschung,
13:136153, 1970.
 61

Xiaokang Yu and Stephen G. Simpson.
Measure theory and weak König's lemma.
Archive for Mathematical Logic, 30:171180, 1990.
Mass Problems and Randomness
This document was generated using the
LaTeX2HTML translator Version 200221 (1.71)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html split 0 massrand
The translation was initiated by Stephen G Simpson on 20070928
Stephen G Simpson
20070928