Maximal set (computability theory)

In recursion theory, the mathematical theory of computability, a maximal set is a coinfinite recursively enumerable subset A of the natural numbers such that for every further recursively 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 recursively enumerable sets.

Maximal sets have many interesting properties: they are simple, hypersimple, hyperhypersimple and r-maximal;^{[clarification needed]} the latter property says that every recursive 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)^{[citation needed]} asked whether maximal sets exists and Frieberg (1958)^{[citation needed]} constructed one. Soare (1974)^{[citation needed]} showed that the maximal sets form an orbit with respect to automorphism of the recursively 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 recursively 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: 309–316, ISSN 0022-4812, MR 0109125
• Myhill, John (1956), "Solution of a problem of Tarski", The Journal of Symbolic Logic, 21: 49–51, ISSN 0022-4812, MR 0075894
• 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.