Definability in the enumeration degrees

We prove that every countable relation on the enumeration degrees, , is uniformly definable from parameters in . Consequently, the first order theory of is recursively isomorphic to the second order theory of arithmetic. By an effective version of coding lemma, we show that the first order theory of the enumeration degrees of the sets is not decidable. Received: August 1, 1994     

Quasi-minimal enumeration degrees and minimal Turing degrees

We show that there exists a set A such that A has quasi-minimal enumeration degree, and there are uncountably many sets B such that A is enumeration reducible to B and B has minimal Turing degree. Answering a related question raised by Solon, we also show that there exists a nontotal enumeration degree which is not e-hyperimmune.During the preparation of this paper, Slaman was partially supported by the HCM European Program no. ERBCHRXCT930415 (while he was visiting the University of Leeds), by NSF Grant DMS-9500878 and was a CNR Visiting Professor at the University of Siena.The preparation of this paper was partially supported by the HCM European Program no. ERBCHRXCT930415 and by MURST 60%.     

Badness and jump inversion in the enumeration degrees

This paper continues the investigation into the relationship between good approximations and jump inversion initiated by Griffith. Firstly it is shown that there is a ${\Pi^{0}_{2}}$ set A whose enumeration degree a is bad—i.e. such that no set ${X \in a}$ is good approximable—and whose complement ${\overline{A}}$ has lowest possible jump, in other words is low₂. This also ensures that the degrees y ≤ a only contain ${\Delta^{0}_{3}}$ sets and thus yields a tight lower bound for the complexity of both a set of bad enumeration degree, and of its complement, in terms of the high/low jump hierarchy. Extending the author’s previous characterisation of the double jump of good approximable sets, the triple jump of a ${\Sigma^{0}_{2}}$ set A is characterised in terms of the index set of coinfinite sets enumeration reducible to A. The paper concludes by using Griffith’s jump interpolation technique to show that there exists a high quasiminimal ${\Delta^{0}_{2}}$ enumeration degree.     

A non-splitting theorem in the enumeration degrees

We complete a study of the splitting/non-splitting properties of the enumeration degrees below by proving an analog of Harrington’s non-splitting theorem for the enumeration degrees. We show how non-splitting techniques known from the study of the c.e. Turing degrees can be adapted to the enumeration degrees.     

Density of the cototal enumeration degrees

We prove that the cototal enumeration degrees are exactly the enumeration degrees of sets with good approximations, as introduced by Lachlan and Shore [17]. Good approximations have been used as a tool to prove density results in the enumerations degrees, and indeed, we prove that the cototal enumerations degrees are dense.     

Limit lemmas and jump inversion in the enumeration degrees

We show that there is a limit lemma for enumeration reducibility to 0_e', analogous to the Shoenfield Limit Lemma in the Turing degrees, which relativises for total enumeration degrees. Using this and `good approximations' we prove a jump inversion result: for any set W with a good approximation and any set X<_eW such that W_eX' there is a set A such that X_eA<_eW and A'=W'. (All jumps are enumeration degree jumps.) The degrees of sets with good approximations include the ⁰₂ degrees and the n-CEA degrees. The results in this paper form part of the author's doctoral dissertation written under the supervision of Prof. Steffen Lempp at the University of Wisconsin Madison. The author is grateful to an anonymous referee for helpful comments and suggestions.     

C-Quasi-Minimal enumeration degrees below c'

This paper is dedicated to the study of properties of the operations ∪ and ∩ in the upper semilattice of the e-degrees as well as in the interval (c,c')_e for any e-degree c. The work was supported by grant IR-97-139 of INTAS-RFBR.     

The limitations of cupping in the local structure of the enumeration degrees

We prove that a sequence of sets containing representatives of cupping partners for every nonzero D⁰₂{\Delta^0_2} enumeration degree cannot have a D⁰₂{\Delta^0_2} enumeration. We also prove that no subclass of the S⁰₂{\Sigma^0_2} enumeration degrees containing the nonzero 3-c.e. enumeration degrees can be cupped to 0_e￠{\mathbf{0}_e'} by a single incomplete S⁰₂{\Sigma^0_2} enumeration degree.     

A note on the enumeration degrees of 1-generic sets

We show that every nonzero \({\Delta^{0}_{2}}\) enumeration degree bounds the enumeration degree of a 1-generic set. We also point out that the enumeration degrees of 1-generic sets, below the first jump, are not downwards closed, thus answering a question of Cooper.     

Numeration and enumeration

In this paper, numeration systems defined by recurrent sequences are considered. We present a class of recurrences yielding numeration systems for which the words corresponding to greedy expressions for natural numbers are easily described. Those sequences, in turn, enumerate classes of words with forbidden substrings.     

On degeneracy in enumeration

In the case of degeneracy in an LP-formulation, there is not a one-to-one correspondence between extreme points and feasible bases. If the task is to find thek best extreme points in the set of feasible solutions to an LP, this lack of correspondence has a certain importance, since methods based on the Simplex Algorithm are oriented towards feasible bases instead of the relevant extreme points. We therefore present an easily implementable method to avoid this problem.     

Formal languages and enumeration

We present a theory of generating functions in countably many non-commuting variables. This generalizes the theory of context free languages. Applications are given to compositions of a number, rooted planar tree, dissected polygons, and the theory of simple random walks.     

Competitive equilibrium and singleton cores in generalized matching problems

We study competitive equilibria in generalized matching problems. We show that, if there is a competitive matching, then it is unique and the core is a singleton consisting of the competitive matching. That is, a singleton core is necessary for the existence of competitive equilibria. We also show that a competitive matching exists if and only if the matching produced by the top trading cycles algorithm is feasible, in which case it is the unique competitive matching. Hence, we can use the top trading cycles algorithm to test whether a competitive equilibrium exists and to construct a competitive equilibrium if one exists. Lastly, in the context of bilateral matching problems, we compare the condition for the existence of competitive matchings with existing sufficient conditions for the existence or uniqueness of stable matchings and show that it is weaker than most existing conditions for uniqueness.