Abstract: Harrington and Soare introduced the notion of an n-tardy set. They showed that there is a nonempty property Q(A) such that if Q(A) then A is 2-tardy. Since they also showed no 2-tardy set is complete, Harrington and Soare showed that there exists an orbit of computably enumerable sets such that every set in that orbit is incomplete. Our study of n-tardy sets takes off from where Harrington and Soare left off. We answer all the open questions asked by Harrington and Soare about n-tardy sets. We show there is a 3-tardy set A that is not computed by any 2-tardy set B. We also show that there are nonempty properties such that if then A is properly n-tardy.
This paper extends and generalizes work of Harrington and Soare on \(n\)-tardy sets. The authors prove the existence of (i) a 3-tardy set that is not \(\leq_T\) any 2-tardy set (and hence is not codable) and (ii) a low\({}_2\), simple, 2-tardy set. They also define a family of nontrivial lattice-theoretic properties \(Q_n\), with \(Q_n\) implying \(n\)-tardiness, and use this family to establish the existence of infinitely many incomplete orbits in \(\mathcal E\).
Recommendations
Cites work
- Automorphisms of the Lattice of Recursively Enumerable Sets: Promptly Simple Sets
- Codable sets and orbits of computably enumerable sets
- Definability, Automorphisms, and Dynamic Properties of Computably Enumerable Sets
- scientific article; zbMATH DE number 3117565 (Why is no real title available?)
- scientific article; zbMATH DE number 194103 (Why is no real title available?)
- Post's program and incomplete recursively enumerable sets.
- Recursively enumerable sets of positive integers and their decision problems
- The Δ₃⁰-automorphism method and noninvariant classes of degrees
- TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
Cited in
(2)
This page was built for publication: On \(n\)-tardy sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q435200)
