[FOM] natural r.e. degrees
Stephen G Simpson
simpson at math.psu.edu
Sun Feb 27 22:32:34 EST 2005
NATURAL R.E. DEGREES
Stephen G. Simpson
February 27, 2005
INTRODUCTION
Several of the FOM editors have urged me to post on the topic of
natural r.e. degrees. (Note that "r.e." is a standard abbreviation for
recursively enumerable, and "degrees" is short for degrees of
unsolvability.)
At the request of the FOM editors, I shall stay as far as possible
away from the history of this topic, and concentrate solely on the
scientific issues.
The current situation as regards natural r.e. degrees may be
summarized as follows:
NNE (No Natural Examples):
Despite more than 50 years of intensive investigation of the
r.e. degrees of unsolvability, nobody has yet discovered a
specific, natural example of an r.e. degree other than the two
examples originally noted by Turing: 0 = the degree of solvable
decision problems, and 0' = the degree of the Halting Problem.
This is in contrast to most other branches of mathematics, which
are motivated and nurtured by a rich stock of specific, natural
examples.
This suggests the following problem in mathematical logic:
NEP (Natural Examples Problem):
To discover and exhibit at least one specific, natural example of
an r.e. degree other than 0 and 0'.
To set the stage for our discussion of NNE and NEP, it must be noted
that many researchers, including many experts on r.e. degrees, regard
NNE as an indisputably true description of the current situation.
However, for reasons which I shall not discuss here, at least one
r.e. degree expert, whom I shall not name here, has chosen to dispute
NNE, even though NNE is indisputable. (The curious reader may search
for "canard" in the FOM archive.) Furthermore, over a number of
years, this dispute over NNE has caused a great deal of
misunderstanding and confusion in the mathematical logic community.
In a recent attempt to dispell this scientific confusion, I have
written two research papers: "Mass Problems and Randomness" (27 pages,
to appear in the Bulletin of Symbolic Logic), and "An Extension of the
Recursively Enumerable Turing Degrees" (15 pages, submitted for
publication). These papers are available on my web page at
http://www.math.psu.edu/simpson/papers/.
In my two papers referenced above, I place the dispute over NNE into a
slightly wider mathematical context, aimed at highlighting and
bringing into clearer focus the (already indisputable) truth of NNE,
as well as the nature and urgency of the NEP problem.
My purpose here on FOM is to present a condensed summary of the
principal findings in my two papers referenced above.
PRINCIPAL FINDINGS
First, let R_T be the set of r.e. Turing degrees, i.e., the degrees of
unsolvability of r.e. sets of natural numbers. Recall that R_T is a
partial ordering and an upper semilattice with bottom element 0 and
top element 0'.
The upshot of more than 50 years of intensive investigation of R_T is
that R_T, viewed as a semilattice, is infinite and structurally rich.
[ For example, the Sacks Splitting Theorem says that every non-zero
degree in R_T is the least upper bound of two other degrees in R_T.
The Sacks Density Theorem says that for every a < b in R_T there
exists c in R_T such that a < c < b. ]
On the other hand, as asserted in NNE, no specific, natural degrees
other than 0 and 0' in R_T are presently known. NEP is the problem of
finding such a degree.
In order to bring NNE and NEP into sharper focus, I embed R_T into a
slightly larger degree structure, called P_w. Briefly, P_w is the
lattice of weak degrees of mass problems associated with nonempty,
effectively closed sets in the Cantor space. For a more leisurely
definition of P_w, see the Appendix below.
My findings concerning the relationship between R_T and P_w are as
follows.
1. There is a natural embedding I: R_T --> P_w of the semilattice R_T
into the lattice P_w. (For the definition of I, see the Appendix
below.)
2. The embedding I: R_T --> P_w is one-to-one and respects and
preserves key algebraic properties of R_T, namely, the bottom and
top elements, the partial ordering, and the semilattice operation.
3. The embedding I: R_T --> P_w respects and preserves key structural
and methodological properties of R_T.
[ For example, Stephen Binns (Ph.D. thesis, Penn State, 2003) has
shown that every non-zero degree in P_w is the least upper bound
of two other degrees in P_w. Thus the Binns Splitting Theorem for
P_w is obviously analogous to the Sacks Splitting Theorem for R_T.
Moreover, the proof of the Binns Splitting Theorem -- by means of
a priority argument -- is similar to the proof of the Sacks
Splitting theorem. In addition, I conjecture that the P_w analog
of the Sacks Density Theorem holds, and by a similar proof. ]
I summarize findings 1, 2, and 3 by saying that the lattice P_w is an
extension of the semilattice R_T which is in many respects close to
and similar to R_T.
4. I have exhibited a host of specific, natural degrees in P_w.
These specific, natural degrees in P_w have names such as 0, 1,
r_1, r^*_2, d, d_REC, d_POLY, d_EXP, d_ER, d_PR, ..., d^2, d^3,
....
These specific, natural degrees in P_w are ordered as follows:
1 > r^*_2 > r_1 > d > 0 ,
r_1 > d_POLY > d_EXP > d_ER > d_PR > ... > d_REC > d > 0 ,
r_1 > ... > d^3 > d^2 > d > 0 .
I conjecture that each of the specific, natural degrees d^2, d^3,
... is incomparable with each of the specific, natural degrees
d_POLY, ..., d_REC.
For the definitions of these specific, natural degrees in P_w, see
the Appendix below.
5. I have shown that these specific, natural degrees in P_w are
closely related to interesting topics in the foundations of
mathematics. The topics are:
a. algorithmic randomness.
b. reverse mathematics.
c. subrecursive hierarchies.
d. computational complexity.
6. My discovery of a host of specific, natural, interesting degrees
in P_w is in striking contrast to the situation in R_T, where no
specific, natural degrees other than 0 and 0' are known.
In particular, all of the specific, natural degrees in P_w
mentioned above are incomparable with all of the degrees in the
image of R_T under the natural embedding I: R_T --> P_w. The
only exceptions to this are 0 = I(0), and 1 = I(0').
In my opinion, findings 1 - 6 above provide an elegant, compelling
demonstration of the sense in which the lack of specific, natural
examples of r.e. degrees (NNE) and the problem of finding such
examples (NEP) are or should be pressing issues for the mathematical
logic community. Namely, I have done this by showing people what
specific, natural degrees look like in a degree structure, P_w, which
is slightly larger than and closely related to the r.e. degrees, R_T.
ANSWERS TO SOME OBJECTIONS
Naturally, my findings and their significance will be disputed.
A. One logician dismisses my findings 1 - 6 as irrelevant to the NEP
problem, because the specific, natural degrees which I have
discovered do not belong to R_T.
I regard this objection as itself irrelevant. Of course I admit
that my findings do not provide a definitive *answer* to NEP, nor
do they suggest how to find an answer. However, I maintain that
that my findings are nevertheless *relevant* to NNE and NEP, in the
way described above, and in at least one other way which I shall
not discuss here.
Speaking generally, it is possible for some new knowledge to be
*relevant* to a problem, even if it does not provide or suggest the
*answer* to the problem. That is the case here.
B. Another logician objects to NNE itself, on the grounds that such a
statement requires a rigorous mathematical definition of the word
"natural" as it applies to r.e. degrees. So long as no such
definition exists, it is proposed to dismiss statements such as NNE
as meaningless, unimportant, unenlightening, unproductive,
contentious, etc.
I find this stance unreasonable, because it is well known that
non-rigorous considerations of naturalness have always played a key
role in almost all high-quality mathematical research, even in the
absence of rigorous definitions of "naturalness". Without
considerations of naturalness, it would be difficult or impossible
to pursue the ideal of "exquisite taste" in mathematical research,
as famously enunciated by von Neumann.
C. A more interesting objection to my findings has been raised in a
series of private conversations, by an expert on r.e. degrees (not
the same expert who was mentioned in the Introduction above).
In non-technical terms, the thrust of this expert's objection is
that NNE is true but does not matter, because specific, natural
examples are not needed in order to have a rich theory. I of
course disagree. It seems clear to me that, without examples,
mathematical research topics tend to lose their vitality and fade
into obscurity. There are signs that this is already happening to
the r.e. degrees.
Actually, I find it remarkable that the r.e. degrees have survived
for so many years and engaged such an able group of researchers,
despite the lack of examples. This certainly sets r.e. degrees
apart from virtually all other highly developed branches of
mathematics.
Unfortunately, the expert just mentioned above is unlikely to post
on FOM or to address these issues in print. Thus, the full
statement of his viewpoint may never see the light of day. That
would be unfortunate, because a thorough discussion of his
viewpoint would get us into a number of interesting technical
issues. These issues concern relativization, a conjecture of
Donald A. Martin, classes of r.e. degrees, and the nature of mass
problems.
In any case, I would be glad for the chance to discuss these issues
further, with experts or non-experts, on FOM or privately.
APPENDIX: MASS PROBLEMS AND P_w
In this appendix I define the degree structure P_w, state some of its
properties, define the embedding I: R_T --> P_w, and define some
specific, natural degrees in P_w.
1. MASS PROBLEMS AND THEIR WEAK DEGREES
Let N^N be the BAIRE SPACE, i.e., the set of all 1-place total
functions f: N --> N from the natural numbers to the natural numbers.
Informally, we identify a subset P of N^N with the "problem" of
finding an element of P. A "solution" of this problem is an element
of P. Problems of this kind are called "MASS PROBLEMS". Thus a mass
problem is a "generalized decision problem", which may have more than
one solution. Conversely, a decision problem is a special kind of
mass problem, which has exactly one solution, i.e., P is a singleton
set. In general, a mass problem may have no solutions, one solution,
or more than one solution. A mass problem is said to be "SOLVABLE" if
it has at least one solution which is computable. A mass problem
which is not solvable is said to be "UNSOLVABLE".
Example:
Let PA = { f in N^N | f is the characteristic function of the set of
G"odel numbers of theorems of some complete, consistent theory in
the language of Peano Arithmetic which includes all the axioms of
Peano Arithmetic }. Then PA may be viewed as a mass problem,
namely, the problem of finding a complete, consistent theory
extending Peano Arithmetic. According to a familiar theorem of
Tarski/Mostowski/Robinson, Peano Arithmetic is "essentially
undecidable", i.e., PA has no computable element. In other words,
viewed as a mass problem, PA is unsolvable.
Formally, let P and Q be subsets of N^N. We say that P is WEAKLY
REDUCIBLE to Q if, given any g in Q, we can use g as a Turing oracle
to compute some f in P. (Informally this means that, given any
"solution" of the mass problem Q, we can use it to compute a
"solution" of the mass problem P.)
The WEAK DEGREES are the equivalence classes of subsets of N^N under
the equivalence relation of mutual weak reducibility. The set of all
weak degrees is partially ordered according to weak reducibility.
Thus, the weak degree of P is less than or equal to the weak degree of
Q if and only if P is weakly reducible to Q.
The weak degree of solvable mass problems is denoted 0. Thus, P is of
weak degree 0 if and only if there exists f in P such that f is Turing
computable, i.e., f is recursive.
The partial ordering of all weak degrees is denoted D_w. It is
straightforward to show that D_w is a complete distributive lattice,
and that 0 is the least element of D_w.
Let D_T be the upper semilattice of all Turing degrees, i.e., degrees
of unsolvability. It is straightforward to show that D_T is naturally
embeddable in D_w. Namely, the Turing degree of f in N^N is
identified with the weak degree of {f}, the singleton set whose only
element is f.
2. THE LATTICE P_w
It is common to regard the set R_T of r.e. Turing degrees as the
smallest or simplest natural, nontrivial substructure of D_T. We wish
to introduce an analogous set of weak degrees, P_w. Our guiding
analogy is:
P_w / D_w = R_T / D_T .
We shall now define P_w.
Let P be a subset of N^N. P is said to be PI^0_1 if, for some
recursive predicate R,
P = { f in N^N | (for all n) R(f,n) } .
Here n ranges over N, the set of natural numbers. Note that a PI^0_1
subset of N^N is sometimes called an EFFECTIVELY CLOSED set, because
it is just the complement within the Baire space N^N of of an
EFFECTIVELY OPEN set, i.e., the union of a recursive sequence of basic
open sets in N^N.
A subset P of N^N is said to be RECURSIVELY BOUNDED if there exists a
recursive function g in N^N such that f(n) < g(n) for all f in P and
all n in N. Recursively bounded PI^0_1 subsets of N^N are sometimes
called EFFECTIVELY COMPACT.
We define P_w to be the set of weak degrees of nonempty, recursively
bounded, PI^0_1 subsets of N^N.
Remark:
It can be shown that every recursively bounded PI^0_1 subset of N^N
is recursively homeomorphic to, hence weakly equivalent to, a
recursively bounded PI^0_1 set of a special kind, namely a PI^0_1
subset of the CANTOR SPACE, {0,1}^N. (Here the recursive bounding
function g is the constant function 2, i.e., g(n) = 2 for all n in
N.)
Thus P_w may be alternatively defined as the set of weak degrees of
nonempty PI^0_1 subsets of {0,1}^N.
It is straightforward to show that P_w is a countable distributive
sublattice of D_w, and that P_w has the same bottom element as D_w,
namely 0, the weak degree of solvable mass problems. This is
analogous to the fact that R_T is a countable subsemilattice of D_T
with the same bottom element as D_T.
It can be shown that P_w has a top element, denoted 1. It turns out
that 1 is the weak degree of PA, the set of completions of Peano
Arithmetic, as in the Example above. See also the discussion of 1
below, in the section on specific, natural degrees in P_w.
3. THE EMBEDDING I: R_T --> P_w
The embedding I: R_T --> P_w is defined as follows. Given d in R_T,
i(d) is defined to be the weak degree of the union of d and PA. Here
PA is the set of completions of Peano Arithmetic, as above.
[ It is not obvious that i(d) as just defined belongs to P_w.
However, this can be shown as a consequence of a key lemma in my paper
"An Extension of the Recursively Enumerable Turing Degrees". ]
[ It is not obvious that the embedding I: R_T --> P_w is one-to-one.
However, this can be shown as a consequence of a theorem known as the
Arslanov Completeness Criterion. ]
It is straightforward to verify the following facts:
I(0) = 0 .
I(0') = 1 .
I preserves the partial ordering and the semilattice or least upper
bound operation from R_T. Namely,
I(a v b) = I(a) v I(b) ,
and
a < b implies I(a) < I(b) .
4. SOME SPECIFIC, NATURAL DEGREES IN P_w
Some specific, natural degrees in P_w are:
0 = the weak degree of {0,1}^N
= the weak degree of solvable mass problems.
1 = the weak degree of PA, the set of completions of Peano
Arithmetic
= the weak degree of the set of separating functions for an
effectively inseparable pair of r.e. sets.
[ It can be shown that 1 is the top degree in P_w. We could
replace Peano Arithmetic by any recursively axiomatizable theory
which exhibits the G"odel/Rosser effective incompleteness
property. ]
r_1 = the weak degree of the set of infinite sequences of 0's and
1's which are random in the sense of Martin-L"of.
r^*_2 = inf (r_2, 1), where r_2 is the weak degree of the set of
infinite sequences of 0's and 1's which are random (in the
sense of Martin-L"of) relative to the Halting Problem.
d = the weak degree of the set of diagonally non-recursive functions
= the weak degree of the set of effectively immune sets.
d_REC = the weak degree of the set of recursively bounded,
diagonally non-recursive functions.
d_POLY = the weak degree of the set of polynomially bounded,
diagonally non-recursive functions.
d_EXP = the weak degree of the set of exponentially bounded,
diagonally non-recursive functions.
d_ER = the weak degree of the set of elementarily recursively
bounded, diagonally non-recursive functions.
d_PR = the weak degree of the set of primitively recursively
bounded, diagonally non-recursive functions.
...
d^2 = the weak degree of the set of pairs (f,g) such that f is
diagonally non-recursive, and g is diagonally non-recursive
relative to f.
d^3 = the weak degree of the set of triples (f,g,h) such that f is
diagonally non-recursive, g is diagonally non-recursive
relative to f, and h is diagonally non-recursive relative to
(f,g).
...
[ It is not obvious that all of these weak degrees belong to P_w.
However, this can be shown as a consequence of a key lemma in my paper
"An Extension of the Recursively Enumerable Turing Degrees". ]
THE END
More information about the FOM
mailing list