advertisement

CUPPING AND DEFINABILITY IN THE LOCAL STRUCTURE OF THE ENUMERATION DEGREES HRISTO GANCHEV AND MARIYA I. SOSKOVA Abstract. We show that every splitting of 00e in the local structure of the enumeration degrees, Ge , contains at least one low-cuppable member. We apply this new structural property to show that the classes of all K-pairs in Ge , all downwards properly Σ02 enumeration degrees and all upwards properly Σ02 enumeration degrees are first order definable in Ge . 1. Introduction Enumeration reducibility introduced by Friedberg and Rogers [11] arises as a way to compare the computational strength of the positive information contained in sets of natural numbers. A set A is enumeration reducible to a set B if given any enumeration of the set B, one can effectively compute an enumeration of the set A. The induced structure of the enumeration degrees De is an upper semilattice with least element and jump operation. This structure can be viewed as an extension of the structure of the Turing degrees, as there is an embedding ι : DT ⇒ De which preserves the order, the least upper bound and the jump operation. The jump operation gives rise to a local substructure, Ge , consisting of all degrees in the interval enclosed by the least degree and its first jump. The elements of the local structure of the enumeration degrees can be characterized in terms of their relationship to the arithmetical hierarchy. Cooper [4] shows that the elements of Ge are precisely the enumeration degrees which contain Σ02 sets, or equivalently are made up entirely of Σ02 sets, which we call Σ02 degrees. Naturally the arithmetical hierarchy gives rise to a substructure of Ge , the substructure of the ∆02 enumeration degrees, the enumeration degrees which contain ∆02 sets. This is a proper substructure of Ge , as there are properly Σ02 enumeration degrees, degrees which do not contain any ∆02 set. Another way to partition the elements of Ge is in terms of the jump hierarchy. We distinguish between low and non-low enumeration degrees, where a degree is low if its enumeration jump is as low as possible, namely 00e . In terms of their relationship with the Turing degrees the elements of Ge can be divided into total enumeration degrees, ones that are images of Turing degrees under the embedding ι, or non-total degrees, ones that are not. Each of these subclasses of Ge is defined by singling out a property of the sets that comprise an element in the class. For example McEvoy [18] proves that an enumeration degree is low if and only if all of its members are ∆02 . An enumeration degree is total if and only if it contains a set of the form A ⊕ A. One of the goals in the study of the local structure of the enumeration degrees is to find a This research was supported by an BNSF Grant No. D002-258/18.12.08 and by a Marie Curie European Reintegration Grant No. 239193 within the 7th European Community Framework Programme. 1 2 H. GANCHEV AND M. SOSKOVA relationship between the natural information content of the sets in a Σ02 degree and its definability in Ge . In this article we give the first example of such a relationship, we prove the local definability of the enumeration degrees of sets that form a K-pair. Definition 1.1. [Kalimullin] A pair of sets of natural numbers A and B is a K-pair if there is a c.e. set W such that: A × B ⊆ W & A × B ⊆ W. The notion of a K-pair is a special case of a U -e-ideal, introduced and used by Kalimullin to prove the definability of the jump operation in the global structure De . In [16] Kalimullin proves that the property of being a K-pair is degree theoretic and first order definable in the global structure De . A pair of sets form a K-pair if and only if their degrees a = de (A) and b = de (B) satisfy the property: K(a, b) ∀x[(a ∨ x) ∧ (b ∨ x) = x]. We will call a pair of enumeration degrees a K-pair if they contain representatives which form a K-pair in the sense of Definition 1.1. K-pairs have been proven useful for coding structures in Ge , some of their main advantages lying in their properties: e.g. every K-pair of nonzero degrees in Ge is a minimal pair of low enumeration degrees. It has been shown in [12] for instance, that using countable K-systems, systems of nonzero e-degrees such that every pair of distinct degrees forms a K-pair, that every countable distributive semi-lattice can be embedded below every nonzero ∆02 e-degree. The local definability of K-pairs is the first step in a larger project [14], aimed at showing that the theory of Ge is computably isomorphic to first order arithmetic, where K-systems are used to code standard models of arithmetic in Ge . Kalimullin [16] has shown that if a pair of sets A and B do not form a K-pair then there is a set C, computable from A ⊕ B ⊕ K, where K denotes the halting set, such that the degree de (C) witnesses the fact that de (A) and de (B) do not satisfy the formula K. Hence if A and B are ∆02 enumeration degrees then C is also ∆02 and the property ”a and b form a K-pair” is first order definable in the substructure of the ∆02 enumeration degrees by the same formula, K. If A and B are properly Σ02 then the witness C is at best estimated as ∆03 , hence it is quite possible that there are fake pairs (a, b) of Σ02 enumeration degrees, such that: Ge |= K(a, b), but De |= ¬K(a, b). The key to the definability of K-pairs lies in the cupping properties of Ge . We say that a Σ02 enumeration degree u is cuppable if there exists an incomplete v < 00e such that u ∨ v = 00e . Cooper, Sorbi and Yi [9] prove that not every nonzero Σ02 enumeration degree is cuppable, in contrast to the ∆02 enumeration degrees, where for every nonzero degree one can find a total ∆02 cupping partner. Soskova and Wu [21] prove furthermore that every nonzero ∆02 enumeration degree is low-cuppable, i.e. cuppable by a low enumeration degree. In [13] a stronger version of Soskova and Wu’s theorem is proved, which also reveals certain cupping properties of K-pairs: Theorem 1.1. [13] For every nonzero ∆02 degree a there is a K-pair, {b, c} of nonzero ∆02 degrees, such that a ∨ b = b ∨ c = 00e . The final ingredient for the definability of K-pairs in Ge is provided by the following new cupping property of the elements in Ge , which we believe is of independent interest. CUPPING AND DEFINABILITY 3 Theorem 1.2. For every pair of Σ02 enumeration degrees u and v with u ∨ v = 00e , there exists a low ∆02 enumeration degree a < 00e , such that at least one of the following is true: (1) u ∨ a = 00e , (2) v ∨ a = 00e . This property reveals that the class of low-cuppable Σ02 enumeration degrees contains at least half of the cuppable enumeration degrees. Whether or not there are cuppable Σ02 degrees, which are not low-cuppable remains open. Using Theorem 1.2 we show how one can give a local definition of a nonempty set of K-pairs. Applying Theorem 1.1 we prove that every member of a K-pair is bounded by some element from this set. Thus as an application of these two structural properties of Ge we obtain the desired definability result: Theorem 1.3. There is a first order formula LK in the language of Ge such that a pair of nonzero Σ02 enumeration degrees a and b form a K-pair if and only if: Ge |= LK(a, b). The definability of K-pairs allows us to give a first order definition of two further classes that have been of interest in the study of the local structure. A nonzero degree a ∈ Ge is downwards properly Σ02 if all nonzero degrees b ≤ a are properly Σ02 . For example every non-cuppable Σ02 degree is necessarily downwards properly Σ02 as every ∆02 enumeration degree is cuppable. Another example is given by Cooper, Li, Sorbi and Yang [8], who show that there is a Σ02 degree which does not bound a minimal pair, whereas every ∆02 degree does. The symmetric class of the upwards properly Σ02 enumeration degrees contains the incomplete enumeration degrees a ∈ Ge such that all incomplete degrees b ≥ a are properly Σ02 . Soskova [20] proves that there is an enumeration degree a < 00e , such that no pair of incomplete degrees above it forms a splitting of 00e . This, combined with Arslanov and Sorbi’s [2] result, that there is a splitting of 00e above every incomplete ∆02 enumeration degree, gives an example of an upwards properly Σ02 degree. Bereznyuk, Coles and Sorbi [3], prove that there is an upwards properly Σ02 degree above any incomplete member of Ge . Cooper and Copestake [7] show furthermore that there are properly Σ02 enumeration degrees that are incomparable with every nonzero, incomplete ∆02 degree, and hence are both upwards and downwards properly Σ02 . We show that these two classes are also first order definable in the local structure. Theorem 1.4. The following two classes of Σ02 enumeration degrees are first order definable in Ge : (1) The class of downwards properly Σ02 enumeration degrees; (2) The class of upwards properly Σ02 enumeration degrees. The revealed relationship between definability and information content in the Σ02 enumeration degrees calls forth the search for other examples of this phenomenon. In view of the nature of the particular classes that are proved definable in this article, an important question that remains open is: Question 1.4.1. Is the class of the ∆02 or the class of the total enumeration degrees enumeration first order definable in Ge ? 4 H. GANCHEV AND M. SOSKOVA 2. Preliminaries We assume that the reader is familiar with the notion of enumeration reducibility, and refer to Cooper [5] for a survey of basic results on the structure of the enumeration degrees and to Sorbi [19] for a survey of basic results on the local structure Ge . For completeness we will nevertheless outline here basic definitions and properties of the enumeration degrees used in this article. Definition 2.1. A set A is enumeration reducible (≤e ) to a set B if there is a c.e. set Φ such that: A = Φ(B) = {n | ∃u(hn, ui ∈ Φ & Du ⊆ B)}, where Du denotes the finite set with code u under the standard coding of finite sets. We will refer to the c.e. set Φ as an enumeration operator and its elements will be called axioms. A set A is enumeration equivalent (≡e ) to a set B if A ≤e B and B ≤e A. The equivalence class of A under the relation ≡e is the enumeration degree de (A) of A. The structure of the enumeration degrees hDe , ≤i is the class of all enumeration degrees with relation ≤ defined by de (A) ≤ de (B) if and only if A ≤e B. It has a least element 0e = de (∅), the set of all c.e. sets. We can define a least upper bound operation, by setting de (A) ∨ de (B) = de (A ⊕ B) and a jump operator de (A)0 = de (Je (A)). The enumeration jump of a set A, denoted by Je (A) is defined by Cooper [4] as LA ⊕ LA , where LA = { n| n ∈ Φn (A)}. Enumeration degrees which contain a set of the form A ⊕ A are called total enumeration degrees. The interest in the class of the total enumeration degrees, arises from the fact that it is an isomorphic copy of the Turing degrees. The map ι, which sends a Turing degree dT (A) to the e-degree de (A ⊕ A), is an embedding, which preserves the order, the least upper bound and the jump operation. We shall say that an e-degree is quasi-minimal if and only if it bounds no total degree, except for the least e-degree 0e . Finally we introduce one further piece of notation. In what follows we will often need to work with a set C reducible to the least upper bound of two other sets, say A and B. To keep notation simple we will consider the set C as being enumerated relative to two sources and write C = Φ(A, B), instead of C = Φ(A ⊕ B). Naturally we will assume that an axiom of the operator Φ has the structure hn, DA , DB i and that it is valid if an only if DA ⊆ A and DB ⊆ B. Further notation and terminology used in this article are based on that of [6]. 3. A local definition of K-pairs K-pairs can be viewed as a generalization of the notion of a semi-recursive set, defined by Jockusch [15]. Recall that a set A is semi-recursive if it has a computable selector function sA : N × N such that for all natural numbers n and m: sA (n, m) ∈ {n, m} and if {n, m} ∩ A 6= ∅ then sA (n, m) ∈ A. It is not difficult to see that if A is semi-recursive then A and A form a K-pair. Indeed let sA be the selector function for A and let ( n , if sA (n, m) = m sA (n, m) = m , if sA (n, m) = n. Now consider the c.e. set W = {(sA (n, m), sA (n, m)) | n, m ∈ N} and notice that A × A ⊆ W and A × A = A × A ⊆ W . CUPPING AND DEFINABILITY 5 Another simple example of a K-pair is {W, A}, where A is any set of natural numbers and W is a c.e. set. This we shall consider as a trivial example and we will mainly be interested in nontrivial K-pairs, ones consisting of two non-c.e sets. We shall say that a degree a is half of a K-pair if there is a nonzero degree b such that {a, b} forms a K-pair of degrees. The degree b will be called a K-partner for a. Some basic properties of K-pairs of degrees, collected from Kalimullin [16], are summarized in the following theorem. Theorem 3.1 (Kallimullin). Let K(a, b) denote the formula with free variables a and b, defined by: ∀x[(a ∨ x) ∧ (b ∨ x) = x]. (1) A pair of degrees a and b form a K-pair if and only if De |= K(a, b). (2) A pair of ∆02 degrees a and b form a K-pair if and only if Ge |= K(a, b). (3) Every half of a nontrivial K-pair in Ge is quasi-minimal and low. (4) The set of degrees which form a K-pair with a fixed degree de (A) is an ideal with upper bound de (A). (5) If a and b form a nontrivial K-pair then a and b form a minimal pair, i.e. the only degree that is both below a and b is 0e . (6) Every nonzero ∆02 enumeration degree bounds a nontrivial K-pair. We add one additional property to the list, which motivates our interest in the cupping properties of the elements in Ge . Lemma 3.1. Let a and b be Σ02 enumeration degrees such that: If c is a Σ02 Ge |= K(a, b). enumeration degree, such that b ∨ c = 00e , then a ≤ c. Proof. By the property K(a, b) applied to c we get: (b ∨ c) ∧ (a ∨ c) = c. Replacing (b ∨ c) with its equal 00e we get: 00e ∧ (a ∨ c) = c. Now as 00e is the largest element of Ge we get: a ∨ c = c or equivallently a ≤ c. Jockusch [15] shows that for every set B there is a semi-recursive set A ≡T B such that A and A are non-c.e. This, combined with the quasi-minimality of Kpairs, proves that every total member of Ge can be represented as the least upper bound of the elements of a nontrivial K-pair. In particular 00e can be split by a nontrivial K-pair of ∆02 enumeration degrees. We are now ready to give a first order definition of K-pairs assuming Theorems 1.1 and 1.2. Consider the formula L(a) a > 0e & ∃b > 0e (a ∨ b = 00e & K(a, b)). From the argument above it follows that there are elements of Ge which satisfy this formula. We show that every element which satisfies this formula is in fact a half of a K-pair. 6 H. GANCHEV AND M. SOSKOVA Propostion 3.1. If Ge |= L(a) then a is half of a nontrivial K-pair. Proof. Let b > 0e be a degree such that a ∨ b = 00e & K(a, b). Then {a, b} is a splitting of 00e and hence applying Theorem 1.2 we get a low ∆02 degree c which cups a or b. Case 1: b ∨ c = 00e . By Lemma 3.1 we get a ≤ c. Now by the monotonicity of the enumeration jump it follows that a is low, hence ∆02 , and by the property that all nonzero ∆02 are low-cuppable, a is as well low-cuppable. Case 2: a ∨ c = 00e . Then similarly b ≤ c and hence ∆02 and low-cuppable. Therefore if one of the degrees a and b is low-cuppable, then both are lowcuppable and both are ∆02 . Now applying part 2 of Theorem 3.1 we get that a and b form a K-pair. The set defined by the formula L is therefore a nonempty set of low enumeration degrees. It does not contain all halves of nontrivial K-pairs. Let c be any total incomplete ∆02 enumeration degree and let A be a semi-recursive set, such that de (A ⊕ A) = c and both A and A are not c.e. It follows from Theorem 3.1 that a = de (A) is half of a nontrivial K-pair and de (A) = a is the largest element of the ideal of K-partners for a. Hence for every K-partner b of a, a ∨ b ≤ a ∨ a = c < 00e and a does not satisfy L. Nevertheless the set L contains an upper bound to every half of a nontrivial K-pair in Ge . Propostion 3.2. If a ∈ Ge is a half of a nontrivial K-pair then there is a degree c ≥ a such that Ge |= L(c). Proof. Let b be a nonzero K-partner for a. Then b is a ∆02 enumeration degree and hence by Theorem 1.1 there is a nontrivial K-pair {c, d} such that b∨c = d∨c = 00e . Consider the degree c. First of all c satisfies the formula L with d as witness for this. Secondly by Lemma 3.1 a ≤ c. On the other hand, suppose that there is a pair of Σ02 enumeration degrees a and b which satisfy the formula K in Ge but are not a K-pair. It follows by an argument similar to the one in the Proposition 3.1 that both a and b are not low-cuppable and hence are downwards properly Σ02 . As every member of the set defined by L is low and hence bounds only ∆02 enumeration degrees it follows that both a and b are incomparable (and even form a minimal pair) with every element which satisfies L. To finalize the proof of Theorem 1.3 we set LK to be the formula: LK(a, b) K(a, b) & a > 0e & b > 0e & ∃c(c ≥ a & L(c)). Now we can easily prove Theorem 1.4 as well. The last property in Preposition 3.1 shows that every ∆02 enumeration degree bounds a nontrivial K-pair. As every K-pair consists of ∆02 enumeration degrees, it follows that a degree is downwards properly Σ02 if and only it bounds no nontrivial K-pair. Thus a degree a is downwards properly Σ02 if and only if: Ge |= ∀b, c[(b ≤ a & c ≤ a) ⇒ ¬LK(b, c)]. To prove the second part of this theorem, recall that every total enumeration degree can be represented as the least upper bound of the elements of a K-pair. The least upper bound of the elements of every K-pair, on the other hand, is a ∆02 degree. The last ingredient comes from a theorem of Arslanov, Cooper and CUPPING AND DEFINABILITY 7 Kalimullin [1] (Theorem 7), which states that for every ∆02 enumeration degree a < 00e there is a total enumeration degree b such that a ≤ b < 00e . From all this it follows that a degree a is upwards properly Σ02 if and only if no incomplete degree above it can be represented as the least upper bound of the elements of a K-pair, i.e. if: Ge |= ∀c, d(LK(c, d) & a ≤ c ∨ d ⇒ c ∨ d = 00e ). 4. Cupping properties of 00e -splittings We start this section with a very general description of the idea behind the construction for the proof of Theorem 1.2. We then proceed to formalizing this idea, giving more intuition as we progress. 4.1. General idea. The construction is inspired by the non-splitting technique introduced in [20]. There it is shown that there is a Σ02 e-degree a < 00e , such that no pair of Σ02 degrees u, v above a splits 00e . An equivalent way to formulate this is as follows. Theorem 4.1 ([20]). There exists a Σ02 enumeration degree a < 00e , such that for every pair of Σ02 enumeration degrees u and v with u ∨ v = 00e at least one of the following is true u ∨ a = 00e or v ∨ a = 00e In the construction of a non-splitting degree, a set A and an auxiliary set E are constructed to meet the following requirements: (1) For every enumeration operator Ψ: NΨ : E 6= Ψ(A). (2) For all triples of an enumeration operator Θ and Σ02 sets U and V : PΘ,U,V : E = Θ(U, V ) ⇒ (∃Γ, Λ)[K = Γ(U, A) ∨ K = Λ(V, A)] Here K is a Π01 member of 00e . The N -requirements guarantee that de (A) is nonzero. Now if U ⊕ V ≡e K then there is an operator Θ such that Θ(U, V ) = E and hence the requirement PΘ,U,V ensures that de (A) cups at least one of the degrees de (U ) or de (V ) to 00e . Hence one incomplete degree is a cupping partner to at least half of the cuppable enumeration degrees. There is no hope that this particular non-splitting degree can be constructed as a low enumeration degree, as by Arslanov and Sorbi [2] there is a splitting of 00e above every incomplete ∆02 enumeration degree. Our task is however much less demanding. Given a particular pair of degrees which splits 00e we have to show that at least one of them is low-cuppable. Let u and v be two given Σ02 enumeration degrees with least upper bound 00e . Fix two representatives U ∈ u and V ∈ v. Definition 4.1. A set A is 1-generic if for every c.e. set W of finite binary strings there is an initial segment of the characteristic function of A, τ ⊆ A, such that: τ ∈ W ∨ ∀µ ⊇ τ (µ ∈ / W ). 8 H. GANCHEV AND M. SOSKOVA Copestake [10] proves that the degree of every 1-generic ∆02 set is low. As every 1-generic set is non c.e., our main plan is to construct a 1-generic ∆02 set A, such that de (A) cups u to 00e . If this plan fails we turn to a backup plan: construct a 1-generic ∆02 sets B, such that de (B) cups v to 00e . So fix a computable listing of all c.e. sets Wi , viewed as sets of finite binary strings. We need to satisfy one of two groups of requirements: (1) The main requirements. There is a ∆02 set A, which satisfies C and Gi for all i < ω, where: C: Gi : ∃Γ(Γ(U, A) = K); ∃τ ⊆ A(τ ∈ Wi ∨ ∀µ ⊇ τ (µ ∈ / Wi )). (2) The backup requirements. There is a ∆02 set B, which satisfies Cˇ and Ǧi for all i < ω, where: Cˇ : ∃Λ(Λ(V, B) = K) Ǧi : ∃τ ⊆ B(τ ∈ Wi ∨ ∀µ ⊇ τ (µ ∈ / Wi )). Following the non-splitting construction we will again make use of an auxiliary Π01 set E, meant to help us use the fact that U ⊕ V is in the largest possible Σ02 enumeration degree. Even though we are constructing this set, we know that there is an enumeration operator Θ such that Θ(U ⊕ V ) = E. Using the recursion theorem we may assume that we are given this operator in advance. We will use this operator to predict changes in the approximations to the sets U and V : an extraction of an element e from the set E will ultimately lead to an extraction of elements out of the set U ⊕ V . Now we turn to our main strategy: construct a 1-generic ∆02 set A and an operator Γ such that Γ(U ⊕ A) = K. Here K is a fixed Π01 member of 00e . To construct Γ we have a main enumeration strategy which watches the approximation to K and enumerates axioms for elements currently in K using finite subsets of the current approximations to U and A. When an element exits the approximation to K it invalidates perviously enumerated axioms by extracting numbers from A. To meet a main genericity requirement, Gi , we have a corresponding main genericity strategy, which tries to find an initial segment of A, either in the set Wi , or which cannot be extended to an element of Wi . The strategy to construct Γ is in conflict with the strategies to make A 1-generic. Extracting elements from A, in order to rectify the enumeration Γ(U ⊕ A) prevents us from restraining A on certain initial segments. To resolve this conflict we try to provoke an extraction from the set U , using the set E. An extraction from the set U will allow us to rectify Γ without changing the approximation to A. If every genericity strategy after finitely many unsuccessful attempt eventually manages to successfully provoke an extraction from the set U , then it is successful, and ultimately all main requirements will be satisfied. Otherwise there will be a least genericity strategy, which fails infinitely often to provoke an extraction from the set U , as every attempt ends in an extraction from the set V . In this case this particular genericity strategy activates the backup strategy: to construct a second 1-generic ∆02 set B and an operator Λ such that Λ(V ⊕ B) = K. The backup strategies, both enumeration and genericity act in a similar way to their main counterparts. The only difference is that every time a backup genericity strategy tries to provoke a change in V , it times its actions with the main genericity strategy, which is responsible for its activation. This ensures that the attempt is successful for the backup strategy. CUPPING AND DEFINABILITY 9 With this general plan in mind we start to formalize the intuitive description of the strategies. We start by selecting approximations to the given sets U and V . 4.2. Approximations. We will use good approximations to the given sets. The notion of a good approximation to a Σ02 sets is first used by Jockusch [15] and by Cooper [4]( Σ02 approximations with infinitely many thin stages). Later on Lachlan and Shore [17] formalize this notion and prove that every n-c.e.a set has one. We fix a good Σ02 approximation {(U ⊕ V ){s} }s<ω to the set U ⊕ V . A good Σ02 approximation is one, which has the following two properties: G. There are infinitely many good stages s such that (U ⊕ V ){s} ⊆ U ⊕ V . Σ02 . For all n there exists a stage s such that at all stages t > s we have (U ⊕ V ) n ⊆ (U ⊕ V ){s} . Denote by GU ⊕V the set of good stages in the approximation to U ⊕ V . We use the following property of good approximations proved in [17]: for every enumeration operator Θ with standard Σ01 approximation {Θ{s} }s<ω , (4.1) lim s∈GU ⊕V Θ{s} ((U ⊕ V ){s} ) = Θ(U ⊕ V ). Denote Θ{s} ((U ⊕V ){s} ) by Θ(U ⊕V ){s} . As noted above we will be constructing a Π01 approximation to a set E and using the recursion theorem we will assume that we are given in advance an operator Θ such that Θ(U ⊕ V ) = E. Denote by l(Θ(U ⊕ V ), E, s) the maximal number n such that Θ(U ⊕ V ){s} n = E {s} n. Then as the sets Θ(U ⊕ V ) and E are equal: lim s∈GU ⊕V l(Θ(U ⊕ V ), E, s) = ∞. Stages at which l(Θ(U ⊕ V ), E, s) > max{l(Θ(U ⊕ V ), E, t) | t < s} will be called expansionary stages. Thus as Θ(U ⊕ V ) = E, there are infinitely many expansionary stages for the operator Θ. One additional consequence of the equality between the two sets will be used. An element of the set E must eventually be permanently enumerated in the set Θ(U ⊕ V ). Hence it will use some finite amount of positive information from the two sets U and V . We introduce the e-degree version of a use function. Let F be a finite set. The age of this set with respect to the approximation to U ⊕ V measured at stage s is the number: ( s − µ t[∀r ∈ [t, s](F ⊆ (U ⊕ V ){r} )] + 1, if F ⊆ (U ⊕ V ){s} ; a(F, s) = 0 otherwise. In other words the age of a finite set is the number of consecutive stages ending in the current stage s at which the set F is a subset of the approximation to U ⊕ V . For instance the age of the empty set a(∅, s) = s + 1 for all s and if F * U ⊕ V {s} then a(F, s) = 0. Let Ax = he, DU ⊕ DV i ∈ Θ{s} be an axiom for e in Θ. The age of this axiom at stage s is the number a(Ax, s) = a(DU ⊕ DV , s). Thus invalid axioms have age 0 at stage s and valid axioms have age equal to the number of consecutive stages at which they have been valid, ending in the current 10 H. GANCHEV AND M. SOSKOVA stage. Denote by ax(e, s) the finite set, such that he, ax(e, s)i is the oldest axiom for e in Θ at stage s, i.e. of greatest age. (If there are more than one valid axioms of maximal age, choose the one with least code). The use of an element e measured at stage s is the set θ(e, s) = [ i≤e, i∈Θ(U ⊕V ax(i, s), ){s} the collection of the finite sets which form the second half of the oldest valid axioms for all elements that currently appear in the set Θ(U, V ). As Θ(U, V ) = E it follows tat for every e ∈ E there will be a stage s such that at all stages t ≥ s the use of e will remain unchanged, i.e. θ(e, s) = θ(e, t). This will be used in the Honestification module described below. 4.3. The tree of strategies. The construction will be in stages. At every stage s we construct a finite path of length less than or equal to s, δ {s} , through a tree of strategies, defined below, approximating the so called true path - a leftmost infinite path of strategies visited at infinitely many stages. If γ ⊆ δ {s} then we shall say that γ is visited or activated at stage s and s will be called a γ-true stage. Every strategy will have outcomes representing different possible ways in which the corresponding requirement might be satisfied. The outcomes of each strategy are ordered linearly. Denote by O the collection of all outcomes. The tree T can be viewed as a computable function with domain the set of finite strings of outcomes, O<ω , and range the set of strategies. The tree of strategies T contains strategies of four types: the main enumeration strategy, main genericity strategies , backup enumeration strategies and backup genericity strategies. The root of the tree is assigned the main enumeration strategy. We will denote this strategy by α. This strategy initiates the construction of a set A and an operator Γ and is successful if Γ(U ⊕A) = K. The strategy has two outcomes e <L b. Outcome e represents the fact that there are infinitely many expansionary stages. The node αˆb is a leaf in the tree T . The node αˆe is assigned the first main genericity strategy β(0). Outcome b represents the fact that l(Θ(U ⊕ V ), E, s) is bounded. By our choice of Θ this cannot be the true outcome of α. We nevertheless leave this outcome on the tree. The effect of this outcome will be that any other strategy is activated only on expansionary stages. The main genericity strategy β = β(i) tries to ensure that A satisfies the i-th genericity requirement Gi . It has outcomes ∞, h, w and fn for every n arranged as follows: ∞ <L · · · <L fn <L . . . f1 <L f0 <L h <L w. Outcome ∞ represents the fact that β has been unsuccessful infinitely often to secure a witness τ ∈ Wi as an initial segment of A, but has provided sufficient conditions for the backup strategies to succeed. The node βˆ∞ is assigned the backup enumeration strategy α̌(β(i)). The outcome fn represents the fact that β has been successful in securing a witness τ ∈ Wi as an initial segment of A on its n-th attempt and outcome w the fact that β has found a witness τ ⊆ A which has no extension in the set Wi . In both cases, o ∈ {fn | n < ω} and o = w, the strategy has successfully satisfied the i-th genericity requirement and βˆo is assigned the next genericity requirement β(i + 1). CUPPING AND DEFINABILITY 11 Finally outcome h signifies that the strategy β has found an element e ∈ E whose use does not stabilize at any stage, i.e. for every s there is a stage t > s such that θ(e, s) 6= θ(e, t). Again this is an outcome that would contradict our choice of Θ. It cannot be the true outcome of the strategy, but it could still seem like the correct outcome on finitely many occasions. We leave it on the tree as it will play a role in the initialization process. The node βˆh is therefore a leaf in the tree T . The backup enumeration strategy α̌ = α̌(β), activated by β, initiates the construction of a set Bα̌ , and an operator Λα̌ . The strategy is successful if ultimately Λα̌ (V ⊕ Bα̌ ) = K. This strategy has only one outcome e. The node e is assigned the first backup genericity strategy β̌(α̌, β, 0). Finally the backup genericity strategy β̌ = β̌(α̌, β, i), working with respect to α̌ and coordinating actions with β, ensures that Bα̌ satisfies the i-th genericity requirement Gi (Bα̌ ). It has three outcomes arranged as follows: f <L h <L w. Outcome f represents the fact that β̌ has been successful in securing a witness τ ∈ Wi as an initial segment of Bα̌ . Outcome w represents the fact that β̌ has found an initial segment τ ⊆ Bα̌ such that ∀µ ⊆ τ (µ ∈ / Wi ). Both nodes β̌ˆf and β̌ˆw are assigned the next genericity strategy β̌(α̌, β, i + 1). Outcome h just as in the main genericity strategy signifies the fact that β̌ has found an element ě ∈ E with unstable use. This again cannot be the true outcome of this strategy, or else we could argue that Θ(U, V ) 6= E, but it could still look like the true outcome any finite number of stages. The node β̌ˆh is a leaf in the tree T . The ordering of the outcomes induces a standard linear ordering of the nodes, the finite strings in the domain of T , namely: γ ≤ σ if γ ⊆ σ (γ is an initial segment of σ) or if there exists ρ such that ρˆo1 ⊆ γ, ρˆo2 ⊆ σ and o1 <L o2 . In the latter case we will also write γ <L σ. If γ < σ we shall say that γ has higher priority than σ. An infinite path in the tree T will be a function f ⊆ T with domain a maximal linearly ordered infinite subset of the domain of T . We will abuse notation and denote with f n both the node of length n in the domain of f and the strategy assigned to it. The next proposition shows that we have two types of infinite paths in T , ones that have a strategy for every main requirement and ones that have a strategy for every backup requirement. Propostion 4.1. Suppose f is an infinite path in the tree T . Then one of the following is true: (1) For every i > 0 a main genericity strategy of type β(i) is assigned to the node f i. (2) There is a strategy β ⊆ f such that α̌(β) is assigned to f |β| + 1 and for every i a backup strategy β̌(α̌, β, i) is assigned to the node f (|β| + i + 1). Proof. Suppose that (1) is not true and let β be the largest node of type main genericity strategy such that β ⊆ f . By our choice of β and the fact that f is infinite it follows that α̌(β) = βˆ∞ ⊆ f and β̌(α̌, β, 0) = α̌ˆe ⊆ f . Now inductively if β̌(α̌, β, i) ⊆ f then as f is infinite either β̌(α̌, β, i)ˆf ⊆ f or β̌(α̌, β, i)ˆw ⊆ f and in both cases this is a β̌(α̌, β, i + 1) strategy. 4.4. Strategies and parameters. In this section we shall give more intuition about how strategies are designed to work and define their parameters. 12 H. GANCHEV AND M. SOSKOVA 4.4.1. The main enumeration strategy. As noted above, α denotes the main enumeration strategy. The strategy α monitors the length of agreement l(Θ(U ⊕V ), E, s) at every stage s. If s is not expansionary then α has outcome b. If s is an expansionary stage then α has outcome e. At every stage s α monitors the construction of the set A and the operator Γ, so that ultimately Γ(U ⊕ A) = K. The axioms in Γ will have a particular format: to every natural number n we will assign an A-marker a(n) and a U marker u(n); the axiom enumerated in Γ at stage s for n will be of the form hn, (U {s} u(n) + 1) ⊕ (A{s} a(n) + 1)i The markers will be defined by the main genericity strategies. The only job of α is to ensure that the constructed operator is correct. So at stage s it will consider all elements n < s and correct Γ(U, A) by enumerating axioms in Γ for elements {s} n ∈ K \Γ(U ⊕A){s} . In this way we can be sure that if n ∈ K then α will consider it at infinitely many good stages in the approximation to U and will eventually enumerate an axiom, which remains permanently valid. To invalidate an axiom it is enough to consider it at infinitely many stages, regardless of whether they are good or not. So at expansionary stages the strategy will extract from A the already {s} defined A-markers that appear in valid axioms for elements n ∈ Γ(U ⊕ A){s} \ K . The parameters for α are hence A and Γ, both with initial value ∅; the markers a(n) and u(n) for every natural number n, also called the α-markers for n, initially undefined. 4.4.2. The main genericity strategy. At every stage s there will be at most one copy of the i-th main genericity strategy which is not in initial state. Let β = β(i) be the i-th main genericity strategy. Recall that the strategy β has to ensure that there is a finite binary string τ ⊆ A such that τ ∈ Wi or no extension µ ⊇ τ is in the set Wi . The strategy β has to overcome the difficulty set by the higher priority strategy α which is extracting markers from A in the rectification process. This is why the simple genericity strategy: select a witness τ ⊆ A, wait until (if ever) an extension µ ⊇ τ enters Wi , restrain µ as an initial segment of A, will not work. The strategy to satisfy Gi is a more complex version of this strategy. The strategy β will have a threshold dβ . The value of this threshold will always be the i-th element of K. We cannot guess in advance this number but, as K is an infinite set, approximated by its standard Π01 approximation, after finitely many wrong guesses we will eventually pick the right value for the threshold. The strategy β is responsible for defining values for the parameters a(dβ ) and u(dβ ). The first marker a(dβ ) that it defines is denoted as a0β and plays the real role of the threshold, the element, below which β can safely assume that A is correct on all elements and will not be further modified. The values of the A-markers are always selected to be larger than the values of the markers defined by higher priority strategies. Note that the way, in which the axioms are defined by the strategy α, ensures that every axiom enumerated in Γ{s} for elements n > dβ is an extension of the valid axiom for dβ at stage s. Thus by extracting the marker a(dβ ){s} from the set A the strategy β can invalidate all axioms for all elements n > dβ valid at stage s. Assuming that higher priority main genericity strategies have finished with their actions, and α has finished correcting Γ for elements n < dβ at stage s0 , the CUPPING AND DEFINABILITY 13 strategy β can safely assume that τ0 = A{s0 } a(dβ ) + 1 is a good candidate for a first witness. If τ0 ∈ / Wi then the strategy β is successful and needs no further actions. The outcome is w and the next genericity strategy is activated. If however there is an extension µ0 ⊇ τ0 such that µ0 ∈ Wi , then the strategy β is now in a difficult position, namely β cannot restrain A on elements a such that |τ | < a ≤ |µ|, without injuring α. This is where the set E comes into play. We will select an element e0 currently in the constructed set E called an agitator and arrange things so that every valid axiom for dβ in Γ, extends the use of e0 . The process of making this arrangement will be called honestification. To do this we wait for a large enough stage s such that the use θ(e0 , s) seems stable at stages t > s. Every time we see that the current stage does not meet this description, i.e. the use has changed since the previous β-true stage, we we must forcefully invalidate all previously enumerated axioms for dβ and reset the value of the parameter u(dβ ). The use of e0 will however eventually become stable, as otherwise we can argue that Θ(U ⊕ V ) 6= E, contradicting our choice of Θ. After finitely many iterations of honestification, at a stage s, say, we will have achieved our goal: the use of e0 has stopped changing and all valid axioms for dβ in Γ extend θ(e0 , s). We shall say that Γ is honest at dβ at stage s. Suppose also that we have found an extension µ0 ⊃ τ0 in the c.e. set Wi . The strategy β will now attack by extracting e0 from E. It will have outcome ∞ at this stage. At every + stage s+ > s, θ(e0 , s) * (U ⊕ V ){s } . If this is because of a permanent extraction from the set U , i.e at all further stages t > s( θ(e0 , s) * U {t} ⊕ N) then all axioms enumerated in Γ for elements n ≥ dβ are invalid at all furthers stages and the strategy β can successfully restrain µ0 ⊆ A with no injury to α. The strategy has outcome f0 at all stages t > s while θ(e0 , s) * U {t} ⊕ N. If the extraction disappears at stage s1 (in this case θ(e0 , s) * N ⊕ V {s1 } ) the strategy will evaluate this first cycle as unsuccessful. It will extract the marker a(dβ ), thereby preserving its work from injury by the strategy α. It will activate the backup strategy α̌(β) below outcome ∞. It will then start a new cycle with a new larger agitator e1 and witness τ1 ⊇ µ∗0 , where µ∗0 is the string µ0 inverted at only one position a(dβ ). At the end of every cycle the strategy will record in a parameter W itβ information about previous attacks. After every attack the strategy will go back an re-evaluate previous attacks. Outcome ∞ will be visited only if there is further evidence that all previous cycles are unsuccessful. The parameters for β(i) are: the threshold dβ , always assigned at stage s the {s} i-th element of K , with first marker defined by β a0β initially undefined; the current agitator eβ and witness τβ initially undefined; the list of witnesses W itβ initially empty. 4.4.3. The backup enumeration strategy. The strategy α̌ = α̌(β(i)) is similar to the main enumeration strategy. It initiates the construction of a set Bα̌ and an operator Λα̌ , so that ultimately Λα̌ (V ⊕ Bα̌ ) = K. Note that α̌ is visited in two different situations: at the beginning of an attack by β and after the end of an unsuccessful attack. Only in the second case can we be sure that the necessary extractions from the approximation of V have been secured. At such stages, at which β does not start an attack, called peaceful stages, α̌ will correct the enumeration Λα̌ (V ⊕ Bα̌ ){s} by extracting elements from B. As α̌ is not 14 H. GANCHEV AND M. SOSKOVA visited at every stage, we cannot assume that it will be visited at infinitely many good stages for the approximation to V . The strategy α̌ will therefore work with a delayed approximation to the set V . Fix a stage s and let s− < s be the previous T {s} visit of α̌ (s = 0 if α̌ has not been visited yet). Then Vα̌ = s− <t≤s V {t} . {s} It is not difficult to see that {Vα̌ }s<ω is also a good Σ02 approximation to V . The backup genericity strategies will as well assign to every element n markers bα̌ (n) and vα̌ (n). If α̌ enumerates an axiom for n at stage s, it is of the form: {s} {s} hn, (Vα̌ vα̌ (n) + 1) ⊕ (Bα̌ bα̌ (n) + 1)i. The parameters for α̌(β) are hence Bα̌ and Λα̌ , both with initial values ∅; markers bα̌ (n) and vα̌ (n) for very natural number n, initially undefined. 4.4.4. The backup genericity strategy. The i-th backup strategy β̌(α̌, β, i) ensures that Bα̌ satisfies the i-th genericity requirement in a similar way to the main genericity strategy. It has a threshold dβ̌ - the i-th element of K, and is responsible for defining the markers bα̌ (dβ̌ ) and vα̌ (dβ̌ ). The first Bα̌ -marker that β̌ defines again plays a special role and is denoted by b0β̌ . The strategy has an agitator eβ̌ for which it ensures that the operator Λα̌ is honest at dβ̌ . The strategy selects a witness τβ̌ = Bα̌ bα̌ (dα̌ ) + 1 and starts searching for an extension of τβ̌ in the set Wi . If there is no such extension then the strategy is successful and has outcome w. Otherwise it has found an extension µ ⊆ τβ̌ in the set Wi and now would like to force a change in the approximation to V in order to be able to secure µ ⊆ Bα̌ . To do so the strategy β̌ will time its attack with one of the attacks of the strategy β. Instead of attacking immediately, it will wait for a stage s at which β is also attacking. As every new cycle of β comes with a new larger agitator eβ , {s} {s} {s} {s} at stage s we have eβ̌ < eβ , hence θ(eβ̌ , s) ⊆ θ(eβ , s). If both eβ̌ and eβ are extracted during a joint attack by β̌ and β at stage s then it will be sufficient for β to look at the changes resulting in θ(eβ̌ , s) * (U ⊕ V ){t} at further stages t > s, when evaluating this attack. In this way whenever the backup strategies are activated at two consecutive stages t > t− > s of the second type (at stages t− and t the strategy β has just evaluated an attack as unsuccessful) we have that T θ(eβ̌ , s1 ) * N⊕( t− <r≤t V {r} ) and so without injury to α̌ the strategy β̌ can secure µ as an initial segment to Bα̌ and have outcome f at all further stages. The parameters for β̌(α̌, β, i) are: the threshold dβ̌ , always assigned at stage {s} s the i-th element of K , with first Bα̌ -marker b0β̌ ; the current agitator eβ̌ and witness τβ̌ initially undefined. 4.5. The construction. The construction is in stages. At every expansionary stage s we construct a finite path of length less than or equal to s, δ {s} . The intention is that there will be a true path - a leftmost path of strategies visited at infinitely many stages, along which all strategies are successful. At the start of the construction all nodes are initialized, E {0} = N and δ {0} = ∅. At stage s > 0 we construct the E {s} from its previous value by allowing active strategies to extract elements from E {s−1} and the finite string δ {s} inductively in steps. δ {s} 0 is always the root of the tree, the main enumeration strategy α. We obtain δ {s} (n + 1) by activating the strategy δ {s} n and allowing it to select an outcome o, then δ {s} (n + 1) = δ {s} nˆo. This process continues until we have defined a string δ {s} of length s or until we have reached a leaf in the tree CUPPING AND DEFINABILITY 15 of strategies. At the end of stage s we initialize all strategies γ > δ {s} . When we initialize a strategy γ- it’s parameters are set to their initial values. Otherwise the parameters inherit their values from the previous stage at which γ was visited and we will not indicate a stage when referring to the current values of the parameters. Suppose we have defined δ {s} n and n < s. We have four cases depending on the type of strategy assigned to δ {s} n. Case 1: The strategy δ {s} n = α is the main enumeration strategy. The strategy proceeds as follows: {s} \ Γ(U {s} ⊕ A{s} ) and both a(n) and u(n) (1) For all n < s such that n ∈ K are defined then enumerate in Γ the axiom hn, (U {s} u(n) + 1) ⊕ (A a(n) + 1)i. (2) If s is not expansionary l(Θ(U ⊕ V ), E, s) ≤ max l(Θ(U ⊕ V ), E, t) t<s then let the outcome be b. {s} (3) If s is expansionary then for all n < s such that n ∈ Γ(U {s} ⊕ A) \ K find all valid axioms, say hn, Du ⊕ Da i ∈ Γ, extract the largest element of Da from A. (Note that we are changing the value of the parameter A.) Let the outcome be o = e. Case 2: The strategy δ {s} n = β(i) is a main genericity strategy. At stage s the strategy first passes through Check. Let s− be the previous stage at which β was visited. • Check: {s} Let dβ be the i-th element of K . If the strategy is in initial state or {s− } {s} {s− } {s− } {s} \K dβ 6= dβ , i.e there is an element m ≤ dβ such that m ∈ K then go to step 1 of Initialization. If at stage s the strategy α extracts an element a < a0β then initialize all of β’s parameters and go to step 2 of Initialization. Otherwise proceed to the submodule indicated at the previous β-true stage s− . • Initialization: (1) Define a new A-marker a(dβ ) as a fresh number, larger than any number that has so far been used in the construction, and enumerate it in the set A. Set a0β = a(dβ ) and make all A- and U -markers for elements n > dβ undefined. (2) Initialize all lower priority strategies. (3) Define a new agitator eβ ∈ E {s} , as a fresh number. (4) If eβ ≥ l(Θ(U ⊕ V ), E, s) then end this substage with outcome h and return to this step at the next β-true stage. Otherwise proceed to the next step. (5) Extract a(dβ ) from the set A and define a fresh value a(dβ ) and enumerate it in A. Define u(dβ ) to be a number larger than the maximal number in θ(eβ , s). Make all A- and U -markers for elements n > dβ undefined. Let τβ = A a(dβ ) + 1. End this substage with outcome h. Proceed to Honestification at the next stage. 16 H. GANCHEV AND M. SOSKOVA • Honestification: If θ(eβ , s) 6= θ(eβ , s− ) or if there is a stage t, such that s− < t ≤ s and θ(eβ , s) * (U ⊕ V ){t} then extract a(dβ ) from the set A. Define a fresh value for the marker a(dβ ) and enumerate it in A. Define a new value for the marker u(dβ ) larger than the maximal number in θ(eβ , s). Make all A- and U -markers for elements n > dβ undefined. Let τβ = A a(dβ ) + 1. End this substage with outcome h. Return to Honestification at the next stage. Otherwise go to Waiting . {s} • Waiting: If there is a finite string µ ⊇ τβ such that µ ∈ Wi then proceed to Attack. Otherwise let the outcome be o = w. Return to Honestification at the next stage. • Attack: {s} (1) Let µ ⊇ τβ be a string such that µ ∈ Wi . Set aµ = a(dβ ) and µ∗ to be the string µ modified in bit aµ so that µ∗ (aµ ) = 0. Enumerate a new entry in the list W itβ namely: hµ, µ∗ , aµ , θ(eβ , s)i. (2) Extract the agitator eβ from the set E {s} and for all a such that a0β ≤ a ≤ |µ| set A(a) = µ∗ (a). (Note that we are modifying the parameter A so that the current marker of the threshold aµ = a(dβ ) is extracted from the set.) Define a new value for the marker a(dβ ) as a fresh number, larger than the length of the string µ, |µ|, and enumerate it in A. Make all A- and U -markers for elements n > dβ undefined. (3) Let the outcome be (o = ∞). At the next true stage go to Result. • Result: Let ē be the least element that was extracted during s− , the stage of the attack. Note that θ(ē, s− ) ⊆ θ(eβ , s− ). If eβ 6= ē then modify the fourth component of the last entry in the list W itβ , making it: hµ, µ∗ , aµ , θ(ē, s− )i. Scan all entries in the list W itβ in the order in which they are enumerated in the list from first to last. Suppose β is examining the n-th entry W itβ [n] = hµn , µ∗n , an , Un ⊕ Vn , sn i. For all a such that a0β ≤ a ≤ |µn | set A(a) = µn (a). (1) If at all stages t, such that s− < t ≤ s, Un * U {t} then let the outcome be o = fn . Return to this sub-step at the next true stage. (2) Otherwise there is a stage t, such that s− < t ≤ s and Vn * V {t} . For all a such that a0β ≤ a ≤ |µn |, set A(a) = µ∗n (a). (This is necessary because the strategy α might have acted at this stage to invalidate an axiom for an element m > dβ , which extends hm, Un ⊕ {an }i.) We say that W itβ [n] is unsuccessful. (3) If all entries are scanned and all are unsuccessful then end this substage with outcome o = ∞. At the next stage return to step 3 of Initialization, choosing a new agitator. Case 3. The strategy δ {s} n = α̌(β(i)) is a backup enumeration strategy. Let T {s} s be the previous visit of α̌. Let Vα̌ = s− <t≤s V {t} . The strategy proceeds as follows: − CUPPING AND DEFINABILITY {s} 17 {s} (1) For all n < s, such that n ∈ K \ Λα̌ (Vα̌ ⊕ Bα̌ ) and both bα̌ (n) and vα̌ (n) are defined, enumerate in Λα̌ the axiom {s} hn, (Vα̌ vα̌ (n) + 1) ⊕ (Bα̌ bα̌ (n) + 1)i. (2) If at stage s the strategy β does not attack, i.e. the visit is peaceful, then {s} {s} find all valid axioms, for all n < s such that n ∈ Λα̌ (Vα̌ ⊕ Bα̌ ) \ K say hn, Dv ⊕ Db i ∈ Λα̌ , extract the largest element of Db from Bα̌ . Let the outcome be o = e. Case 4. The strategy δ {s} n = β̌(α̌, β̌, i) is a backup genericity strategy. • Check: Let dβ̌ be the i-th element of K state or if • • • • {s− } dβ̌ 6= {s} dβ̌ {s} . If the strategy is in initial then go to step 1 of Initialization. If at stage s the strategy α̌ extracts an element b < b0β̌ then initialize all of β̌’s parameters and go to step 2 of Initialization. Otherwise proceed to the submodule indicated at the previous β̌-true stage s− . Initialization: (1) Define a new Bα̌ -marker bα̌ (dβ̌ ) as a fresh number, larger than any number that has so far been used in the construction, and enumerate it in the set Bα̌ . Let b0β̌ = bα̌ (dβ̌ ) and make all Bα̌ - and Vα̌ -markers for elements n > dβ̌ undefined. (2) Initialize all lower priority strategies. (3) Define a new agitator eβ̌ ∈ E {s} , as a fresh number. (4) If eβ̌ ≥ l(Θe (U ⊕ V ), E, s) then end this substage with outcome h and return to this step at the next β̌-true stage. Otherwise proceed to the next step. (5) Extract bα̌ (dβ̌ ) from the set Bα̌ and define a fresh value bα̌ (dβ̌ ) and enumerate it in Bα̌ . Set vα̌ (dβ̌ ) to be a number larger than max(θ(eβ̌ , s)). Make all Bα̌ - and Vα̌ -markers for elements n > dβ̌ undefined. Set τβ̌ = Bα̌ bα̌ (dβ̌ ) + 1. End this substage with outcome h. Proceed to Honestification at the next stage. Honestification: If θ(eβ̌ , s) 6= θ(eβ̌ , s− ) or if there is a stage t, such that s− < t ≤ s and θ(eβ̌ , s) * (U ⊕ V ){t} then extract bα̌ (dβ̌ ) from the set Bα̌ . Define a fresh value for the marker bα̌ (dβ̌ ) and enumerate it in Bα̌ . Define a new value for the marker vα̌ (dβ̌ ) larger than the maximal number in θ(eβ̌ , s). Make all Bα̌ - and Vα̌ -markers for elements n > dβ̌ undefined. Set τβ̌ = Bα̌ bα̌ (dβ̌ ) + 1. End this substage with outcome h. Return to Honestification at the next stage. Otherwise go to Waiting. {s} Waiting: If there is a finite string µ ⊇ τβ̌ such that µ ∈ Wi then proceed to Attack. Otherwise let the outcome be o = w. Return to Honestification at the next stage. Attack: (1) If at stage s the strategy β dose not perform an attack then let the outcome by o = w, return to Honestification at the next stage. Otherwise proceed to the next step. (Note this is how β̌ times its attack with β.) 18 H. GANCHEV AND M. SOSKOVA {s} (2) Let µ ⊇ τβ̌ be a string such that µ ∈ Wi . For all b such that τβ̌ < b < |µ|, set Bα̌ (b) = µ(b). Define a new fresh value for the marker bα̌ (dβ̌ ), a number larger than the length of the string µ, and enumerate it in Bα̌ . Make all Bα̌ - and Vα̌ -markers for elements n > dβ̌ undefined. (3) Extract eβ̌ from the set E {s} and go to Result. • Result: Let the outcome be o = f. Return to this step at the next true stage. 4.6. Verification of the construction. The tree of strategies T has two features which make it nontrivial to prove that there is an infinite true path in the construction. Some nodes have infinitely many outcomes and some nodes are leaves. To start off we prove that the true path exists even though some nodes in the tree have infinitely many outcomes and contains at least one node different from the root, i.e. is of length at least 2. Later on we shall see that the true path is infinite. Propostion 4.2. There exists a path f in the tree of strategies T such that: (1) For all β ⊆ f there is a stage s such that at all t > s, (δ {t} ≥ β). (2) For all β ⊆ f there exist infinitely many stages s such that β ⊆ δ {s} . Proof. We prove that every strategy, visited at infinitely many stages has a leftmost infinite outcome, i.e. a leftmost outcome that it has at infinitely many true stages, also called the true outcome, which is not a leaf. Then f is defined inductively by f (0) = ∅ and f (n + 1) is the true outcome of f n, if f n is not a leaf and f = f n, otherwise. The main enumeration strategy has true outcome e, as by our choice of Θ and the property 4.1 there are infinitely many expansionary stages. The backup enumeration strategies and backup genericity strategies have only finitely many outcomes. the leftmost one visited at infinitely many stages is their true outcome. So suppose β is a main genericity strategy, visited at infinitely many stages. If β has outcome ∞ at infinitely many stages then this is the true outcome of β. Otherwise there is a stage s such that β does not have outcome ∞ at all t > s. It follows from the construction that no new entries are enumerated into the list W itβ after stage s and hence the only possible outcomes for β at stages t > s are finitely {s} many: w, h, and fn where n ≤ W itβ , and the leftmost one of them visited at infinitely many stages is β’s true outcome. We know now that there is at least one main genericity strategy along the true path, namely β(0) = αˆe. We shall next investigate some properties of main genericity strategies along the true path. Propostion 4.3. Let β be a main genericity strategy on the true path. Then: (1) There is a stage s0β such that: β is not initialized at stages t > s0β , β is the only main genericity strategy of type (i) accessible at stages t > s0β and β is visited at every αˆe-true stage t > s0β . (2) There is a stage sdβ such that at stages t > sdβ the value of dβ does not change. At stage sdβ the final value of the marker a0β is defined. All αmarkers for the element dβ are defined by β at stages t ≥ sdβ . CUPPING AND DEFINABILITY 19 (3) There is a stage scβ ≥ sdβ such that at stages t > scβ Check does not send β to Initialization. At stages t > scβ the parameter A is not modified on elements a < a0β . (4) After stage scβ every time β changes the value of the marker a(dβ ) all main genericity strategies β(j),where j > i, that are accessible at stages t > scβ , i.e. for which there is a true stage t > scβ , are in initial state. (5) If β’s true outcome is w or fn for some natural number n then there is a stage seβ such that β does not modify any parameters and has its true outcome at every true stage t > seβ . Proof. Assume inductively that the statement is true for main genericity strategies along the true path of higher priority than β = β(i). It follows by the definition of the tree that all such strategies have outcome w or fn for some n. By the induction hypothesis (claim 5) and the fact that β ⊆ f there is a stage s0β such that β is not initialized after stage s0β and such that at stages t > s0β the parameter A is not modified by main genericity strategies of higher priority than β. Furthermore it follows that the markers a(n) and u(n) for the first i − 1 elements of K do not change as the only accessible strategies of type β(j), where j ≤ i are the ones that are initial segments of β. In other words if s > s0β is an αˆe-true stage then s is a β-true stage. Hence the only strategies of lower priority than β that are accessible at stages t > s0 are strategies which extend β. {sd } Let sdβ ≥ s0β be such that K β correctly approximates the first i elements of K. Then after stage sdβ the value of the threshold dβ does not change and a0β receives d its final value, i.e. (a0β ){t} = (a0β ){sβ } = a0β for all t ≥ sdβ . As β is the only strategy of type (i) accessible after stage sdβ , dβ receives α-markers only from β after stage sdβ . After stage sdβ the strategy α will extract finitely many numbers a < a0β . And every time such an element is extracted it will not be reenumerated back in A. This follows from the fact that at stages t > sdβ strategies of higher priority β do not modify A and accessible strategies of lower priority γ ⊇ β are initialized at stage sdβ and modify A only on elements larger than a0γ ≥ a0β . Hence there is a least stage scβ such that at stages t > scβ the strategy α does not extract numbers less than a0β from A and hence A a0β is not modified at stages t > scβ . At stage scβ the strategy β performs step 2 of Initialization for the last time and all lower priority strategies are in initial state. The following is a diagram which shows the way in which β can change its outcome at consecutive true stages: h ⇐ ∞ ⇐ · · · ⇐ f1 ⇐ f0 ⇐ ∞ ⇐ (h ⇔ w) The strategy β changes the value of the marker a(dβ ) at stage s > scβ only when it has outcome h during Initialization or Honestification and when it has outcome ∞ during Attack at stage s. In the second case all main genericity strategies are initialized at stage s. In the first case let s− be the largest stage scβ < s− < s such that β has outcome ∞ if there is such state and s− = scβ otherwise. Then strategies extending outcomes fi for some natural number i are in initial state at stage s− and are not accessible at stages t ∈ [s− , s]. Strategies extending w are initialized at stage s. 20 H. GANCHEV AND M. SOSKOVA If β has true outcome o ∈ {w, fn | n < ω}, then from the diagram it follows that there is a stage seβ such that β has outcome o at all stages t > seβ . From the construction it follows that β does not modify any parameters . The properties listed above are true for the backup genericity strategies along f . Propostion 4.4. Let β̌ be a backup genericity strategy on the true path. Then: (1) There is a stage s0β̌ such that: β̌ is not initialized at stages t > s0β̌ , β̌ is the only backup genericity strategy of type (α̌, β, i) accessible at stages t > s0β̌ and β̌ is visited at every α̌-true stage t > s0β̌ . (2) There is a stage sdβ̌ such that at stages t > sdβ̌ the value of dβ̌ does not change. At stage sdβ̌ the limit value of the marker b0β̌ is defined. All α̌markers for the element dβ̌ are defined by β̌ at stages t ≥ sdβ̌ . (3) There is a stage scβ̌ > sdβ̌ such that at stages t > scβ̌ Check does not send β̌ to Initialization. At stages t > scβ̌ the value of Bα̌ is not modified below b0β̌ . (4) After stage scβ̌ every time β̌ changes the value of the marker bα̌ (dβ̌ ) all backup genericity strategies β̌(α̌, β, j), where j > i, that are accessible at stages t > scβ̌ , i.e. for which there is a true stage t > scβ̌ , are in initial state. (5) If β̌’s true outcome is w or f then there is a stage seβ̌ such that β̌ does not modify any parameters and has its true outcome at true every stage t > seβ̌ . Proof. The proof is carried out in the same way as the proof of Proposition 4.3. Finally we are ready to prove that the true path is infinite. Propostion 4.5. If β ⊆ f is a main genericity strategy then it’s true outcome is not h. Similarly if β̌ ⊆ f is a backup genericity strategy then it’s true outcome is not h. Hence the true path is infinite. Proof. Suppose towards a contradiction that β ⊆ f has true outcome h and let s ≥ scβ be a stage such that at stages t > s the strategy β is not initialized and does not have outcome ∞. Then at stages t > s the strategy β has a fixed agitator eβ ∈ E. As E = Θe (U ⊕ V ) then limt θ(eβ ) = θ(eβ ) exists and θ(eβ ) ⊆ U ⊕ V . Let slim > s be a β-true stage such that at all stages t > slim we have θ(eβ , t) = θ(eβ ) and θ(eβ ) ⊆ (U ⊕ V ){t} . It follows that β cannot have outcome h at stages t > slim contradicting the fact that h is β’s true outcome. The second statement is proved in a similar way. Propostion 4.6. Let β ⊆ f be a main genericity strategy and let dβ be the limit value of β’s threshold attained at stage sdβ . If τβ is defined as the current witness of β at stage s ≥ scβ then for all a ≥ a0β such that a is a previous value of the A-marker of the threshold dβ , τβ (a) = 0. Proof. We prove this with induction on the stage s. Suppose that the statement is {s} true for values of the witness τβ defined before stage s. Recall that τβ = A{s} a(dβ ). If a is an old marker of the threshold dβ , a < a(dβ ){s} and it is sufficient to prove that a ∈ / A{s} . Suppose towards a contradiction that a is an old marker defined before and cancelled before or on stage s and a ∈ A{s} . As every time β cancels an old value CUPPING AND DEFINABILITY 21 of the A-marker of the threshold, it extracts this value from A, this could only be possible if a strategy later on at stage sa < s re-enumerates a in A and a remains in the set A at all stages t ∈ [sa , s]. By Proposition 4.3 the only strategy that can re-enumerate a in the set A is the strategy β and by construction this is only possible if at stage sa the strategy β starts evaluating W itβ [n]{sa } for some n, and µn (a) = 1. But µn is defined as an extension of a previous value τ of the witness τβ and by induction if a < |τ | then τ (a) = 0. It follows that |τ | ≤ a < |µn | and by construction the only possibility is that a = an , as the next value of the Amarker for dβ is defined as a number larger than |µ|. So at stage sa the strategy β has outcome fn and is evaluating the result of its most recent attack. At stage s a new value for τβ is defined, so β must have evaluated it most recent attack as unsuccessful. This means that at a stage in the interval (sa , s) the strategy β evaluates W itβ [n] as unsuccessful and extracts an = a from the set A, contradicting our choice of stage sa . It follows that the assumption is wrong and a ∈ / A{s} . Propostion 4.7. Let β ⊆ f be a main genericity strategy and let dβ be the limit value of β’s threshold attained at stage sdβ . If an axiom hx, Du ⊕ Da i is enumerated in Γ{s} for an element x ∈ / K after stage sdβ then one of the following holds: (1) s ≤ scβ . Then the axiom is invalid at all stages t > scβ . (2) Da contains a marker a of the threshold dβ which is cancelled as current at stage s+ at which β defines the next value of the A-marker of the threshold. Then a ∈ / A{t} at all t > s+ . (3) Da contains a marker a of the threshold dβ which is cancelled as current at stage s+ and at stage s+ , a = an becomes a component of the n-th entry in the list W itβ , hµn , µ∗n , an , Un ⊕ Vn i and in this case Un ⊆ Du . (4) Da contains the final value of the A-marker of the threshold dβ . {s} Proof. As s > sdβ and x ∈ K \ K it follows that x > dβ . By the fact that every time a new value for the markers of dβ are defined, the markers for x are cancelled and the format of the axioms enumerated in Γ it follows that Da contains the current marker a = a(dβ ){s} which is defined by β by Proposition 4.3. If s ≤ scβ then at stage scβ the strategy α extracts an element a0 < a0β such that a0 ∈ A{s} , hence a0 ∈ Da , which is never re-enumerated in the set A. It follows that the axiom is invalid at all stages t > scβ . So suppose that s > scβ If a = a(dβ ){t} at all t > s then case 4 is true. Otherwise let s+ be the stage at which a(dβ ) is changed. If a ∈ A{t} at some t > s+ . Then as in Proposition 4.6 only β can enumerate a in the set A during Result if for some n, µn (a) = 1. This is only possible if an = a. So if a 6= an for any member if the list W itβ then a ∈ / A{t} at all stages t > s+ . + Finally suppose a = an for some n. Then s is the stage of the n-th attack after stage scβ . Let s− be the stage at which a(dβ ) received the value a. Then at this {s− } stage u(dβ ) is set to a number larger than the maximal number of θ(eβ , s− ) and all α-marker for elements n > dβ are undefined. At stages t ∈ (s− , s+ ] the strategy β does not change the value of a(dβ ) and hence has outcome w if visited. It follows {s} {s− } that s ∈ (s− , s+ ] and eβ = eβ = eβ . On the other hand θ(eβ , s+ ) = θeβ ,s ⊆ {s} + (U ⊕ V ) . Hence θ(eβ , s ) ⊆ Du ⊕ N. Finally Un ⊕ Vn is defined as the value of 22 H. GANCHEV AND M. SOSKOVA θ(ē, s+ ), where ē ≤ e. As by the definition of the use function θ(ē, s+ ) ⊆ θ(e, s+ ), we can conclude that Un ⊆ Du . As by Proposition 4.6 at all stages t ≥ s+ if an ∈ A{t} then β has outcome fn at stage t and hence Un * U {t} , the axiom hx, Du ⊕ Da i is invalid at all stages t ≥ sn . Corollary 4.1. If β = β(i) ⊆ f has true outcome w or fn for some natural number n then β successfully satisfies Gi . Proof. Suppose that β has outcome o = w or o = fn for some natural number n at all stages t ≥ seβ , where seβ is a least such stage. Then by Proposition 4.3 at stage seβ all lower priority main genericity strategies γ ⊇ βˆo are in initial state at stage se and will not modify A{t} on numbers a < a(dβ ){t} < (a0γ ){t} at stages t ≥ seβ . Higher priority main genericity strategies do not modify A at all. Suppose that β has outcome w at all stages t ≥ seβ . Then the final value of the witness τβ is defined at stage shβ , the previous β-true stage before seβ . Note that shβ h h is the last stage at which β has outcome h and τβ = A{sβ } a(dβ ){sβ } . The final value of the witness τβ does not belong to the set Wi , otherwise after stage seβ , β would have outcome ∞. To see that τβ ⊆ A we show that α does not modify A |τ | at stages t > shβ . Indeed, the only case in which α would need to change A after stage sh on a number less than |µ| is when it sees a valid axiom for and element {t} x∈ /K which was enumerated before stage sh . By Proposition 4.7 it follows that Case 1, 2 and 4 cannot apply to this axiom. Case 3 does not apply as well as by Proposition 4.6 for all entries in the list W itβ , τβ (an ) = 0 and hence A{sh } (an ) = 0. As by assumption β does not enter Result after stage shβ , no strategy including β can re-enumerate these markers back in A{t} at all t > shβ . As there are no more choices for the assumed axiom, it follows that t does not exists and α does not modify A{t} on numbers a < |τ | at stages t > shβ . Now suppose that β has outcome fn . Then µn ⊆ Wi and at stage seβ the strategy e β starts evaluating W itβ [n] and sets µn ⊆ A{sβ } . In this case as well it is easy to see that µn will remain an initial segment of A at all further stages as axioms for elements x ∈ / K with maximal A-marker less than |µn | are invalid at all stages t > seβ . They cannot be Case 4 axioms, and Case 1 and 2 axioms are obviously not valid at any stage t > seβ . Case 4 axioms which contain markers am for m < n are invalid as µn (am ) = 0. Indeed µn is defined as an extension of a previous witness τβ which by Proposition 4.6 has this property. Finally if the axiom is of the form hx, Du ⊕ Da i and Da contains an then Un ⊆ Du . However at all stages t > seβ , Un * U {t} hence in this case as well α does not modify A{t} on numbers a ≤ |µn |, hence µn ⊆ A. Propostion 4.8. Let β̌ = β̌(α̌, β̌, i) ⊆ f and let dβ̌ be the limit value of β̌’s threshold attained at stage sdβ̌ . If an axiom hx, Dv ⊕ Db i is enumerated in Λ{s} for an element n ∈ / K after stage sdβ̌ then one of the following holds: (1) s ≤ scβ̌ . Then the axiom is invalid at all stages t > sβ̌c . (2) Db contains a marker b of the threshold which is extracted at stage s+ at which β̌ defines the next value of the Bα̌ -marker, and is never reenumerated in Bα̌ . CUPPING AND DEFINABILITY 23 (3) Dv contains a subset Vn which eventually becomes a component of the n-th entry in the list W itβ , hµn , µ∗n , an , Un ⊕ Vn i. (4) Da contains the final value of the A-marker of the threshold dβ . Proof. Part one is proved just as Part 1 of Proposition 4.7, so assume that s > scβ̌ . We note that scβ̌ > scβ as every time β is restarted during Check, β̌ is initialized. {s} As s > scβ̌ and x ∈ K \ K it follows that x > dβ̌ . By the fact that every time new values for the markers of dβ̌ are defined, the α̌-markers for n are cancelled and the format of the axioms enumerated in Λα̌ it follows that Db contains the current marker b = bα̌ (dβ̌ ){s} which is defined by β̌ by Proposition 4.4. If b = bα̌ (dβ̌ ){t} at all t > s then case 4 is true. Otherwise let s+ be the stage at which bα̌ (dβ̌ ) {t} is changed. If this is during Initialization or Honestification then b ∈ / Bα̌ at all t > s+ . Suppose that s+ is the stage at which β̌ performs an Attack and times it with the n-th Attack of β. Then at stage s+ the strategy β̌ extracts its agitator eβ̌ . On the next β-true stage the strategy β evaluates the result of its n-th attack and enumerates as the fourth component Un ⊕ Vn = θ(eβ̌ , s+ ). Let s− be the stage at which b(α̌)(dβ̌ ) received the value b. Then at this stage {s− } vα̌ (dβ̌ ) is set to a number larger than the maximal number of θ(eβ̌ , s− ) and all α̌-marker for elements n > dβ̌ are undefined. At stages t ∈ (s− , s+ ] the strategy β̌ does not change the value of bα̌ (dβ̌ ) and hence has outcome w if visited. It follows {s} {s− } {s+ } that s ∈ (s− , s+ ] and eβ̌ = eβ̌ = eβ̌ = eβ̌ and θ(eβ̌ , s− ) = θeβ̌ ,s = θeβ̌ ,s+ = T Un ⊕ Vn ⊆ t∈[s− ,s] (U ⊕ V ){t} . Hence Vn ⊆ Dv . Corollary 4.2. If β̌ = β̌(α̌, β, i) ⊆ f has true outcome w or f then β successfully satisfies Gi (A). Proof. Suppose that β̌ has outcome o = w or o = f at all stages t ≥ seβ̌ , where seβ̌ is a least such stage. Then by Proposition 4.4 at stage seβ all lower priority backup {t} genericity strategies γ ⊇ β̌ˆo are in initial state at stage seβ̌ and will not modify Bα̌ on numbers b ≤ bα̌ (dβ̌ ){t} < (b0γ ){t} at stages t ≥ seβ . Higher priority strategies do not modify Bβ̌ at all at stages t ≥ seβ̌ . {t} We prove that α̌ does not modify Bα̌ on numbers b ≤ bα̌ (dβ ){t} at stages t > seβ . Suppose towards a contradiction that it does. Then at a stage t > seβ̌ , α̌ invalidates {t} a valid at stage t axiom, hx, Dv ⊕ Da i, for an element x ∈ / K . By Proposition 4.8 this must be a case 3 axiom and Dv contains a subset Vn which at a stage s < seβ becomes a component of the n-th entry in the list W itβ , hµn , µ∗n , an , Un ⊕ Vn i. By construction at stage t > seβ̌ the strategy β has outcome ∞ after evaluating W itβ [n] {t} as unsuccessful, hence Vn * Vα̌ , contradicting the assumption that hx, Dv ⊕ Da i is valid at stage t. If β̌ has outcome w at all stages t ≥ seβ . Then τβ̌ ⊆ Bα̌ and τβ̌ ∈ / Wi . Indeed if {t} τβ̌ ∈ Wi and t1 < t2 are two consecutive β̌-true stages after t then at least one of them is a stage of an attack by the main genericity strategy β, hence β̌ would attack and have outcome h <L w, contradicting the choice of seβ̌ . 24 H. GANCHEV AND M. SOSKOVA {se } If β̌ has outcome f then at stage seβ̌ it has found an µ ∈ Wi , ensured µ ⊆ Bα̌ β̌ and defined the final value of bα̌ (dβ̌ ) > |µ|. It follows that µ ⊆ Bα̌ . Lemma 4.1. There is a ∆02 1-generic set C such that U ⊕ C ≡e K or V ⊕ C ≡e K. Proof. By proposition 4.1 we have two cases for the true path f : Case 1: For every i a strategy of type β(i) is assigned to the node f i. We will prove that in this case C = A is the required set. It follows from the construction and Part (2) of Proposition 4.3 that the limit values of the markers a0i = a0β(i) exist for every β(i) ⊆ f and form an unbounded increasing sequence. Furthermore by Part (3) of Proposition 4.3 for every i there is a stages si = scβ(α,i) , such that at all stages t > si , A{si } Ai = A{t} Ai and hence the set A is ∆02 . For every number n if n ∈ / K then the actions of the main enumeration strategy α ensure that at infinitely many stages s (the αˆe-true stages after the extraction of n from K) n ∈ / (Γ(U ⊕ A)){s} , hence n ∈ / Γ(U ⊕ A). Let n be the i-th element of K. Then n = dβ at all stages t > sdβ , where β = β(α, i) ⊆ f . Hence at all stages t > sdβ the α-markers for n are defined. By our assumption Proposition 4.5 and our assumption on f , either o = fk for some k or o = w is the true outcome for β and there is a stage seβ such that the α-markers for n, u(n) and a(n) do not change after stage seβ . Let s > scβˆo be a U -true stage such that at all t > s U u(n) + 1 ⊆ U {t} . Then at stage s, α ensures that there is a valid axiom for n in Γ, say hn, Un ⊕ An i. By our choice of stage s Un ⊆ U {t} and An ⊆ A{t} at all stages t > s, hence n ∈ Γ(U ⊕ A). Finally by Corollary 4.1 it follows that A is 1-generic. Case 2: There is a strategy β ⊆ f such that α̌(β) is assigned to f |β| + 1 and for every i a backup strategy β̌(α̌, β, i) is assigned to the node f |β| + i + 1. We will prove that in this case C = Bα̌ is the required set. That Bα̌ is ∆02 is proved as in the first case using the limit values of the markers 0 bi = b0β̌(α̌,β,i) for every β̌ ⊆ α̌ ⊆ f and by Part (3) of Proposition 4.4. To prove that Λα̌ (V ⊕ Bα̌ ) we observe that there are infinitely many stages s (the α̌-true stages after the extraction of n from K at which β does not attack) at {s} which α ensures that there are no valid axioms for elements n < s, n ∈ / K . If n is the i-th element of K then n = dβ̌ at all stages t > sdβ̌ , where β̌ = β̌(α̌, β, i) and the values of its α̌-markers will eventually reach a limit. Hence at a α̌ stage s at {t} which V vα̌ (n) + 1 ⊆ Vα̌ ⊆ V the strategy α̌ ensures that there is a valid axiom for n in Λα̌ at all stages t > s, hence n ∈ Λα̌ (V ⊕ Bα̌ ). Finally by Corollary 4.2 it follows that Bα̌ is 1-generic. Acknowledgements: We would like to thank an anonymous referee, whose comments and remarks helped us to improve the exposition of this article. References [1] M. M. Arslanov, S. B. Cooper, and I. Sh. Kalimullin, Splitting properties of total enumeration degrees, Algebra and Logic 42 (2003), 1–13. [2] M. M. Arslanov and A. Sorbi, Relative splittings of 00e in the ∆2 enumeration degrees, Lect. Notes in Logic 13 (1999), 44–56. CUPPING AND DEFINABILITY 25 [3] S. Bereznyk, R. Coles, and A. Sorbi, The distribution of properly Σ02 e-degrees, J. Symbolic Logic 65 (2000), 19–32. [4] S. B. Cooper, Partial degrees and the density problem. Part 2: The enumeration degrees of the Σ2 sets are dense, J. Symbolic Logic 49 (1984), 503–513. [5] , Enumeration reducibilty, nondeterministic computations and relative computability of partial functions, Recursion theory week, Oberwolfach 1989, Lecture notes in mathematics (Heidelberg) (K. Ambos-Spies, G. Muler, and G. E. Sacks, eds.), vol. 1432, Springer-Verlag, 1990, pp. 57–110. [6] , Computability theory, Chapman & Hall/CRC Mathematics, Boca Raton, FL, New York, London, 2004. [7] S. B. Cooper and C. S. Copestake, Properly Σ2 enumeration degrees, Z. Math. Logik Grundlag. Math. 34 (1988), 491–522. [8] S. B. Cooper, A. Li, A. Sorbi, and Y. Yang, Bounding and nonbounding minimal pairs in the enumeration degrees, J. Symbolic Logic 70 (2005), 741–766. [9] S. B. Cooper, A. Sorbi, and X. Yi, Cupping and noncupping in the enumeration degrees of Σ02 sets, Annals of Pure and Applied Logic 82 (1996), 317–342. [10] C. Copestake, 1-Genericity in the enumeration degrees, J. Symbolic Logic 53 (1988), 878– 887. [11] R. M. Friedberg and Jr. H. Rogers, Reducibility and completeness for sets of integers, Z. Math. Logik Grundlag. Math. 5 (1959), 117–125. [12] H. Ganchev and M. I. Soskova, Embedding distributive lattices in the Σ02 enumeration degrees, accepted in Journal of Logic and Computation. [13] , The high/low hierarchy in the local structure of the ω-enumeration degrees, accepted in Annals of Pure and Applied Logic. [14] , Interpreting true arithmetic in the local structure of the enumeration degrees, in preparation. [15] C. G. Jockusch, Semirecursive sets and positive reducibility, Trans. Amer. Math. Soc. 131 (1968), 420–436. [16] I. Sh. Kalimullin, Definability of the jump operator in the enumeration degrees, Journal of Mathematical Logic 3 (2003), 257–267. [17] A. H. Lachlan and R. A. Shore, The n-rea enumeration degrees are dense, Arch. Math. Logic 31 (1992), 277–285. [18] K. McEvoy, Jumps of quasi-minimal enumeration degrees, J. Symbolic Logic 50 (1985), 839–848. [19] A. Sorbi, The enumeration degrees of the Σ02 sets, Complexity, Logic and Recursion Theory (New York) (A. Sorbi, ed.), Marcel Dekker, 1997, pp. 303–330. [20] M. I. Soskova, A non-splitting theorem in the enumeration degrees, Annals of Pure and Applied Logic 160 (2009), 400–418. [21] M. I. Soskova and G. Wu, Cupping ∆02 enumeration degrees, Mathematical Structures in Computer Science 19 (2009), 169–191. Faculty of Mathematics, Sofia University, 5 James Bourchier bvld., 1164 Sofia