Maximal set (computability theory)

In computability theory, a maximal set is a coinfinite computably enumerable subset A of the natural numbers such that for every further computably enumerable subset B of the natural numbers, either B is cofinite or B is a finite variant of A or B is not a superset of A. This gives an easy definition within the lattice of the computably enumerable sets.

Maximal sets have many interesting properties: they are simple, hypersimple, hyperhypersimple and r-maximal; the latter property says that every computable set R contains either only finitely many elements of the complement of A or almost all elements of the complement of A. There are r-maximal sets that are not maximal; some of them do even not have maximal supersets. Myhill (1956) asked whether maximal sets exist and Friedberg (1958) constructed one. Soare (1974) showed that the maximal sets form an orbit with respect to automorphism of the computably enumerable sets under inclusion (modulo finite sets). On the one hand, every automorphism maps a maximal set A to another maximal set B; on the other hand, for every two maximal sets A, B there is an automorphism of the computably enumerable sets such that A is mapped to B.

References

• Friedberg, Richard M. (1958), "Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication", The Journal of Symbolic Logic, 23 (3), Association for Symbolic Logic: 309–316, doi:10.2307/2964290, JSTOR 2964290, MR 0109125, S2CID 25834814
• Myhill, John (1956), "Solution of a problem of Tarski", The Journal of Symbolic Logic, 21 (1), Association for Symbolic Logic: 49–51, doi:10.2307/2268485, JSTOR 2268485, MR 0075894, S2CID 19695459
• H. Rogers, Jr., 1967. The Theory of Recursive Functions and Effective Computability, second edition 1987, MIT Press. ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1.
• Soare, Robert I. (1974), "Automorphisms of the lattice of recursively enumerable sets. I. Maximal sets", Annals of Mathematics, Second Series, 100 (1), Annals of Mathematics: 80–120, doi:10.2307/1970842, JSTOR 1970842, MR 0360235