In her 1990 thesis, Ahmad showed that there is a so-called “Ahmad pair”, i.e., there are incomparable -enumeration degrees and such that every enumeration degree is . At the same time, she also showed that there is no “symmetric Ahmad pair”, i.e., there are no incomparable -enumeration degrees and such that every enumeration degree is and such that every enumeration degree is .
In this paper, we first present a direct proof of Ahmad’s second result. We then show that her first result cannot be extended to an “Ahmad triple”, i.e., there are no -enumeration degrees , and such that both and are an Ahmad pair. On the other hand, there is a “weak Ahmad triple”, i.e., there are pairwise incomparable -enumeration degrees , and such that every enumeration degree is also or ; however neither nor is an Ahmad pair.
Enumeration reducibility is a positive reducibility between sets of natural numbers. It arises naturally as a notion of relative computability for partial functions and has applications in effective mathematics, especially in computable topology, in computable model theory and in group theory.
We associate an algebraic presentation of this reducibility as a degree structure. The structure of the enumeration degrees is a partial order with least upper bound and a jump operator (just like its more famous cousin, the structure of the Turing degrees). In this article we focus on structural properties of its local substructure – the degree structure of the enumeration degrees of the -sets, which can be defined also as those enumeration degrees below the degree . Here, is the enumeration degree of the complement of the halting problem . The -enumeration degrees can be viewed as the counterpart in enumeration reducibility of either the c.e. Turing degrees or the Turing degrees , i.e., the -Turing degrees. Both analogies are imperfect, but reasonable in certain respects. We refer the reader to [14] for more information on current trends in research on the enumeration degrees.
One of the common questions about a degree structure viewed as a partial order is that of the complexity of its first-order theory. For most degree structures commonly being considered, the theory turns out to be as complicated as possible: global structures like the Turing degrees or the enumeration degrees have theories that are computably isomorphic to the theory of second-order arithmetic, while local structures usually have theories that are equivalent to the theory of first-order arithmetic. We then wonder about the fragments of the first-order theory, identified by restricting sentences to a certain quantifier complexity. We find that decidability breaks down at level 3, i.e., the -fragment is not decidable. On the other hand the ∃- and often even the -fragment is decidable.
For the -enumeration degrees, the first of these questions has been completely settled: The full first-order theory was shown to be undecidable by Slaman and Woodin [13], and equivalent to full first-order arithmetic by Ganchev and Soskova [4].
As for the second question, the ∃-fragment is easily seen to be decidable, whereas Kent [5] showed the -fragment to be undecidable. The decidability of the -fragment remains open.
The decidability of the -fragment can be rephrased algebraically as (uniformly effectively) deciding the following
For any given finite partial orders and (for ), can any embedding of into the -enumeration degrees be extended to an embedding of for some (where i may depend on the particular embedding of )? (Without loss of generality, we will from now on assume that any finite partial order is bounded, i.e., has a least element 0 and a greatest element 1.)
Two major subproblems of Question 1.1 have been shown to be decidable:
Lempp, Slaman and Sorbi [8] showed that the above question is decidable for , i.e., given any finite partial orders , it is decidable whether any embedding of into the -enumeration degrees can be extended to an embedding of .
Lempp and Sorbi [10] showed that all finite lattices can be embedded, even preserving 0 and 1. (The lattice embeddings question can be seen as a disjunction of extending embeddings to certain one-point extensions of a finite lattice viewed as a partial order.)
As noted earlier, the -enumeration degrees are often compared to the c.e. Turing degrees. Both are dense structures with full first-order theories as complicated as the theory of first-order arithmetic. For the c.e. Turing degrees this was proved by Slaman and Woodin (unpublished, see Nies, Shore and Slaman [11]); for the c.e. Turing degrees we have that in addition the ∃-fragment is decidable, whereas Lempp, Nies and Slaman [7] showed the -fragment to be undecidable. However, the lattice embeddings problem for the c.e. Turing degrees remains one of the main open problems dating back to the 1960’s (see Lempp, Lerman and Solomon [6] for the most recent update), and thus the decidability of the -theory of the c.e. Turing degrees remains wide open as well.
An important algebraic difference between the c.e. Turing degrees and the -enumeration degrees was discovered by Ahmad in her Ph.D. thesis [1] (see Ahmad and Lachlan [2, Corollary 3.2]): There are incomparable -enumeration degrees and (called an “Ahmad pair”) such that any degree is also . (This makes “non-splitting”, i.e., join-irreducible, and thus cannot happen in the c.e. Turing degrees by the Sacks Splitting Theorem [12].) More interestingly even, Ahmad also showed (see Ahmad and Lachlan [2, Theorem 3.3]) that this phenomenon is not symmetric: For any two incomparable -enumeration degrees and , there is either a degree which is , or there is a degree which is .
In the language of Question 1.1, Ahmad’s results can be rephrased as stating that not every embedding of with incomparable and can be extended to an embedding of where and , but that every embedding of can be extended to an embedding of either or of where and .
In this paper, we prove two extensions of Ahmad’s results in different directions, thus adding to our toolbox toward our ultimate goal, deciding the -theory of the -enumeration degrees. Again in the language of Question 1.1, our first result can be rephrased as stating that every embedding of with incomparable , and can be extended to an embedding of where and or an embedding of where and (leaving the relationship between and , and between and , unspecified so as to not have too many cases); a similar formulation can be found for our second result.
We first present, in Section 2, a direct proof of Ahmad’s result that there is no symmetric Ahmad pair. (Currently, the only published proof in the literature is indirect and hard to modify.) In Section 3, we show that there is no Ahmad triple, i.e., there are no -degrees , and such that both and form an Ahmad pair. On the other hand, in Section 4, we also show that there is a weak Ahmad triple, i.e., there are pairwise incomparable -enumeration degrees , and such that every enumeration degree is also or ; however, neither nor forms an Ahmad pair. We should add here that Kent (personal communication around 2006) identified the existence of an Ahmad triple and of a “cupping Ahmad pair” (i.e., an Ahmad pair whose join is ) as the two main initial obstacles toward a decision procedure for the -theory of the -enumeration degrees.
It is worth pointing out that the first two results are specific to the -enumeration degrees. Lempp, Slaman, and Soskova [9] have shown that every finite distributive lattice L can be embedded as an interval of -enumeration degrees so that for every enumeration degree we have that or . Embedding the diamond in such a way shows that symmetric Ahmad pairs are possible in general.
A direct proof that there is no symmetric Ahmad pair
In this section, we will present a direct proof of the following
(Ahmad [1] (see Ahmad and Lachlan [2, Corollary 3.2])).
There is no symmetric Ahmad pair in the-enumeration degrees, i.e., there are no incomparable-degreesandsuch that every enumeration degreeis, and every enumeration degreeis.
To show that the degrees of a pair of sets and is not an Ahmad pair, we need to build a set such that . Cooper’s density proof [3] builds precisely such a set assuming that in addition . Under this additional assumption, we can build as follows: We satisfy two types of requirements. The first type ensures that for every e, we have by threatening to code into the e-th column of . The second type of requirement ensures that for every i, we have by threatening to make , which (assuming is computable) is a c.e. set. Here and . To make this idea work, the construction uses a good approximation to the set , i.e., a uniformly computable sequence of finite sets such that
for every n, there is a stage s such that ; and
for every n, there is a stage s such that for every , if then .
Stages at which are called good. The sets reducible to , namely, , , , and , are approximated with correct approximations – good approximations whose good stages include all good stages for the approximation of . If we restrict our attention to good stages for , then two sets with correct approximations are the same if and only the length of agreement between them measured at such stages is unbounded. So, if we enumerate elements into only by enumerating axioms of the form into , then we ensure that gains new elements only at good stages for , and this allows us to limit the activity of each requirement to a finite set.
If is not bounded by , then this construction fails: It can be that there are infinitely many good stages for that are bad for , causing us to falsely assume that a requirement of the first type requires attention again and again and forcing it to contribute an infinite set to . This, in turn, is in critical conflict with the second type of requirements, which depend on the assumption that each column in is finite. The problem we see should not surprise us, because Ahmad pairs do exist. Ahmad’s original proof of Theorem 2.1 uses the Gutteridge operator to show that if and form an Ahmad pair, then and all sets bounded by have eventually correct approximations with respect to the approximation to , and so we can build with using essentially the same construction as the one described above. The proof is ingenious, though difficult to modify. We give a direct construction, using the priority method and a tree of strategies. The main idea is to build the sets and in a more entangled way so that our failure to prove that allows us to switch off unwanted axioms enumerated into and avoid the problem described above.
Assume that and are incomparable -sets. (If and are comparable, then their enumeration degrees do not form an Ahmad pair by definition.)
We fix approximations for and so that is a good approximation to . So even though we cannot ensure that good stages for are good for or vice versa, we may at least ensure that there are infinitely many common good stages.
Requirements
The construction builds an enumeration operator , attempting to satisfy the following requirements for each enumeration operator and each enumeration operator :
If some requirement fails then we will construct an enumeration operator satisfying the following subrequirements for each of the enumeration operators and :
Clearly, satisfying either group of requirements, namely, all - and all -requirements, or, for some fixed , all - and all -requirements, will suffice since .
We will denote by (for ) whenever the operator is clear from the context.
Tree of strategies
Order each of the types of requirements and subrequirements in a priority of order type ω. We have four types of strategies: an -strategy α, an -strategy β, an -strategy γ, and an -strategy δ.
The root of the tree of strategies T is ∅, an -strategy working on the highest-priority -requirement. An -strategy has only one outcome and is immediately followed by an -strategy, working on the highest-priority -requirement.
An -strategy β has outcomes , , , and for all , ordered as follows:
For every , the nodes and are -strategies working on the highest-priority -requirement that is not assigned to any of β’s predecessors. The nodes and are -strategies working on the highest-priority -requirement that is not assigned to any of β’s predecessors.
An -strategy γ has outcomes , where is ordered by the standard ordering on ω. Each such immediate successor of this strategy is a main -strategy, working on the highest-priority -requirement that is not assigned to any of its predecessors.
Similarly, an -strategy δ has outcomes , where is ordered by the standard ordering on ω. Each such immediate successor of this strategy is an -strategy, working on the highest-priority -requirement (for the same as δ) that is not assigned to any of its predecessors.
Construction
At stage 0, all strategies are in initial state: All operators associated with these strategies are empty, all parameters are undefined. At stage , we build a path of length . The intention is that there will be a true path defined by
that correctly describes the outcomes of each strategy. The construction consists of substages t for , where we act for some strategy of length t depending on the current outcome of the strategy which acted at the previous substage starting at the root. When a strategy is activated at stage s, it first ensures that it is not missing any good stages by adjusting the approximations to and : If is the previous stage at which this strategy was active, then it replaces by for . We describe further actions of each strategy depending on its type below.
At the end of stage s, we initialize all strategies of lower priority than , i.e., strategies extending or to the right of the strategies which acted at stage s.
Each -strategy β and each -strategy δ works with the version of and determined by the longest -strategy , δ (we say that β and δ work for α); this version of is the set of -axioms enumerated by all the - and -strategies working for the same -strategy α.
We begin with the -strategies, as they are directly lifted from the density construction. So, let γ be an -strategy. The first time a strategy is visited after initialization, the strategy receives a unique number , the stage of first visit after initialization. To keep this assignment of stages injective, we interrupt the stage s construction if s is the first stage when γ is visited: We set , , and move on to stage . If is already defined, then we consider the length of the common initial segment of and up to s. For every number , if , we search for the axiom that has been valid the longest and enumerate each element of the form , where into the set via the axiom . The outcome of the strategy is , where k is the standard code of the finite set of all numbers for which γ has enumerated an axiom that looks valid at stage s. The only thing we assume about the coding of finite sets, in addition to its effective properties, is that implies .
We will be able to argue that if γ is on the true path, then γ enumerates only a finite set D into , as the sequence must be bounded. At sufficiently large stages in the approximation to , the outcome we select will always correspond to a superset of D. At stages that are also good (i.e., stages s such that ), we will be able to correctly identify the code of D as the correct outcome. In other words, the code of the set D will be γ’s true outcome.
An -strategy δ works similarly to the -strategy. It also receives a unique number , the stage of first visit after initialization, and interrupts the stage s construction if s is the first stage when δ is visited. Otherwise, we consider the length of the common initial segment of and up to s. For every number , if , we search for the axiom that has been valid the longest and enumerate each element of the form , where is in the set via the axiom . The outcome of the strategy is , where k is the standard code of the finite set of all numbers for which δ has enumerated an axiom that looks valid at stage s.
The -strategy does nothing, has only one outcome , and determines the version of and that all the - and -strategies working for the -strategy use.
The -strategy β attempts to construct an enumeration operator Ψ such that by enumerating axioms into and its version of .
At the first stage after initialization, the -strategy β is assigned the parameter . Note that we can assume that is larger than for any k such that a higher-priority -strategy λ (which can be either an - or an -strategy) has . Until its next initialization, β will only contribute numbers to the -th columns of and . To every element a, we assign the coding location targeted for . The coding locations that we associate with a given number a but are targeted for will change more dynamically during the construction. Initially, we assign as well.
At a stage , β does the following. It orders the elements of by age: For each , we define its age (at stage s) as follows.
Without loss of generality, we will assume that at most one element enters the approximation to or at a fixed stage s. (We can ensure this by artificially delaying the approximations if necessary.) And so, for every stage , there may be at most one element with . Furthermore, if , then is odd, and if , then is even. At stage s, we will say that b is older than a if .
If , then we exit this strategy with outcome (this is an outcome that has not been visited so far). Since is infinite, this will only be a temporary situation. Otherwise, we pick the oldest number a such that . Let . We must ensure that β’s effect on is computable, and so the strategy will dump into all elements of the form and assign new markers to all elements with . (Here, to dump an element m into means to enumerate the axiom into .) We have two cases depending on the parity of k.
Case 1: If k is even, i.e., if , then we will be able to argue that . The strategy selects outcome . While a maintains its age, we will design axioms for younger elements enumerated into by β so that their use includes a. Thus, if this is β’s true outcome, they will be invalid and hence β contributes finitely much to .
Case 2: If k is odd, i.e., if , then we would like to add an axiom for a into Ψ, but to do this we need some preparation. We will identify an axiom in and use it. Let be the previous stage when β considered k:
If some b with has at some stage , then, since b is older than a, we may assume that we have identified for b and that . (Otherwise, b would be our choice for the oldest disagreement.) We can therefore enumerate the axiom so that . The outcome is . If this is the true outcome, then we do not care what happens to as strategies below this outcome will be working with new versions of this set.
Otherwise, for every b with , we can associate a set , the use of the oldest valid axiom for in the set . We enumerate into the axiom
Next, we check whether . If , then we have evidence that this requirement may be satisfied by . Unfortunately, we have no evidence that the effect of β on is finite, so we use the marker . We will always only enumerate axioms of the form into , where is the use of a -axiom for . The case we are in suggests that .
If at some stage , then we can guarantee that under this outcome, β’s effect on is finite. This is because we include the use of a -axiom for in the use of every axiom we enumerate into for numbers with age larger than k. (This is true as long as a maintains its age.) We set the outcome to be .
Otherwise, at all stages , so we have evidence that . We end with outcome and let strategies below forget about this version of .
Finally, if at all stages (by the same axiom at all stages since the last visit), then let be the axiom that has been valid the longest. Enumerate into . We have eliminated a as a difference, and so we may proceed to pick the oldest difference once again.
Verification
We define the true path f in the tree of strategies as the leftmost path of strategies visited infinitely often. If , then we will say that λ has true outcome o. If s is a stage at which λ is visited, then we say that s is λ-true. We need to prove that f is well defined and strategies along it satisfy their requirements. We do so by showing the following properties of the construction by simultaneous induction.
The true path f is infinite, furthermore:
If β is an-strategy and, then:
There is a leftmost outcome o that β visits at infinitely many stages.
There are finitely many values of the parameter, and for each such value,is a computable set.
If, thenis satisfied, and for every value of, the setis finite.
If, thenis satisfied.
If γ is an-strategy and, then:
There is a leftmost outcome o that γ visits at infinitely many stages.
The setconsists of all numbers that γ contributes to.
The requirementis satisfied.
If δ is an-strategy and, then:
There is a leftmost outcome o that δ visits at infinitely many stages.
The setconsists of all numbers that γ contributes to.
The requirementis satisfied.
We will prove the statements above in turn, assuming that all statements are true for higher-priority strategies along the true path. We first note that -strategies along the true path have only one possible outcome, visited at every true stage, hence cannot cause f to be finite.
A. Let be an -strategy. It follows from the definition of the true path that β is visited at infinitely many stages and initialized finitely often. There is a stage at which β is first visited after its last initialization. At this stage, receives its final value, and by construction, we interrupt this stage so that no other strategy has the same parameter at any point during the construction. By construction, no strategy has so far enumerated any element into the -th column of or : Lower-priority strategies σ are initialized at stage , so their parameter (if defined) will have higher value than . Higher-priority strategies λ will not add elements to the -th column of or , either. To see this, note that they are either not visited at further stages, hence do not act any longer; they are -strategies with and hence enumerate elements into smaller columns of or ; or they are -strategies whose true outcome is extended by β and hence by B(2) and C(2), they will not enumerate any more valid axioms into either operator or . Thus β is the unique strategy that adds elements into the -th column of or . If is a previous value of the parameter , then our analysis shows that no strategy can add valid axioms for numbers in the t-th columns of and after stage .
Let be the enumeration operator constructed by β. By assumption, , hence . Let a be the oldest disagreement, where the age of the disagreement is defined as in the construction. This means that there is some stage such that at all stages , we have that if , then with a fixed marker . The age c of a remains constant, and at stages , the strategy β will not visit any outcome left of the c-outcomes (which depend on the parity of c), so the marker will remain fixed. Furthermore, the way β adjusts the approximation to and when visited ensures that there are infinitely many stages at which we visit β, and a is the oldest disagreement at stage t. At such stages, β will visit a c-outcome, and since there are finitely many c-outcomes (only one c-outcome if c is even, and three c-outcomes , , and if c is odd), there is a leftmost outcome visited at infinitely many stages, proving . Note that if β reaches Case 2.3 infinitely often, then β also ends in Case 2.2 infinitely often because if t is such that , but , where is the previous β-true stage, then our convention ensures that . All numbers greater than in the -th column of will be dumped into , hence the -th column of is cofinite, proving .
If , then the age of a after stage is , where k is the stage such that at all , we have that via the same axiom , say. As we argued above, is β’s true outcome. We prove that : That is clear, as by construction, any axiom that β enumerates into for contains a in its use, and as we already argued, no other strategy enumerates valid axioms for . On the other hand, β enumerated the valid axiom into Ψ because it saw that , and since , it follows that . Up until stage , there are only finitely many axioms enumerated into by β. After stage , any axiom enumerated by β into will include a in its use because the age of a remains constant. It follows that all such axioms are invalid, and so β contributes a finite set to .
Suppose . Then , and we have several cases, depending on the leftmost outcome visited infinitely often. If this is , then infinitely often after stage , we visit β, and it stops at Case 2.1 of the construction, because some b with has at some stage t since we last considered a. There are finitely many such b, and hence the described scenario happens infinitely often with some fixed such b. As pointed out in the construction, since b is older than a, we know that at such stages via the same axiom , and so the construction ensures that using this axiom. It follows that .
Otherwise, there is a stage such that at all β-true stages at which a is the oldest disagreement, Case 2.1 does not apply. This means that for every older b, there is a fixed valid axiom . This means that the axiom that we enumerate into for is valid, and so . On the other hand, since infinitely often we are in Case 2.2, , and so is satisfied.
If β’s true outcome is , then . In this case, we already know that is satisfied. After stage , any axiom enumerated by β into will include some in its use, where . It follows that all such axioms are invalid, and so β contributes a finite set to . This ensures that (3) is true.
Otherwise, there is a stage after which Case 2.2.a does not apply. The true outcome is , and at all stages by the same axiom. It follows that . To complete the proof, we will show that . Any -axiom enumerated for has the form . Such an axiom can only be enumerated after the axiom is enumerated into Ψ. Since , it follows that . We conclude that is satisfied, proving .
B. Let be an -strategy. It follows from the definition of the true path that γ is visited at infinitely many stages and initialized finitely often. There is a first stage at which γ is visited after its last initialization. This is the stage at which receives its final value, and by construction, we interrupt this stage so that no other strategy has the same parameter at any point during the construction. Lower-priority strategies σ have . Higher-priority strategies are the only ones that can enumerate elements into , so by induction, is a computable set. If s is a good stage in the approximation to , then and . Suppose that is unbounded. Then we can argue that : If , then pick a good stage s at which and . It follows that . Similarly, if , then we can pick a good stage s at which and . It follows that .
Furthermore, if is unbounded then we can also argue that . One inclusion follows from the fact that . For the reverse inclusion, fix . Let be the oldest valid axiom. (Note that the age of this axiom depends only on .) Pick a good stage that is greater than the age of this axiom and at which . At this stage, we enumerate all , where , into the set via the axiom . Since s is good, these are valid axioms, and hence . It follows that , contradicting the fact that is not c.e. (otherwise it would be comparable with ).
Thus is bounded by some number , say, at all good stages in the construction. At good stages, the strategy γ enumerates axioms only in response to finitely many n. For each such n, we know by the fact that we are looking at a good stage that . Eventually, the oldest valid axiom will emerge, and so γ will keep selecting the same axiom for this element, and thus ultimately γ will enumerate only finitely many elements into , and all these elements will be enumerated at good stages. Let be the set of these elements. Let be a stage such that at all , we have that . At all γ-true stages , the strategy γ will have outcome , where . By our choice of coding, we have that . By the adjustment that γ makes to the approximation of , we know that γ is visited at infinitely many good stages for the approximation to . At such stages, γ will have outcome . This proves (1) and (2).
To see that the requirement is satisfied, we prove that there is some element such that . Assume that this is not the case. Pick a stage s such that all elements that are in are in and s is good. There are infinitely many such stages, and we visit γ at such stages. At such a γ-true stage t, we have that , contradicting our choice of .
C. The case where is an -strategy is proved similarly to Case B. □
Either all requirementsandare satisfied, or there is some requirementsuch that all requirementsandare satisfied.
If there are infinitely many -strategies along the true path f, then by the construction of the tree, it follows that there are infinitely many -requirements assigned to nodes on the true path, as only such strategies have immediate successors that are -strategies. Thus all -requirements are assigned to nodes on the true path and hence by Lemma 2.2 are satisfied. Consider any -strategy . Let be the next -strategy along the true path. By the construction of the tree, γ’s immediate predecessor is an -strategy β with true outcome or for some k. It follows from Lemma 2.2 that is satisfied, thus all requirements are satisfied.
If there are finitely many -strategies along f, then fix the longest such α. Every immediate successor of α along the true path is either an -strategy with true outcome or or an -strategy. Hence there are infinitely many of each, and by Lemma 2.2, they are all successful. By the design of the tree, it follows that all requirements and are satisfied. □
No Ahmad triple
In this section, we extend the ideas introduced in the previous section to prove our main result:
There is no Ahmad triple in the-enumeration degrees, i.e., there are no-degrees,, andsuch thatbut every enumeration degreeis, and such thatbut every enumeration degreeis.
Requirements
Suppose , and are -sets. The construction builds an enumeration operator , attempting to satisfy the following requirements for each of the enumeration operators and :
If some -requirement fails, then we will construct an enumeration operator satisfying the following subrequirements for each of the enumeration operators and :
If some -requirement fails, then we will construct an enumeration operator satisfying the following subsubrequirements for each of the enumeration operators and :
We will denote by , by , and by whenever the operator is clear from the context.
Overview
We first give a high-level overview of how the overall construction works, without going into the specifics of the priority tree layout and the arrangement of different outcomes. At each node α of the priority tree, there will be an active version of and (where is, of course, maintained globally). Each version of and is built in some cone; is built in a cone with an -requirement at the top of the cone, while is built in a cone with an -requirement at the top. These cones are nested in the sense that each node where a particular set is active is also a node where a set is active; but a cone for can contain many different -cones. The setup here is typical of a non-uniform argument; the situation in our construction is perhaps slightly more complicated than a typical non-uniform argument due to having to keep track of three levels of non-uniformity. However, the overall spirit is the same: The set is maintained globally, and there will only be one version of it, i.e., every node in the tree is in the one -cone. Inside each -cone, we will have the active sets and . Inside this -cone, we actively try and satisfy the - and the -strategies, while leveraging on the assumption that the - and -strategies at the top of the - and -cones are unsuccessful. While this assumption is not violated, we stay in the -cone and only consider the - and the -strategies.
If we ever detect that the -strategy is successful, we will exit the -cone and immediately place the next -strategy before starting a new -cone below it. Similarly, if we ever detect that the -strategy is successful, we will end the current - and -cones and immediately place the next -strategy before starting a new - and a new -cone below. In this way, depending on how many different - and -cones the true path of the construction crosses, we will be able to argue that along the true path, either all - and -requirements are satisfied, or all - and -requirements are satisfied in some final -cone, or all - and -requirements are satisfied in some final -cone.
It remains to describe how a node α assigned to a requirement is able to either detect the success of its parent -strategy, or the success of its grandparent -strategy, or be able to leverage on the failure of both to ensure the success of its own requirement. By our experience with the -strategies thus far, it is important to note that α must not be too liberal with enumerating true axioms into , and ; if we do not exit the current -cone, we must make sure that α’s contribution to is finite or at least computable. If we do not exit the current -cone, then α’s contribution to must be finite, while α’s contribution to must be finite regardless of the true outcome. (If we do not ensure this, then along the true path, when we have the next , - or -node, we will not be able to run the respective basic -strategy.)
With the foregoing comment in mind, consider a node α assigned to a requirement . The obvious strategy is to associate each number a (targeted for ) with a number (targeted for ) and try to maintain that iff . We build a reduction which will emulate . Since cannot possibly hold, we must be able to find some where , and hence will be satisfied. This naive strategy will work to satisfy in isolation; unfortunately, we may not be able to guarantee that the effect on is finite; as discussed above, if we satisfy , we stay in the -cone, and we will need the strategy to enumerate only finitely many true axioms for . Notice that if there is some , then this condition can be ensured, since the strategy for α will only need to enumerate further axioms putting some into if the length of agreement goes up; hence all newer axioms in will include the number a. However, if the disagreement is witnessed by some , then there is no way to prevent infinitely many elements from being put into by the strategy. Note that the same problem applies even if we try and diagonalize and , or and . The solution to this problem is to ensure that under the problematic outcome where , all future axioms enumerated by α putting some into must also include the use of certain elements in and . If we entangle the axioms for newer in this way correctly, then we will be able to argue that in the end, either we will be able to diagonalize and , or we can diagonalize and , or else we can force all newer -axioms enumerated by α to become invalid.
To arrange for this entangling to work properly, we will need another setup. Under the assumption that and hold, we will need to start a backup-strategy, which we will name β. Each time β sees further proof that and hold, it will extend the reduction that it builds. The basic working of β is that it associates each number b targeted for with a number targeted for and a number targeted for . (For technical reasons, in the construction, the association will be fixed while the association will be dynamic, but we do not encumber ourselves with these details at this time.) The plan will be to let emulate , so that the necessary disagreement between and must produce a corresponding disagreement between and . Fix the element b so that we have either
and and , or
and and .
Since b will eventually be in one of the -sets involved above, almost every axiom enumerated by the main strategy α putting some into will be able to observe and use the information provided by this number b.
Consider a future stage s when the strategy α is deciding whether or not to enumerate an axiom putting some into . By our assumption on b, we must see either or . If the strategy for α sees but , then it does not need to proceed with its strategy and does not enumerate any axiom for into since it currently looks like . If, however, α sees but , then it also does not need to enumerate an axiom for into . This is because either , in which case both and , or they are all three out of the respective sets, and so we must currently see or . Therefore, the only time when α enumerates into is when it sees both and , in which case it will include the use of the latter two in the axiom for in .
Now finally assume that β is along the true path of the construction. If the first case (i) above applies to b, then almost every axiom enumerated by the strategy for α will be invalid, since they will include the use of , which was exactly what we wanted to achieve. If the second case (ii) applies and is not eventually in , then again almost every axiom enumerated by the strategy for α will be invalid, since they will include the use of . Finally, assume that the second case (ii) applies and . Then in this case, it may be possible that the strategy for α enumerates infinitely many elements into , but then we would have , and we will exit the current -cone. In this case, the current set will be irrelevant anyway.
Tree of strategies
Order each of the types of requirements, subrequirements and subsubrequirements in a priority of order type ω such that each -requirement precedes all the -subrequirements, and each -subrequirement precedes all the -subsubrequirements.
The root of the tree of strategies T is ∅, an -strategy working on the highest-priority -requirement. An -strategy has only one outcome and is immediately followed by an -strategy, working on the highest-priority -requirement. An -strategy has only one outcome and is immediately followed by an -strategy, working on the highest priority -requirement.
An -strategy α has outcomes , , , , and for all , ordered as follows:
For every , the nodes are -strategies working on the highest-priority -requirement that is not assigned to any of α’s predecessors. The nodes and are -strategies working on the highest priority -requirement that is not assigned to any of α’s predecessors. The nodes are -strategies working on the highest-priority -requirement that is not assigned to any of α’s predecessors. Finally, the nodes are backup -strategies with their own outcomes (defined below).
An -strategy γ has outcomes , where ordered by the standard ordering on ω. Each such immediate successor of this strategy is a main -strategy, working on the highest-priority -requirement that is not assigned to any of its predecessors. The outcomes and immediate successors of the - and -strategies are defined analogously ( and , respectively).
Finally, a backup -strategy β has outcomes , and for all , ordered as follows:
For every , the nodes and are -strategies working on the highest-priority -requirement that is not assigned to any of β’s predecessors. The nodes are -strategies working on the highest-priority -requirement that is not assigned to any of β’s predecessors.
Construction
This construction has many properties that are similar to the one in Section 2. At stage 0, all strategies are in initial state: All operators associated with these strategies are empty, and all parameters are undefined. At stage , we build a path of length with the intention of building a true path defined by
When a strategy is activated at stage s, it first adjusts the approximations to , , and : If is the previous stage at which this strategy was active, then it replaces by for . At the end of stage s, we initialize all strategies of lower priority than , i.e., strategies extending or to the right of the strategies which acted at stage s.
Each strategy β works with the version of and determined by the longest -strategy (we say that β works for α); this version of is the set of -axioms enumerated by all the -strategies and -strategies working for the same -strategy. Similarly, each strategy β works with the version of and determined by the longest -strategy ; this version of is the set of -axioms enumerated by all the backup -strategies and -strategies working for the same -strategy.
, ,
The -strategies work precisely as in the previous construction. Let γ be such a strategy. The first time γ is visited after initialization, it receives a unique number , the stage of first visit after initialization, and stops the construction of for this stage. If is already defined, then we consider the length of the common initial segment up to s of the sets and that are named in the corresponding requirement: For , these are and ; for , these are and ; and for , these are and . For every number , if , then we search for the axiom that has been valid the longest, and we enumerate each element of the form , where , into the set via the axiom . Note that this action might enumerate some number into where is already in via an axiom enumerated by a different node.
The outcome of the strategy is , where k is the standard code of the finite set of all numbers for which γ has enumerated an axiom that looks valid at stage s. As before, we assume that implies .
,
The -strategy and the -strategy do nothing, have only one outcome , and determine the version of and , or and , respectively, that substrategies work with.
The -strategy α attempts to construct an enumeration operator such that by enumerating axioms into . (It will not enumerate axioms into either or , only its backup strategies will.)
At the first stage after initialization, the -strategy α is assigned the parameter . We can assume that is larger than for any k such that a higher-priority -strategy λ has . Until its next initialization, α will only contribute numbers to the -th columns of . To every element a, we assign the coding location targeted for .
At stage , α does the following. It orders the elements of by age:
Once again, we assume the age is defined injectively, i.e., for every stage , there may be at most one element with . Also, if , then is odd, and if , then is even.
If , then we exit this strategy with outcome . Otherwise, we pick the oldest number a such that . Let . We have two cases depending on the parity of k.
Case 1: If k is even, i.e., if , then we will be able to argue that . The strategy selects outcome . While a maintains its age, we will design axioms for younger elements enumerated into by α so that their use includes a. Thus if this is α’s true outcome, they will be invalid, and hence α contributes finitely much to . Under this outcome, we do not care about .
Case 2: If k is odd, i.e., if , then we would like to add an axiom for a into . We will follow a similar scheme as in the previous construction: We will add an axiom for into , wait until shows up in , and use the (currently) valid axiom to define an axiom for a in . We entangle the axiom for with axioms from both and . First, we consider all such that the age of z in (i.e., the least such that for all ) is less than k. Let be the previous stage when α considered k:
If some such is not in via the same axiom for all stages , then we have evidence that , and so we exit with outcome . If b is younger than a, then α will always include the use of an axiom for z being in in the use of the axiom for being in , so if this is the true outcome, then is satisfied and α’s effect on is finitary.
Otherwise, for every that is older than a, we can associate a set , the use of the oldest valid axiom for z being in . Next, we consider every backup strategy β (an immediate successor of α) that is not in initial state, every number such that the age of (i.e., the least such that at all , we have via the same axiom) is less than k, and for each such , the coding locations that are associated with b by β. (Note that we do not restrict β to the ones that extend an older outcome than k. There will only be finitely many such backup strategies being considered due to the restriction on the age of .)
If for some such , there is an such that at some stage , then we have two cases:
If at some stage , then we have evidence that . We exit with outcome and argue that if this is the true outcome, then is satisfied and α enumerates finitely many valid axioms into because they all must include the use of a -axiom for all such .
If at all , then the outcome is . We have evidence that as it was either dumped there (i.e., we enumerated the axiom into ) or its axiom has use . If this is the true outcome, then we aim to show that is satisfied by . In this case, we do not care about α’s effect on even though that effect will be finitary as we argued in the previous case.
Otherwise, for every older and each associated with b, we can associate a set , the use of the oldest valid axiom for in the set . We enumerate into the axiom for whose use consists of
all b such that (note that this includes a),
all for older , and
all where β is a substrategy of α not in initial state (at the end of this stage) with older , and corresponding .
Next, we check whether . If at some stage , then we have evidence that may be satisfied by . Unfortunately, we have no evidence that the effect of α on is finite. So we activate the backup strategy below outcome . The backup strategy will either turn off future axioms enumerated by α or ensure that is satisfied.
Finally, if (by the same axiom at all stages since the last visit), then let be the axiom that has been valid longest. Enumerate . We have now eliminated a as a difference, and so we will pick the oldest difference once again, starting over at the current substage. (This can happen at most finitely often at any substage.)
Notice that the set is only relevant under the outcomes and of α (corresponding to items (1) and (2a) above, respectively). Since α itself does not add axioms to , but rather, they are only added by the backup strategies, whenever some outcome of α is played, the effect on each column of will be finite if α has true outcome or . This is also the reason we have multiple backup strategies for α.
Backup
The backup -strategy β works with its immediate predecessor α and attempts to construct an enumeration operator such that by enumerating axioms into and its version of .
Just like α, the strategy β is assigned the parameter at the first stage after initialization. We can assume that is larger than for any k such that a higher priority -strategy λ has . The strategy β associates to every element b the coding location targeted for . To certain elements b, it will also dynamically assign a coding location targeted for .
At a stage , β orders the elements of by age so that if , then is odd, and if , then is even.
If , then we exit this strategy with outcome . Otherwise, we pick the oldest number b such that . If there is no marker associated with b, then we choose to be the least number of the form which has not been chosen as a marker. We also enumerate the axiom into .
Let . We must ensure that β’s effect on is computable and so the strategy will dump into all markers which are currently associated with any number with . Furthermore, to each such , we associate a new marker , which is the least number of the form which has not been chosen as a marker. We also enumerate the axiom into .
We will not ensure that β’s effect on is finitary or computable because if β is on the true path, then either or will be satisfied and will not be relevant to strategies extending β.
We now have two cases depending on the parity of l.
Case 1: If l is even, i.e., if , then unlike for α, we cannot simply take the easy win , because we still have not guaranteed that α’s effect on is finitary. For that reason, we will instead consider the marker . We will argue that is evidence that is not an element of , and so we check whether . Let be the previous stage when α considered l:
If is not in for some (via the same axiom), then we will be able to argue that if this is the true outcome, then α enumerates only finitely many axioms into as all but finitely many of them will include an axiom for in . In this case, is satisfied, and α’s action on is finitary. So we take outcome .
Otherwise, we have evidence that and so if this is the true outcome, then is satisfied and we take the outcome . Below this outcome, we do not care anymore what happens to .
Case 2: If l is odd, i.e., if , then we enumerate the axiom into the operator .
If , then, if this is the true outcome, all but finitely many axioms that α enumerates will contain the use of an axiom for being in which is invalid. It follows that once again, is satisfied and α’s action on is finitary. We exit with outcome .
Finally, if (by the same axiom at all stages since the last visit), then let be the axiom that has been valid longest. Enumerate into . We have now eliminated b as a difference, and so we will pick the oldest difference once again, starting over at the current substage. (This can happen at most finitely often at any substage.)
Verification
We define the true path f in the tree of strategies as the leftmost path of strategies visited infinitely often. If , then we will say that λ has true outcome o. If s is a stage at which λ is visited, we say that s is λ-true. We need to prove that f is well-defined and strategies along it satisfy their requirements. We do so by showing the following properties of the construction by simultaneous induction.
The true path f is infinite, furthermore:
If α is an-strategy and, then:
There are finitely many values of the parameter.
There is a leftmost outcome o that α visits at infinitely many stages.
If, thenis satisfied, and for every value of, the setis finite.
If, thenis satisfied, and for every value of, the setis finite.
If, thenis satisfied.
If, thenis satisfied.
If β is a backup strategy for an-strategy α and, then:
There are finitely many values of the parameter.
There is a leftmost outcome o that β visits at infinitely many stages.
For every value of, the setis computable.
If, thenis satisfied, and for every value of, the setis finite.
If, thenis satisfied.
Ifis an-,-, or-strategy, respectively, then:
There is a leftmost outcome o that γ visits at infinitely many stages.
The setconsists of all numbers that γ contributes to,, or, respectively.
The requirement,, or, respectively, is satisfied.
A. Since , there is a least stage at which α is visited after its final initialization. At this stage, receives its final value, proving (1). By construction, we interrupt this stage so that no other strategy has the same parameter at any point during the construction. We claim that α is the only strategy that adds elements to . By construction, no strategy has enumerated any element into so far. Lower-priority strategies σ are initialized at stage , so any future values of will be greater than . Once that occurs, σ cannot add elements to . Higher-priority strategies will not add elements to , either. To see this, note that any strategy λ of higher priority that potentially adds elements into after stage is either an -strategy with , or an -strategy which will not enumerate any valid -axioms for numbers into by inductive hypothesis and our choice of . This proves our claim. Note that if is a previous value of the parameter , then our analysis shows that no strategy can add elements into after stage . It follows that is finite.
Let be the enumeration operator constructed by α. By assumption, , hence . Let a be the oldest disagreement between and . This means that there is some stage such that at all stages , we have that stabilizes, and if , then . Furthermore, the way α adjusts the approximation to and when visited ensures that there are infinitely many stages at which we visit α and a is the oldest disagreement at stage t. At such stages, α will visit an -outcome, and since there are finitely many -outcomes, there is a leftmost outcome o visited at infinitely many stages, proving (2).
To prove (3), suppose that o is . In order to show that is satisfied, we will show that . Since o is , we have for infinitely many stages t, so . We argued above that only α can enumerate -axioms for . By construction, the use of any such axiom contains a. So . As for , note that implies that . For any -axiom for a, there is a corresponding -axiom for with the same use. The latter axiom witnesses that as desired.
To show that is finite, it suffices (by our reasoning above) to show that there is a stage after which no -axiom enumerated by α is valid. This holds because any -axiom enumerated by α when the current outcome is o or to the right of o must contain a in its use, yet . This completes the proof of (3).
To prove (4), first suppose that o is . In order to show that is satisfied, we will show that . Since o is , there are infinitely many stages s such that there is some with age less than and , where . (Recall that is the last stage before s at which α considered .) There are only finitely many z which ever have age less than , so the scenario described happens infinitely often with some fixed z. It follows that as desired.
To show that is finite, note that for all but finitely many stages at which we visit α, the age of z in is smaller than the age of the oldest disagreement between and . At such stages, if α enumerates a -axiom, its use contains the use of a -axiom for z being in . Since , it follows that α only enumerates finitely many valid -axioms. Therefore, is finite (as α is the only strategy which adds elements into ). This completes the analysis if o is .
Next suppose o is . In this case, we will show that . By assumption on o (and the fact that there are only finitely many backup strategies β and numbers b such that the age of in is ever less than ), there are a backup strategy β, a number b, and a number such that at infinitely many stages s at which we visit α, we have that
the age of in is less than ;
m is one of the markers that β associates with b; and
for some .
It follows that and . Since o is , we have . We will show that . The only -axiom enumerated by β for has use , so it is not valid. Furthermore, one can show that β is the only strategy that adds elements into . The proof is similar to that for α and : Note that while β may not be along the true path, its immediate predecessor α is along the true path and therefore so are all of its predecessors. We have shown that .
To show that is finite, note that for all but finitely many stages when we visit α, the age of in is smaller than the age of the oldest disagreement between and . At such stages, if α enumerates a -axiom, its use contains the use of a -axiom for m. Since , it follows that α only enumerates finitely many valid -axioms. Therefore, is finite (as α is the only strategy which adds elements into ). This completes the proof of (4).
To prove (5), suppose that o is . To show that is satisfied, we will show that . Fix β, b and m, following the analysis in the case where o is . As before, we have . However, since o is , we have . Since we enumerated the -axiom when associating m with b, it follows that . So .
To prove (6), suppose o is . We have . To show that , consider a stage large enough such that for all ,
if , then ;
if the age of z in is less than , then , and the use of the oldest valid -axiom for z has stabilized; and
if β is a backup strategy for α and the age of (the current value of) in is less than , then
has stabilized and lies in ;
each lies in ; and
the use for the oldest valid -axiom for each has stabilized.
Such exists because o is . At any stage at which we visit α, we would enumerate a valid -axiom for . We conclude that as desired.
B. Since , there is a least stage at which β is visited after its final initialization. At this stage, receives its final value, proving (1). By construction, we interrupt this stage so that no other strategy has the same parameter at any point during the construction. One can show that β is the only strategy that adds elements into , and if t is a previous value of , then no strategy adds elements into after stage . It follows that is computable for every previous value t of .
Let be the enumeration operator constructed by β. By assumption, , hence . Let b be the oldest disagreement between and . Following similar reasoning as that for α, there is a leftmost outcome o of the form , or which is visited at infinitely many stages, proving (2).
To prove (3), we begin by showing that stabilizes. Once and have stabilized, the only way that changes is if some with is the oldest disagreement between and . At such a stage , the current outcome of β would be to the left of o. This only occurs finitely often, proving that stabilizes. Then all numbers greater than in the -th column of will eventually be dumped into , implying that is cofinite. As for older values of , we mentioned above that the corresponding columns of are computable.
To prove (4), first note that by A(6), is satisfied. It remains to show that for every value of , the set is finite. As reasoned above, it suffices to show that α only enumerates valid -axioms for finitely many elements in , where has stabilized. The proof differs depending on whether o is or .
Suppose o is . We have and . By β’s construction of , we have (via an axiom with the same use as a -axiom for b). Let t be the age of in . Consider any stage s such that , , the age of in , and all have stabilized. Suppose α enumerates a -axiom for some at stage s. Then is the oldest disagreement between and . Furthermore, if , then the use of the -axiom enumerated by α contains the use of a -axiom for , rendering it invalid (because ). But there are only finitely many for which there is some s such that , so α can only enumerate valid -axioms for finitely many as desired.
If o is , the analysis proceeds similarly but with instead of . In this case, we have that and . By β’s construction of , we have via . Let t be the age of in . Consider any stage s such that , and the age of in all have stabilized. Suppose α enumerates a -axiom for some at stage s. Then is the oldest disagreement between and . Furthermore, if , then the use of the -axiom enumerated by α contains the use of a -axiom for , rendering it invalid (because ). But there are only finitely many for which there is some s such that , so α can only enumerate valid -axioms for finitely many as desired. This completes the proof of (4).
To prove (5), suppose o is . We will show that . Since o is , we have . To show that , note first that the only -axiom enumerated by β for has use , so it is not valid. Furthermore, as mentioned above, β is the only strategy that adds elements into , so . This completes the proof of (5).
C. We will prove (1)–(3) in the case where γ is an -strategy. Then we will sketch how to modify the proof to address the - and -strategies.
Since , there is a least stage at which γ is visited after its final initialization. At this stage, receives its final value, proving (1). By construction, we interrupt this stage so that no other strategy has the same parameter at any point during the construction.
Consider the sequence of good stages s, i.e., stages at which . This sequence is infinite because is a good approximation to . We claim that the length of agreement between and is bounded on this sequence. Towards a contradiction, suppose not. We begin by showing that : First, if , then pick a good stage s such that and . Then . Conversely, if , then pick a good stage s such that and . Then as desired.
Next, we shall show that . The forward inclusion is trivial. To prove the backwards inclusion, consider . Let be the oldest -axiom putting n into . Pick a good stage such that is permanently in and . When we first visit γ at some stage , we enumerate a -axiom for each . By the way that γ adjusts the approximation to , we have . Therefore, , implying that . This proves the reverse inclusion.
By inductive hypotheses B(3) and C(2), is computable, because the only strategies that contribute elements to after stage are backup strategies or -strategies . The equality proved in the previous paragraph then implies that , and hence , is c.e., contradicting our assumption on . Therefore is bounded on the sequence of good stages s. Fix a bound . Using this, we will prove (1) and (2). First note that γ can only contribute numbers to at good stages, because every -axiom enumerated by γ at stage s has use . This means that only numbers can cause γ to enumerate valid -axioms. If , then at good stages, so n will not cause γ to enumerate any valid -axioms. As for , the oldest valid -axiom for n will appear to be the oldest valid axiom at all sufficiently large good stages, because we are working with a good approximation to . Therefore, at all sufficiently large good stages, γ does not enumerate any valid -axioms not already in . This proves that γ enumerates only finitely many elements into . Let be the set of these elements. To prove (1) and (2), it remains to show that is the leftmost outcome that γ visits at infinitely many stages. Consider a stage s after which D lies permanently in . At any γ-true stage , γ’s current outcome satisfies . This implies that . By the adjustment that γ makes to the approximation of , we know that γ is visited at infinitely many good stages. At all such stages (after stage s), γ will have outcome . This proves (1) and (2).
Finally, to prove (3), we show that there is such that . Assume that this is not the case. Fix a stage s such that for all and each in , we have . Consider any good stage at which we visit γ. If , then we must have . So , contradicting our choice of .
This proves (1)–(3) in the case where γ is an -strategy. As for the - and -strategies, most of the above proof goes through if we simply replace , , and by the appropriate sets or operators. The only nontrivial change is in proving that is computable (for ) or is computable (for ), respectively. To prove the former, apply inductive hypotheses A(3), A(4), B(4), and C(2). Note that A(5) and B(5) are not relevant because any strategy above γ with such a true outcome works with a different version of . To prove the latter, apply inductive hypothesis C(2). Any backup strategy above γ works with a different version of , so we are not concerned with it. □
One of the following holds:
All requirementsandare satisfied.
There is some operatorsuch that all requirementsandare satisfied.
There are operatorsandsuch that all requirementsandare satisfied.
First, suppose there are infinitely many -strategies along the true path f. By construction of the tree of strategies, there must be infinitely many -strategies along f as well. Thus all -strategies are assigned to nodes on the true path and hence are satisfied. To show that is satisfied, fix an -strategy . Let γ be the next -strategy along f. By construction of the tree of strategies, γ’s immediate predecessor is either an -strategy with true outcome of the form , or a backup -strategy with true outcome of the form . In both cases, the previous lemma shows that is satisfied.
Second, if there are only finitely many -strategies along f, fix and such that α is an -strategy and no immediate successor of α is an -strategy. If there are infinitely many -strategies along f, we claim that all requirements and are satisfied. By construction of the tree of strategies, there must be infinitely many -strategies along f. Thus all -strategies are assigned to nodes on the true path and hence are satisfied. To show that is satisfied, fix an -strategy extending α. Let δ be the next -strategy along f. By construction of the tree of strategies, δ’s immediate predecessor is either an -strategy with true outcome of the form , or a backup -strategy with true outcome of the form or . In each case, the previous lemma shows that is satisfied. This proves our claim.
Finally, suppose there are only finitely many -strategies along f. Fix extending α and such that is an -strategy and no immediate successor of is an -strategy. (Such exists because α’s only immediate successor, which must lie along f, is an -strategy.) Then no immediate successor of α along f can be a backup -strategy, so every immediate successor of along f is either an -strategy with true outcome of the form or , or an -strategy. By the previous lemma and the design of the tree, all requirements and are satisfied. □
A weak Ahmad triple
In the previous section, we saw that an Ahmad triple is not possible in the -enumeration degrees. In this section, we show a positive result, the existence of what we call a weak Ahmad triple.
There are pairwise incomparable-enumeration degrees,, andsuch that
there are-degreesandwith; and
for every-degree, we have that eitheror.
We call such a triple of degrees,, anda weak Ahmad triple.
Requirements
We will construct -sets , , , and satisfying the following list of requirements for every natural number e:
Then , , and clearly satisfy clauses (1) and (2) of the theorem: Indeed, if , then Z will take the role of X for some requirement and the role of Y for some requirement . If either requirement is satisfied by the first disjunct, then we know that or , respectively. Otherwise, we have that both and , and so . Finally, by the definition of the degrees and by density, our requirements imply that , and are pairwise incomparable: Clearly, for each by (1). Similarly, for some contradicts (1). If for some , then fix x with , so by (2), and in particular , contradicting the last sentence.
The reader might recognize the -requirements to be very similar to the requirements for making an Ahmad pair. Indeed, we can think of as being the strategy making an Ahmad pair “relative” to , while is the strategy making an Ahmad pair “relative” to . In fact, as we will see, the addition of to the oracle in will not pose additional difficulties, and a similar Ahmad pair strategy can be used.
Naive description of the strategies
We start by briefly outlining naive strategies to satisfy each requirement and then discuss how to modify them in order to avoid conflicts between them. The construction shares many similarities with the usual construction of an Ahmad pair on a tree. We will use the usual setup of a tree of strategies ordered by priority.
An -requirement , say, is satisfied using a standard Friedberg–Muchnik strategy α: It picks a witness and enumerates it into . It waits to see if this witness will ever enter the set . It wins if this never happens, provided that remains in . If , we say that is realized. In that case, α can win by extracting from and ensuring that will remain in by imposing a finite restraint on the sets and .
Of course, this puts -strategies and -strategies in conflict, and so already we see the need for a priority ordering between strategies. This is an easy obstacle to deal with. The complexity of our construction will only be revealed once we think about the -strategies as well.
Consider an -requirement , say, and its strategy β. Its initial goal is to build the operator so that , where . When activated at stage s, for every natural number , it checks whether , and if so, it enumerates a new axiom into , where D contains a fresh number that we enumerate into . If, on the other hand, , then the strategy invalidates all valid axioms for n by extracting from the corresponding marker . A new fresh value is then picked for to use in the next Γ-axiom. (This allows us to keep our sets .)
The - and -strategies do not interfere with each other: They modify the sets and , respectively; however, -strategies do not involve the set , and -strategies do not involve the set . -strategies do not interfere with higher priority -strategies, as our priority tree will ensure that whenever an -strategy imposes a restraint, all lower-priority strategies are initialized and choose all of their parameters (specifically, numbers or witnesses they might later on like to extract from some set) as fresh numbers, larger than any number seen in the construction so far. An -strategy does not directly interfere with -strategies of higher priority: Its extraction of the witness z from may cause some x to leave X. However, our design of the axioms that are enumerated into will guarantee in that case that x will also leave , and hence the -strategy will not even have to act in response.
The situation is quite different, unfortunately, when one considers how the extraction of from by an -strategy α affects a higher-priority -strategy β: In that case as well, some y may be forced out of through this extraction, and so β will react by extracting from . This action, however, might directly interfere with the restraint that α is trying to impose on in order to keep . In order to deal with this problem, we will need to modify our strategies.
An -strategy working below a single -strategy
For simplicity, we describe first the actions and outcomes of an -strategy α with one -strategy β of higher priority working above it. In the formal construction below, we will deal with the more general case.
The -strategy α will start by defining a threshold to be larger than any number mentioned so far. This threshold is meant to allow the -strategy β enough room to satisfy its requirement. If changes its value on a number , then α will be restarted. So α can assume that does not change below and hence does not change on any for . From this point on, α (temporarily) takes over control of the operator : It defines a killing point as a fresh number and enumerates it into . It will require that the strategy β adds this killing point to the axiom that it enumerates into for any . Whenever α is restarted, all parameters that α had at the previous stage will be canceled except for the threshold and the killing point . The killing point is extracted from (thereby invalidating all axioms that were enumerated into for any element ). Finally, a new value for will be set – a fresh number, not seen in the construction so far, and this fresh number is added to . Note that (assuming changes finitely often, which is something we will prove in Lemma 4.4), this restart can happen at most finitely often.
The strategy α has three outcomes, . Once it has completed its initial setup (defining thresholds and killing points), the strategy picks a witness as a fresh number and enumerates it into as before. It waits to see if becomes realized, and while waiting, the strategy has its rightmost outcome . Suppose enters via an axiom . The strategy first checks if it can extract without causing -correction that will extract from some number in . At this point, the strategy is willing to sacrifice all other setups that it has made so far and enumerate into and as many numbers as necessary in order to guarantee this, with the exception of a certain pair of finite sets and consisting of witnesses selected by higher-priority strategies and kept out of their corresponding set. So if it is possible to add to and some finite set of numbers that make the extraction of essentially harmless, then the strategy extracts from and takes outcome , where it will remain forever (unless initialized or restarted).
Suppose that this is not possible. In this case, the strategy α gives up on the witness (at least for now) and decides to prove that β’s requirement is satisfied by initiating the construction of Δ so that . We say that α switches β from Γ to Δ. The fact that an extraction of from causes the extraction of a finite set from can now be turned into the first axiom in Δ. We would like to have a stronger relationship: if and only if . Of course, currently there might be other numbers in and whose extraction may also cause to leave . In order to remove their influence, we will dump into and , respectively, all numbers that were ever in or unless they belong to a higher-priority -strategy (i.e., are in or ) or a lower-priority -strategy : We collect those elements in and . The act of dumping means that we enumerate these numbers into or , respectively, and never again allow them to leave these sets. (Note that any numbers controlled by strategies to the right of the outcome ∞ of α, or which will be replaced by new versions, can be dumped without harm.) We begin the construction of the operator Δ by enumerating the axiom , along with for every element x that is dumped into . At the end of this stage, we will visit the outcome ∞, but before we do so, we set things up for a new round: We extract the killing point from and redefine it as a fresh number. We record the parameters in a list W that we keep track of and then redefine the value of as a new fresh number. At the next visit, the strategy α will start a new attempt at diagonalization with this new witness, but it will keep an eye on the previous witness z and its parameters and . If it ever sees that by dumping into and elements outside of , it can restore and extract z from (and this extraction will not cause β to extract any element from back out of to correct ), then the strategy α will do so and take outcome forever.
Below the outcome ∞ of α, we will have a duplicate strategy for every requirement of lower priority than β’s requirement, including the one that α failed to satisfy. These strategies will not have to worry about the strategy β any longer as its requirement is satisfied in a different way. Specifically, an -strategy γ will be able to employ the original Friedberg–Muchnik strategy with a couple of modifications: The witnesses that γ can use have to be the witnesses that α formerly used for its definition of Δ; these will be collected in a stream that α controls. Every time α has outcome ∞, it adds one more element to the stream . The strategy γ will wait for the stream to contain a currently unused witness z before it can carry on. It will then proceed as usual; however, it will only trust below the current killing point of α. So z will be realized if at the current stage. If ∞ is α’s true outcome, i.e., if α visits this outcome infinitely often, then β’s activity is pushed away by the extraction of the infinite unbounded sequence of killing points, thereby destroying as discussed above, but giving γ enough room to faithfully realize its witness. Note that since is unbounded, we will still have that if the witness is never realized then it does not belong to . Finally, if γ succeeds in realizing a witness, then it extracts it from and declares victory with outcome . This might have an unanticipated effect on the operator Δ that α is constructing. It is possible that an axiom for some number was enumerated into Δ under the assumption that z remains in . The extraction of z from may cause to not be a subset of , even though . To prevent complications in the operator Δ, we will in this case dump (and thus remove from the stream) all elements in the stream that entered the stream after z did.
A similar consideration has to be incorporated when an -strategy δ works below . For simplicity, we may assume that δ has no -strategy working above it. The strategy δ also operates a simple Friedberg–Muchnik strategy with the additional requirement that whenever it extracts a witness from , it must dump into (and thus remove from the stream) all witnesses that were put into the stream after δ defined its witness.
Strategies, parameters and the tree
We will describe the tree of strategies (which will be a finite-branching tree). We start with a priority ordering of all requirements of order type ω. To define the tree, we will make use of two other sets defined inductively as we move down the tree. We have a set of nodes that have been killed, and a list of requirements that need to be assigned (or reassigned) to nodes . The root of the tree will be assigned the highest-priority requirement, and we set and to consist of all requirements. Suppose that we have assigned a requirement to a node σ in the tree. If this strategy is an -strategy, say, then it has only one immediate successor . We set and assign to the highest-priority requirement in the list . We set .
Suppose now that σ is assigned an -requirement, say, an -requirement. (The case is similar, but now conflicting with .) Let be all initial segments of σ to which we have assigned an -strategy and which are not in . (We call such alive at σ.) The strategy σ has immediate successors,
We set and assign to each of the nodes and the highest-priority requirement in this list. We also set . For , we set to be , along with the requirements associated with , and σ. We assign to the highest-priority requirement in . We set .
Let h be an infinite path in the tree of strategies T. Every requirementin our priority ordering is assigned to some nodesuch that for every δ with,is not in.
We prove this statement by induction on the priority ordering of all requirements. Suppose that the statement is true for all requirements of higher priority than the requirement , and let be least such that no requirement of higher priority than enters where , or is assigned to any such δ. It follows that is assigned to some longest , and we have the following two cases:
Case 1: . Fix the -strategies that are alive at σ. By our inductive hypothesis, if there is a least strategy extending σ that puts into the list , then this strategy cannot kill for any by our inductive assumptions. Thus only σ (and possibly strategies extending σ) are killed by δ, and so δ will be assigned the requirement . Now, since no -requirement of higher priority than will switch from Γ to Δ along h beyond δ, the requirement cannot be added to for any with ; as a consequence, there is also a longest -strategy along h.
Case 2: , and by symmetry assume . Fix as usual the -strategies alive at σ. The strategy σ cannot put into the set unless σ switches the outcome of from Γ to Δ along h (since, by inductive hypothesis, no can be killed along h anymore). But then must be assigned to and cannot be added to for any with . □
An -strategy β has only its operator as a parameter. Initially (and after every initialization), we set . We will also refer to as (in the case of an -strategy, and proceed similarly in the case of an -strategy.)
An -strategy α extending -strategies still alive at α has a threshold , a set of killing points , a witness , a list of old witnesses , each component of which contains a number z, an index , two finite sets and , and enumeration operators , …, . Initially (and after every initialization), all of these parameters are undefined or empty. An -strategy γ has the same list of parameters with respect to all -strategies that are still alive at γ.
In addition, every strategy has two streams and . These streams are determined by the predecessor of every strategy. Whenever a strategy is canceled, most of the elements in its stream (except for possibly one element) will be dumped into the corresponding set or .
Construction
In our construction, we will build a sequence . Each is a node of length s on our tree of strategies. Strategies visited at stage will modify the values of their parameters, as well as the approximations to the sets , , and . Since our tree is finitely branching, there is a leftmost path of nodes visited at infinitely many stages, the true path. The intention is that for every requirement , there is a strategy along the true path that satisfies .
At stage 0, we set , and all parameters of all strategies are in initial state (either undefined or empty). All streams are empty.
At stage , we always start by visiting the root of the tree, namely, . We add to the streams and of the root the element s. Suppose we have built along with its streams and . If we have added a new number to , then we denote it by . If we have added a new number to , then we denote it by . If , then we are done with the construction of : We initialize all strategies , dump their streams into and , respectively, empty their streams (i.e., set ), and move on to the next stage.
Otherwise, we have four cases depending on the requirement assigned to :
is an -strategy β: The strategy scans all .
If , then the strategy picks a fresh marker and enumerates it into . Then it defines as the finite set of all β-killing points that belong to an -strategy with current threshold . (Note that this is a finite set as there are currently only finitely many strategies that are not in initial state.) The strategy then enumerates into the axiom .
If , then the strategy extracts from all markers that are in some valid axiom for x in .
Once the scan is over, the strategy defines the stream by adding to its previous value the number and, similarly, the stream by adding to it the number (if they exist). Then the strategy ends the substage with outcome 0.
is an -strategy. This case is dealt with analogously to the previous case.
is an -strategy α. Fix to be the -strategies alive at α. Let be the greatest lower bound of the set of all killing points , where γ is an -strategy and . Let and be the sets of witnesses currently used by higher-priority - and -strategies, respectively. Similarly, the sets and consist of the current witnesses of - and -strategies extending outcome .
If this is the first time that α is visited after initialization, then define the threshold to be fresh and large and the killing points as fresh numbers. Enumerate every killing point into . Then go to the first case which applies:
If has changed since we last visited α, then cancel , and for every . Extract the killing points where from . Define new values for these killing points and enumerate them into . Initialize all strategies of lower priority than α. Dump the streams and into and , respectively. Set for every possible outcome o of α and end the substage with outcome .
If the previous time when we visited α, it had outcome , and α has not been initialized since, then let the outcome again be . Define and by adding to them the number and , respectively (if they exist).
Scan the list of old witnesses . For each entry such that z has not yet been dumped into , check to see whether the number can be decreased: Find the least such that for every , if we enumerate back into the set , into every number such that and , and into every number that is not in the set , then will not be forced to extract from any number in during -correction. (In this case, we say that z is -cleared for .) If there are no witnesses with , then move on to step (d). Otherwise, among all witnesses with , pick the one with least , and among these the least z. Enumerate into , dump into every number such that and , and into every number such that . If , then set , extract it from and end the substage with outcome . Set for every possible outcome o of α and dump the elements that were in each stream into and , respectively.
Otherwise, if , then set . Let be the set such that if and only if . Enumerate into the axiom . Update the record in to include . Extract the killing points where from , and end the substage with outcome . We set the streams for every outcome o of α that is to the right of and dump all elements that were in those streams except z into and , respectively. Dump into (if it exists). We leave and unchanged for every outcome o of α that is to the left of . We update by adding the number z to it, and by adding the number (if it exists) to it.
If no current witness is selected and exists and is larger than the current witness of every -strategy γ with or , then define and enumerate it into . Otherwise (if is defined but too small), dump into . End the substage with outcome , leaving all streams of immediate successors of α unchanged.
If or if but for every valid axiom , we have that , then end the substage with outcome . Add into and into (if they exist). Leave all other streams of immediate successors of α unchanged.
If via an axiom with , then we add to and go back to step (c). (Note that the current outcome will not be , since in step (c), we are guaranteed to find some witness .) We also cancel the value of the current witness so that at the next visit, if α passes through steps (a), (b) and (c), then it will go to step (d) and select a new value of the witness.
is an -strategy. This case is dealt with analogously to the previous case.
Verification
As anticipated, we have an infinite true path f of strategies on the tree consisting of the leftmost nodes visited at infinitely many stages. Our intention is to prove that nodes along this path satisfy their requirements. In order to prove that nodes on this path are initialized only finitely often, we must consider an -strategy on the true path and think about how many times it can be restarted, as that is the only reason, other than just visiting a node to the left of a strategy, that causes the initialization of strategies. We will prove, in Lemma 4.4, that for every -strategy , the set is , and similarly, for every -strategy , the set is . Throughout this proof, we will phrase various interactions between strategies for the pairs and . We note that the relationship between and is symmetric.
First, we point out a technical fact about streams that will be useful in the rest of the proof.
If n enters a stream of a strategy δ at stage s and δ was last visited or initialized at stage, thenand n is larger than all previous elements of either stream of δ.
The proof is an easy induction on the construction. The root is never initialized, and at stage , , which is the last time the root was visited.
Suppose the statement is true about δ. If δ adds and to the stream of its immediate successor, then the statement clearly follows by induction, as we cannot initialize an immediate successor of δ without either visiting or initializing δ. So suppose that δ is an -strategy, say, and δ adds a witness z to the stream of , as that is the only other case. In that case, the witness z was defined after was last visited or initialized at stage t, as whenever we initialize or visit , we initialize and empty the stream of all strategies where . At the stage when z was defined, it was defined as , which by induction is greater than or equal to the previous stage when δ was visited, and hence greater than or equal to t, and larger than any element in the stream of . □
Letbe an-strategy. Suppose that α is an-strategy such thatand β is alive at α. Letbe a threshold of α. Then there is a stage s such that after stage s, the strategy β does not modify the setbelow the threshold. Thus, in particular, if β is never killed along f then the setis.
We prove this theorem by induction on the priority of β and α. So towards a contradiction, suppose that the statement is false for a pair of strategies , and take the pair where α has highest priority. It follows from our choice of α that there is a least stage such that after stage , the strategy α (and hence β as well) is not initialized and never again changes the value of its threshold . At stage , the strategy α picks its killing points as fresh numbers, and hence they do not interfere with any axiom for any number in . After stage , every time changes on some number , the strategy α is restarted. It chooses all parameters anew and initializes all lower-priority strategies. This means that if β enumerated a new axiom into for some such that , then:
This axiom cannot be invalidated by any strategy γ of equal or lower priority than α, as -strategies are initialized or restarted and hence pick their killing points as fresh numbers larger than and have thresholds larger than n (hence none of their killing points will be included by β in this axiom). -strategies have to pick their witnesses anew, from fresh streams, as their streams are emptied at the current stage. Hence these witnesses will be larger than the current stage and will not be included in the -portion of the axiom for n.
The axiom that made n enter uses (by our convention) only numbers smaller than the current stage and hence it will not be invalidated by any strategy of equal or lower priority than α, as these strategies are initialized and their streams are emptied. By Lemma 4.3, their streams will contain only numbers larger than the current stage, from which they will pick their witnesses.
No strategy of higher priority than α can invalidate either of these axioms, either: A higher-priority strategy extracts from or only at stages at which it, for the first time after initialization, has its leftmost outcome , which by our choice of must happen before stage . Similarly, after stage , higher-priority strategies extract killing points only associated with -strategies that they end up killing, and since β is alive at α, this cannot be β. Of course, all -markers are different, so -strategies do not interfere with each other.
It only takes finitely many stages for any number that ever enters to enter permanently, and hence after that stage, β will not need to modify ever again. □
The lemma above has two easy but significant corollaries. The first corollary was already anticipated by us.
Every strategy along the true path is initialized at most finitely often. □
The second corollary gives us the satisfaction of -requirements in one case.
Ifis an-strategy that is alive at every successor of β along the true path, then. The analogous statement for-strategies holds as well.
Fix an -strategy . Consider the -strategies along the true path. The sequence of the final values of their thresholds, attained at the first true stage after the corresponding strategy stops being initialized, is an unbounded increasing sequence. By Lemma 4.4, for every i, there is a stage such that at all , the strategy β does not modify on numbers less than , and hence, by β’s design, at all stages . Furthermore, the proof of Lemma 4.4 actually gives us more: If is in at any β-true stage after selects its last threshold , then . This gives us immediately that and, by the unboundedness of , the fact that . □
We next concentrate on the -requirements. To prove that each is eventually satisfied, we will first show that once a number is -cleared, it will remain -cleared at all future stages.
Fix an-strategybelow-strategiesalive at α. If α moves a witness z fromto, where, at a stage after α’s last initialization, then at any future stage, if z is extracted fromandis enumerated back into, the strategywill not changeto cause z to be extracted from.
Suppose that at stage s, the strategy α moves z from to , where . At this stage, it dumps into all numbers such that , and into all numbers such that . At stage s, we see that under these circumstances, the extraction of z from will not cause any number y that is currently in and that has an -marker to leave the set . Assuming that as seen at the current stage s remains a subset of , and that as seen at stage s remains a subset of , this will be true at future stages as well, as every strategy to the right of is initialized and will select its future witnesses from its stream that is currently empty and will by Lemma 4.3 in the future only have elements larger than any number mentioned before stage s, hence not be included in any axiom in valid at stage s.
The only potential problem is that some strategy γ might, at a stage t, extract from a number y that is in the set at stage s, or from a number y that is in the set at stage s.
First note that if , then y is the current witness of an -strategy . Since δ has no witness at stages when it has an infinite outcome, and its current witness is not in if it has outcome , it follows that . This means that y remains the current witness of δ at all future stages and never enters another stream. No other strategy has access to it in order to extract it at stage t.
Suppose that for . Let be the strategy with witness y at stage s. Let γ be the strategy that extracts y at stage t. Once again, γ cannot have higher priority than α, or else α would be initialized. It follows that , or else , where , as all other strategies of lower priority than α are initialized at the stage when y was assigned to δ as a witness and thus have streams consisting of elements larger than y by Lemma 4.3. If , then at stage t, the strategy α dumps all elements less than t that are not in into and , respectively, in particular z will be dumped. If and , then consider the stage r at which y entered the stream of . Since at stage s, the number y is already in the stream of , and whenever a number switches streams, all streams associated with strategies to the right are dumped, we have that at stage r, the number z is dumped (z cannot already be in a stream to the left of or equal to at stage r, or else y would have been dumped before stage r). □
Every-requirement is satisfied.
By symmetry, fix an -requirement, say. By Lemma 4.2, there is a strategy α along the true path that is assigned and such that no strategy σ extending α along the path f has . It follows that or .
Let be the first stage after which α is not initialized. Recall that the number is defined as the greatest lower bound of the set of all killing points , where γ is an -strategy and . Every time that α is visited, this number has a larger value than at the previous visit. Furthermore, no -strategy of higher priority than α modifies on numbers . This is because when such an -strategy γ such that has outcome , it extracts from all killing points , where , and then it redefines them as fresh numbers. The strategy γ cannot extract any smaller killing point without initializing α.
So can only be modified by an -strategy β above α. We note that such a strategy is necessarily alive at α. Indeed, if β is not alive above at α, then it is killed by a strategy γ such that and β is γ’s j-th -strategy, where . Every time that γ has outcome , it extracts its j-th killing point from , thereby invalidating all axioms in for numbers . After stage , the strategy β does not modify on any number , hence if it sees a valid axiom for some x that needs to be made invalid, then . This axiom has marker .
If , then let be such that α has outcome at every stage . After stage s, the strategy α will select its final witness . It follows from the construction that never enters with an axiom that does not use any numbers larger than . Since the values of at α-true stages form an unbounded sequence, it follows that every axiom we ever see for in is invalid at infinitely many stages. Hence . As no strategy other than α can extract from , and is enumerated into at the stage when it is defined, it follows that .
If, on the other hand, , then there is a stage such that α has outcome for the first time at stage s. At this stage, α has found a witness z that is cleared by all higher priority -strategies that are alive at α. Note that , and by Lemma 4.7, no strategy β that is alive at α will extract a marker from that is in . Every number that was in when the axiom for z in was found is dumped into at stage s (only elements that are in are preserved; however, they cannot have been in when z was realized and not be in later unless α is initialized). It follows that . □
The final lemma that we present handles the case when an -requirement is satisfied by its backup strategy, which completes the proof.
Let α be an-strategy below the-strategiesalive at α. If, then. (Of course, a symmetric result holds for-strategies below-strategies.)
Let be a stage such that is not initialized after stage . After this stage, the set does not change. We prove that if is an element that is never dumped into , then either or if and only if .
Fix x and suppose that x is never dumped into and that . Fix the least witness z of α such that . Consider the stage at which z is realized and enters one of the streams of α’s immediate successors. If , then at that stage, x would be dumped into . So suppose that . Now consider the next stage at which α has outcome . At that stage, some element enters the stream , and by our choice of , we know that at this stage, x is in some stream where . If , then x would be dumped into at this stage, so suppose that and x enters the stream at stage s. Then at this stage, we add an axiom into for x, where is such that under the current circumstances at stage s, we have that if and only if . As in the proof of Lemma 4.7, if some number that is in the set at stage s is extracted from or a number that is in the set at stage s is extracted from , then x is dumped into . So suppose that neither of these ever happens. Then clearly, if , then , as all strategies of lower priority than are initialized at stage s. If at any stage , we visit α and notice that even if , then the strategy α will move x to a smaller stream and initialize , contrary to our assumptions. □
Putting Corollary 4.6 and Lemma 4.9 together, we conclude the following
Every-requirement is satisfied.
Fix an -requirement, say. By Lemma 4.2, let β be the longest -strategy along f. If β is not switched from Γ to Δ by any strategy extending β along f, then by Corollary 4.6, is satisfied. If and α switches β from Γ to Δ, then β is α’s i-th live -strategy. By Lemma 4.9, , and hence is once again satisfied. □
The second author was partially supported by AMS-Simons Foundation Collaboration Grant 626304. The third author was supported by MOE grant RG23/19. The fourth author was supported by NSF grants DMS-1762648 and DMS-2053848 and by the grant FNI-SU80-10-128/16.04.2020. All the authors thank the two referees for their helpful comments.
References
1.
S.Ahmad, Some results on the structure of the enumeration degrees, PhD thesis, Simon Fraser University, Canada, 1989.
2.
S.Ahmad and A.H.Lachlan, Some special pairs of e-degrees, MLQ Math. Log. Q.44(4) (1998), 431–449. doi:10.1002/malq.19980440402.
3.
S.B.Cooper, Partial degrees and the density problem. II. The enumeration degrees of the sets are dense, J. Symbolic Logic49(2) (1984), 503–513. doi:10.2307/2274181.
4.
H.Ganchev and M.Soskova, Interpreting true arithmetic in the local structure of the enumeration degrees, J. Symbolic Logic77(4) (2012), 1184–1194. doi:10.2178/jsl.7704070.
5.
T.F.Kent, The -theory of the -enumeration degrees is undecidable, J. Symbolic Logic71(4) (2006), 1284–1302. doi:10.2178/jsl/1164060455.
6.
S.Lempp, M.Lerman and R.Solomon, Embedding finite lattices into the computably enumerable degrees – A status survey, in: Logic Colloquium ’02, Lect. Notes Log., Vol. 27, Assoc. Symbol. Logic, La Jolla, CA, 2006, pp. 206–229.
7.
S.Lempp, A.Nies and T.A.Slaman, The -theory of the computably enumerable Turing degrees is undecidable, Trans. Amer. Math. Soc.350(7) (1998), 2719–2736. doi:10.1090/S0002-9947-98-01800-5.
8.
S.Lempp, T.A.Slaman and A.Sorbi, On extensions of embeddings into the enumeration degrees of the -sets, J. Math. Log.5(2) (2005), 247–298. doi:10.1142/S0219061305000432.
9.
S.Lempp, T.A.Slaman and M.I.Soskova, Fragments of the theory of the enumeration degrees, Advances in Mathematics383 (2021), 107686. doi:10.1016/j.aim.2021.107686.
10.
S.Lempp and A.Sorbi, Embedding finite lattices into the enumeration degrees, J. Symbolic Logic67(1) (2002), 69–90. doi:10.2178/jsl/1190150030.
11.
A.Nies, R.A.Shore and T.A.Slaman, Interpretability and definability in the recursively enumerable degrees, Proc. London Math. Soc. (3)77(2) (1998), 241–291. doi:10.1112/S002461159800046X.
12.
G.E.Sacks, On the degrees less than , Ann. of Math. (2)77 (1963), 211–231. doi:10.2307/1970214.
13.
T.A.Slaman and W.H.Woodin, Definability in the enumeration degrees, Arch. Math. Logic36(4–5) (1997), 255–267.
14.
M.I.Soskova, The theory of the enumeration degrees, definability, and automorphisms, in: Contemporary Logic and Computing, Landsc. Log, Vol. 1, Coll. Publ., London, 2020, pp. 706–730.
