On n-tardy sets

DOI10.1016/J.APAL.2012.02.001zbMATH Open1252.03100arXiv1101.0228OpenAlexW2963259647MaRDI QIDQ435200FDOQ435200

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)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Recursively enumerable sets of positive integers and their decision problems
• Title not available (Why is that?)
• TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
• Automorphisms of the Lattice of Recursively Enumerable Sets: Promptly Simple Sets
• Post's program and incomplete recursively enumerable sets.
• Codable sets and orbits of computably enumerable sets
• Definability, Automorphisms, and Dynamic Properties of Computably Enumerable Sets
• The Δ₃⁰-automorphism method and noninvariant classes of degrees

Cited In (2)

• Title not available (Why is that?)
• 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)