On n-tardy sets

DOI10.1016/J.APAL.2012.02.001MaRDI QIDQ435200zbMATHOpenAlexFDO

Authors Peter A. Cholak, Peter M. Gerdes, Karen Lange

Publication date 11 July 2012

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1101.0228

zbMATH Keywords

automorphisms\(n\)-tardy setsc.e. setsr.e. sets

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)

Abstract: Harrington and Soare introduced the notion of an n-tardy set. They showed that there is a nonempty $mathcalE$ 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 $mathcalE$ properties $Q_n(A)$ such that if $Q_n(A)$ then A is properly n-tardy.

Recommendations

• Publication:4863241
• Codable sets and orbits of computably enumerable sets
• Extending properly n - REA sets1
• scientific article; zbMATH DE number 123920
• There is no fat orbit

Cites work

• scientific article; zbMATH DE number 3117565 (Why is no real title available?)
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• 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
• Post's program and incomplete recursively enumerable sets.
• Recursively enumerable sets of positive integers and their decision problems
• TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
• The Δ₃⁰-automorphism method and noninvariant classes of degrees

Cited in

(2)

• scientific article; zbMATH DE number 841085 (Why is no real title available?)
• Some recent research directions in the computably enumerable sets

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)