FOM: Thickness Lemma

[Joseph Shoenfield]

     In a recent communication, Friedman has mildly criticized my
use of the term "priority theory".   His point seems to be that
theories are generally named after the object studied rather than
the method used; so I should have talked about "RE degree theory".
He has a point, but I think there are special reasons for speaking
of priority theory.   In most of the early papers on RE degree
theory, the priority methods used were of more interest that the
results proved.   RE degree theory was often criticized because of
this; but all turned out well, since the methods developed were
eventually used to prove more interesting results.   In my communi-
cation, I cited several problems about the use of priority which
are amenable to a mathematical solution; it seems reasonable to
call these problems in priority theory.
     One problem which I suggested was to find general theorems,
such as the Thickness Lemma, which enable us to prove results about
RE degrees without further use of priority.   In the rest of this
commuication, I would like to show how the Thickness Lemma could
have been proved by someone investigating priority theory.
     The priority method is a method for constructing an RE set A.
We divide the conditions we want A to satisfy into an infinte se-
quence of smaller conditions.   At step s in the construction of A,
we treat these conditions in order.   In treating condition n, we
put a finite number of numbers into A (positive action) and select
a finite set of numbers which we wish to keep out of A (negative
action).   These wishes must be respected in the remainder of step
s.   However, at a later step, condition m for m<n may violate these
wishes; we say condition m injures condition n.   Then condition n
must start its work again.  This is OK, provided that condition n is
only injured finitely many times.   Since there are only finitely
many m<n, it is enough to insure that the positive action of condi-
tion m only puts finitely many numbers into A.   Another problem which
could arise for condition n is that at each s, a condition m<n keeps
out of A one of the numbers n wishes to put in.   To avoid this, we
also require that the negative action of m only keep finitely many
numbers out of A.
     It is easy to imagine problems in which condition n wants to put
an infinite set B of numbers into A.   Since condition n may be in-
jured finitely often, we can only hope to put a subset C of B into A
where B-C is finite.   Even for this, there is no hope without a
restriction on B.   For example, if B is (Turing) complete, then C
and hence A will be Turing complete; so A is useless for RE degree
theory.   This may suggest taking B to be recursive; then C
is recursive and thus has no effect by itself on the degree of A.
     The first problem is that a condition may now be injured infi-
nitely often.   Each time condition n is injured, it starts again and
produces new negative action.   Thus condition n may have infinite
negative action, which as we saw may injure (in another way) a higher
condition.
     All of this can be overcome, provided each B is recursive and the
necessary negative action is of a certain kind.    For example, if D
is an RE non-recursive set, Sacks discovered a negative action to in-
sure that D is not recursive in the A constructed by a finite injury
construction; this can be used here.
     Now let us state the result.   A set A of numbers gives rise to
a sequence of sets by letting An be the set of x such that P(n,x) is
in A (where P is a fixed recursive pairing function).   We say B is
piecewise recursive if each Bn is recursive.   We say a subset C of B
is thick if Bn-Cn is finite for each n.
     Thickness Lemma: If B is RE and row-recursive and D is RE and
not recursive, then there is a thick RE subset C of B such that D
is not recursive in C.
     The Thickness Lemma has many consequences in RE degree theory.
For example, it implies that there is a high, non-complete RE set
(a result first proved by Sacks by an infinite injury priority
argument). For this, we need to find an RE, row-recursive B such that
every thick RE subset of B is high.    This is fairly easy and re-
quires no use of priority.   Slightly stronger forms of the Thickness
Lemma (proved by the same method) lead (with some additional effort
but no use of priority) to the Yates index set theoem, which,
in conjunction with the Recursion Theorem, implies the Sacks density
theorem.   (For all this, see my book on degrees or Soare's book on
RE sets.)   I hope the above gives some feeling of why the Thickness
Lemma can do so much of the work of priority.
     I have used the above ideas to obtain a type of RE set which, in
some sense, is the most general sort of RE set obtainable by a finite
injury construction.   I hope to write you soon about this.