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; 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.
Myhill (1956) asked whether maximal sets exist and Friedberg (1958) constructed one.
This mathematical logic-related article is a stub.