Hostname: page-component-586b7cd67f-rcrh6 Total loading time: 0 Render date: 2024-11-24T05:24:24.238Z Has data issue: false hasContentIssue false
  • English
  • Français

Jump equivalence of the Δ20 hyperimmune sets1

Published online by Cambridge University Press:  12 March 2014

S. B. Cooper
S. B. Cooper*
Affiliation:
University of California, Berkeley, California 94720 University of Leeds, Leeds, England
Get access Rights & Permissions [Opens in a new window]

Extract

An infinite set A is said to be hyperhyperimmune (h.h.i.) if, for any collection of disjoint simultaneously recursively enumerable (r.e.) finite sets, A must fail to intersect with one of those sets. Thus the elements of an h.h.i. set are, in a sense, very elusive. D. A. Martin [3] showed that the degrees of h.h.i. sets with r.e. complements are exactly the r.e. degrees with jump 0″. More generally, C. G. Jockusch [2] found a′ ≥ 0″ to be a sufficient condition for a to be the degree of an h.h.i. set and found a′ ≥ 0′ to be necessary. However, it was also shown that in the degrees as a whole neither condition gave a characterization of the h.h.i. degrees. The purpose of this note is to prove that a′ = 0″does characterize the h.h.i. degrees below 0′.

Theorem. The degrees below 0′ containing h.h.i. sets are exactly those degrees below 0′ with jump 0″.

Proof. From [2], if a′ ≥ 0″, then a contains an h.h.i. set.

Conversely, let A ∈ a where a′ < 0″ and a < 0′. Let {As ∣ s ≥ 0} be a recursive sequence of finite sets such that for each x, lims, Ax(x) exists and equals A(x).

For a set B, let B[m] denote B ∩ [0, m], and (if B is finite) let ∣B∣ denote the cardinality of B.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 37 , Issue 3 , September 1972 , pp. 598 - 600
Copyright
Copyright © Association for Symbolic Logic 1972

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.)

Footnotes

1

This work was financed in part under the Senior Fulbright-Hays Program.

References

REFERENCES

[1]Cooper, S. B., Minimal degrees and the jump-operator, this Journal (to appear).Google Scholar
[2]Jockusch, Carl G. Jr., The degrees of hyperhyperimmune sets, this Journal, vol. 34 (1969), pp. 489–493.Google Scholar
[3]Martin, D. A., Classes of recursively enumerable sets and degrees of unsolvability, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 12 (1966), pp. 295–310.CrossRefGoogle Scholar
[4]Yates, C. E. M., Recursively enumerable sets and retracing functions, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 8 (1962), p. 341.CrossRefGoogle Scholar