recursion theory Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since ex ...

, the

mathematical Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

theory of computability, a maximal set is a coinfinite recursively enumerable subset ''A'' of the

natural number In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...

s 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 Simple or SIMPLE may refer to: *Simplicity, the state or quality of being simple Arts and entertainment * ''Simple'' (album), by Andy Yorke, 2008, and its title track * "Simple" (Florida Georgia Line song), 2018 * "Simple", a song by John ...

, 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''. 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 In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphism ...

of the recursively enumerable sets under inclusion (

modulo In computing and mathematics, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another, the latter being called the '' modulus'' of the operation. Given two positive numbers and , mo ...

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

* * * H. Rogers, Jr., 1967. ''The Theory of Recursive Functions and Effective Computability'', second edition 1987, MIT Press. (paperback), . *
Computability theory {{mathlogic-stub