Dynamic and structural properties of the computably enumerable sets

Abstract:

Friedberg [1] and Mučnik [4] famously constructed computably enumerable sets of whole numbers that are noncomputable but do not code the halting set. To build their examples, they independently developed the priority method, a dynamic and flexible construction framework. Harrington and Soare [2] showed that one can identify such examples using only the structure of the collection $\mathcal{E}$ of computably enumerable (c.e.) sets under set containment. In other words, they gave a (nonempty) property $Q$ in terms of set containment that is satisfied in $\mathcal{E}$ by only incomplete noncomputable c.e. sets. All c.e. sets that satisfy $Q$ have a slow enumeration property called $2$-tardiness [3]. We explore $n$-tardiness, as a means to further understand the interplay between dynamic enumeration properties of c.e. sets and static structural properties of $\mathcal{E}$. We also discuss the structure of $\mathcal{D}$-maximal sets, generalizations of both maximal and hemimaximal sets in $\mathcal{E}$. We use both tardiness and $\mathcal{D}$-maximality to further develop the picture of orbits of sets under automorphisms of $\mathcal{E}$.

This is joint work with Peter Cholak and Peter Gerdes.

References

[1] Richard M. Friedberg. Two recursively enumerable sets of incomparable degrees of unsolvability (solution of Post’s problem, 1944). Proc. Nat. Acad. Sci. U.S.A., 43:236-238, 1957.
[2] Leo Harrington and Robert I. Soare. Post’s program and incomplete recursively enumerable sets. Proc. Nat. Acad. Sci. U.S.A., 88(22):10242-10246, 1991.
[3] Leo Harrington and Robert I. Soare. Codable sets and orbits of computably enumerable sets. J. Symbolic Logic, 63(1):1-28, 1998.
[4] A. A. Mučnik. On the unsolvability of the problem of reducibility in the theory of algorithms. Dokl. Akad. Nauk SSSR (N.S.), 108:194-197, 1956.