Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6424819 | Annals of Pure and Applied Logic | 2012 | 19 Pages |
Abstract
Harrington and Soare introduced the notion of an n-tardy set. They showed that there is a nonempty E 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 E properties Qn(A) such that if Qn(A) then A is properly n-tardy.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Logic
Authors
Peter A. Cholak, Peter M. Gerdes, Karen Lange,