Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-26T02:03:46.458Z Has data issue: false hasContentIssue false
  • English
  • Français

On minimal pairs of enumeration degrees

Published online by Cambridge University Press:  12 March 2014

Kevin McEvoy  and
S. Barry Cooper
Kevin McEvoy
Affiliation:
School of Mathematics, University of Leeds, Leeds LS2 9JT, England
S. Barry Cooper
Affiliation:
School of Mathematics, University of Leeds, Leeds LS2 9JT, England
Get access Rights & Permissions [Opens in a new window]

Extract

For sets of natural numbers A and B, A is enumeration reducible to B if there is some effective algorithm which when given any enumeration of B will produce an enumeration of A. Gutteridge [5] has shown that in the upper semilattice of the enumeration degrees there are no minimal degrees (see Cooper [3]), and in this paper we study those pairs of degrees with gib 0. Case [1] constructed a minimal pair. This minimal pair construction can be relativised to any gib, and following a suggestion of Jockusch we can also fix one of the degrees and still construct the pair. These methods yield an easier proof of Case's exact pair theorem for countable ideals. 0″ is an upper bound for the minimal pair constructed in §1, and in §2 we improve this bound to any Σ2-high Δ2 degree. In contrast to this we show that every low degree c bounds a degree a which is not in any minimal pair bounded by c. The structure of the co-r.e. e-degrees is isomorphic to that of the r.e. Turing degrees, and Gutteridge has constructed co-r.e. degrees which form a minimal pair in the e-degrees. In §3 we show that if a, b is any minimal pair of co-r.e. degrees such that a is low then a, b is a minimal pair in the e-degrees (and so Gutteridge's result follows). As a corollary of this we can embed any countable distributive lattice and the two nondistributive five-element lattices in the e-degrees below 0′. However the lowness assumption is necessary, as we also prove that there is a minimal pair of (high) r.e. degrees which is not a minimal pair in the e-degrees (under the isomorphism). In §4 we present more concise proofs of some unpublished work of Lagemann on bounding incomparable pairs and embedding partial orderings.

As usual, {Wi}i ∈ ω is the standard listing of the recursively enumerable sets, Du is the finite set with canonical index u and {‹ m, n ›}m, n ∈ ω is a recursive, one-to-one coding of the pairs of numbers onto the numbers. Capital italic letters will be variables over sets of natural numbers, and lower case boldface letters from the beginning of the alphabet will vary over degrees.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 50 , Issue 4 , December 1985 , pp. 983 - 1001
Copyright
Copyright © Association for Symbolic Logic 1985

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Case, J., Enumeration reducibility and partial degrees, Annals of Mathematical Logic, vol. 2 (1971), pp. 419–439.CrossRefGoogle Scholar
[2]Cooper, S. B., Minimal pairs and high recursively enumerable degrees, this Journal, vol. 39 (1974), pp. 655–660.Google Scholar
[3]Cooper, S. B., Partial degrees and the density problem, this Journal, vol. 47 (1982), pp. 854–859.Google Scholar
[4]Cooper, S. B., Partial degrees and the density problem. Part 2: The enumeration degrees of the Σ2 sets are dense, this Journal, vol. 49 (1984), pp. 503–513.Google Scholar
[5]Gutteridge, L., Some results on enumeration reducibility, Ph.D. Dissertation, Simon Fraser University, Burnaby, 1971. (Abstract: Dissertation Abstracts International, vol. 33B (1972), pp. 319B–320B.)Google Scholar
[6]Kleene, S. C. and Post, E. L., The upper semi-lattice of degrees of unsolvability, Annals of Mathematics, ser. 2, vol. 59 (1954), pp. 379–407.CrossRefGoogle Scholar
[7]Lachlan, A. H., Lower bounds for pairs of recursively enumerable degrees, Proceedings of the London Mathematical Society, ser. 3, vol. 16 (1966), pp. 537–569.CrossRefGoogle Scholar
[8]Lachlan, A. H., Embedding nondistributive lattices in the recursively enumerable degrees, Conference in Mathematical Logic–London 1970 (Hodges, W., editor), Lecture Notes in Mathematics, vol. 255, Springer-Verlag, Berlin, 1972, pp. 150–177.Google Scholar
[9]Lagemann, J., Embedding theorems in the reducibility ordering of the partial degrees, Ph.D. Dissertation, Massachusetts Institute of Technology, Cambridge, Massachusetts, 1972.Google Scholar
[10]Lerman, M., Degrees of unsolvability, Springer-Verlag, Berlin, 1983.CrossRefGoogle Scholar
[11]McEvoy, K., Jumps of quasi-minimal enumeration degrees, this Journal, vol. 50 (1985), pp. 839–848.Google Scholar
[12]McEvoy, K., On the structure of the enumeration degrees, Ph.D. Thesis, University of Leeds, Leeds. 1984.Google Scholar
[13]Rogers, H. Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[14]Rozinas, M., The semilattice of e-degrees (Russian), Recursive functions (Russian) (Polyakov, E. A., editor), Ivanovskiĭ Gosudarstvennyĭ Universitet, Invanovo, 1978, pp. 71–84. (MR 82i: 03057).Google Scholar
[15]Soare, R. I., Tree arguments in recursion theory and the 0‴-priority method, Recursion theory, Proceedings of Symposia in Pure Mathematics, vol. 42, American Mathematical Society, Providence, Rhode Island, 1985, pp. 53–106.CrossRefGoogle Scholar
[16]Soare, R. I., Recursively enumerable sets anddegees, Omega Series in Logic, Springer-Verlag, Berlin (to appear).Google Scholar
[17]Spector, C., On degrees of recursive unsolvability, Annals of Mathematics, ser. 2, vol. 64 (1956), pp. 581–592.CrossRefGoogle Scholar
[18]Thomason, S. A., Sublattices of the recursively enumerable degrees, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 17 (1971), pp. 273–280.CrossRefGoogle Scholar
[19]Yates, C. E. M., A minimal pair of recursively enumerable degrees, this Journal, vol. 31 (1966), pp. 159–168.Google Scholar