Dynamic properties of computably enumerable sets
Leo A. Harrington, Robert Irving Soare · Cambridge University Press eBooks · 1996
A set A ⊆ ω is computably enumerable (c.e.) , also called recursively enumerable, (r.e.) , or simply enumerable , if there is a computable algorithm to list its members. Let ε denote the structure of the c.e. sets under inclusion. Starting with Post [1944] there has been much interest in relating the definable (especially ε-definable) properties of a c.e. set A to its “information content”, namely its Turing degree, deg( A ), under ≤ T , the usual Turing reducibility. [Turing 1939]. Recently, Harrington and Soare answered a question arising from Post's program by constructing a nonemptly ε-definable property Q(A) which guarantees that A is incomplete ( A < T K ). The property Q(A) is of the form (∃ C )[ A ⊂ m C & Q − ( A, C )], where A ⊂ m C abbreviates that “ A is a major subset of C ”, and Q − ( A,C ) contains the main ingredient for incompleteness. A dynamic property P(A) , such as prompt simplicity, is one which is defined by considering how fast elements elements enter A relative to some simultaneous enumeration of all c.e. sets. If some set in deg( A ) is promptly simple then A is prompt and otherwise tardy . We introduce here two new tardiness notions, small-tardy ( A, C ) and Q -tardy( A, C ). We begin by proving that small-tardy( A, C ) holds iff A is small in C ( A ⊂ s C ) as defined by Lachlan [1968]. Our main result is that Q -tardy( A, C ) holds iff Q − ( A,C ). Therefore, the dynamic property, Q -tardy( A, C ), which is more intuitive and easier to work with than the ε-definable counterpart, Q − ( A,C ), is exactly equivalent and captures the same incompleteness phenomenon.