Article contents
A noninitial segment of index sets
Published online by Cambridge University Press: 12 March 2014
Extract
Let {Wk}k ≥ 0 be a standard enumeration of all recursively enumerable (r.e.) sets. If A is any class of r.e. sets, let θA denote the index set of A, i.e., θA = {k ∣ Wk ∈ A}. The one-one degrees of index sets form a partial order ℐ which is a proper subordering of the partial order of all one-one degrees. Denote by ⌀ the one-one degree of the empty set, and, if b is the one-one degree of θB, denote by the one-one degree of . Let . Let {Ym}m≥0 be the sequence of index sets of nonempty finite classes of finite sets (classified in [5] and independently, in [2]) and denote by am the one-one degree of Ym. As shown in [2], these degrees are complete at each level of the difference hierarchy generated by the r.e. sets. It was proved in [3] that, for each m ≥ 0,
(a) am+1 and ām+1 are incomparable immediate successors of am and ām, and
(b) .
For m = 0, since Y0 = θ{⌀}, it follows from (a) that
(c) .
Hence it follows that
(d) {⌀, , ao, ā0, a1, ā1 is an initial segment of ℐ.
- Type
- Research Article
- Information
- Copyright
- Copyright © Association for Symbolic Logic 1974
References
REFERENCES
- 3
- Cited by