|
|
|
|
|
|
just in case g is a prefix of c A. Clearly,  is a partial order on STR. We identify the elements of STR with those of N.1 |
|
|
|
|
|
|
|
|
11.4 Definition (Jockusch [101]) A is 1-generic just in case, for every r.e. set L, there is an n such that either (a)  , or (b) for all  ,  . |
|
|
|
|
|
|
|
|
Jockusch [101] shows that 1-generic sets exist and are, in a reasonable sense, plentiful. Here then is the promised characterization of trivial sets. |
|
|
|
|
|
|
|
|
11.5 Proposition For all A, OAEx = Ex if and only if  and A is Turing reducible to a 1-generic set. |
|
|
|
|
|
|
|
|
The if direction of the proposition is due to Fortnow, Gasarch, Jain, Kinber, Kummer, Kurtz, Pleszkoch, Slaman, Solovay, and Stephan [59], and the only if direction is due to Slaman and Solovay [177]. Slaman and Solovay's [177] proof of the only if direction is quite difficult. Kummer and Stephan [114] have an easier proof of this direction. Here we show Proposition 11.6 below, a weak version of the if direction. The full argument of the if direction is left to Exercise 11-4. |
|
|
|
|
|
|
|
|
11.6 Proposition Suppose A is a 1-generic set that is  K. Then OAEx = Ex. The following two lemmas imply the proposition. |
|
|
|
|
|
|
|
|
11.7 Lemma Suppose A is 1-generic and  . Then there is an M such that, for each  , MA Ex-identifies f, making only finitely many queries to A. |
|
|
|
|
|
|
|
|
11.8 Lemma Suppose  and  and M are such that, for each  , MA Ex-identifies f, making only finitely many queries to A. Then  . |
|
|
|
|
|
|
|
|
We prove Lemma 11.7 below. The proof of Lemma 11.8 is left to Exercise 11-3. Before proving Lemma 11.7, we introduce one more bit of notation. For each oracle scientist M,  , and  , we define |
|
|
|
 |
|
|
|
|
1Via the isomorphism  Exercise: Show that this really is an isomorphism. |
|
|
|
|
