m Jean Abou Samra moved page Maximal set to Maximal set (computability theory): Add parentheses/disambiguator: The existing title doesn't help to quickly understand what the article is about since there are a great many contexts in mathematics where we have a family of subsets and we want to find/study its maximal elements
m Use the more modern terminology (recursive → computable)
Line 1:
In [[recursioncomputability theory]], the [[mathematics|mathematical]] theory of [[computability]], a '''maximal set''' is a coinfinite [[recursivelycomputably enumerable set|recursivelycomputably enumerable subset]] ''A'' of the [[natural number]]s such that for every further recursivelycomputably 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 (order)|lattice]] of the recursivelycomputably enumerable sets.
Maximal sets have many interesting properties: they are [[simple set|simple]], [[hypersimple set|hypersimple]], [[hyperhypersimple]] and r-maximal; the latter property says that every recursivecomputable 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 recursivelycomputably enumerable sets under inclusion ([[Modulo (jargon)|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 recursivelycomputably enumerable sets such that ''A'' is mapped to ''B''.
