s-Degrees within e-Degrees
For any enumeration degree a let \(D^s_{\bf a}\) be the set of s-degrees contained in a. We answer an open question of Watson by showing that if a is a nontrivial \(\Sigma^0_2\) -enumeration degree, then \(D^s_{\bf a}\) has no least element. We also show
- PDF / 415,526 Bytes
- 9 Pages / 430 x 660 pts Page_size
- 53 Downloads / 178 Views
stract. For any enumeration degree a let Das be the set of s-degrees contained in a. We answer an open question of Watson by showing that if a is a nontrivial Σ20 -enumeration degree, then Das has no least element. We also show that every countable partial order embeds into Das .
1
Introduction
Positive reducibilities formalize models of relative computability which use only “positive ” oracle information. The most comprehensive positive reducibility is enumeration reducibility, denoted by ≤e . Intuitively a set A is enumeration reducible to a set B if there is some effective procedure for enumerating A given any enumeration of B. This is made mathematically precise by defining A ≤e B if there exists a c.e. set Φ such that A = {x : (∃ finite D)[x, D ∈ Φ & D ⊆ B]} (often denoted by A = ΦB ) where finite sets are identified with their canonical indices. In this context a c.e. set Φ is also called an enumeration operator. It is clear that given a set B, an enumeration operator Φ, and a given x, there is no bound to the number n of oracle questions which are needed to enumerate x in ΦB , i.e. to the cardinality of a finite set D for which we need D ⊆ B, in order to have x ∈ ΦB . One can therefore introduce restricted, or strong, versions of enumeration reducibility by requesting instead that there be such a bound, such as is done in [1]. Although extreme, the case n = 1, in which for any given x we need at most one oracle question, is particularly interesting, and occurs often in practical applications of enumeration reducibility. This suggests the following definition: Definition 1.1. An enumeration operator Φ is called an s-operator if for every x, D ∈ Φ, we have that D has at most one element. It is straightforward to see that the s-operators (s stands for singleton) can be effectively listed, and give rise to a reducibility (called s-reducibility), denoted by ≤s . The corresponding degree structure, denoted by Ds , consists of the
The author has been supported by a Marie Curie Incoming International Fellowship of the European Community FP6 Program under contract number MIFI-CT-2006021702.
M. Agrawal et al. (Eds.): TAMC 2008, LNCS 4978, pp. 579–587, 2008. c Springer-Verlag Berlin Heidelberg 2008
580
T.F. Kent
equivalence classes, called s-degrees, of the subsets of ω under the equivalence relation ≡s generated by ≤s . The s-degree of a set A will be denoted by degs (A). The structure Ds is an upper semilattice with least element 0s = degs (∅) consisting of the c.e. sets, and the operation of least upper bound is given by degs (A) ∪ degs (B) = degs (A ⊕ B), where ⊕ denotes the usual disjoint union of sets. It is clear that if A ≤s B then A ≤e B and so it is natural to ask questions about the structure of the s-degrees contained within a single enumeration degree. Given a set A, define A∗ = {n : Dn ∈ A} where n is the canonical index of the finite set Dn . It follows that A∗ ≡e A and if B ≤e A then B ≤s A∗ , and so degs (A∗ ) is the greatest s-degree in dege (A). Zacharov [10] showed that ≤s is properly contained
Data Loading...
