Maximal set (computability theory): Difference between revisions

Revision as of 03:24, 16 July 2008

Revision as of 00:00, 31 July 2008

Line 1:

{{articleissues|context=July 2008|jargon=July 2008|orphan=July 2008|incomplete=July 2008}}

In [[recursion theory]], the [[mathematics|mathematical]] theory of computability, a '''maximal set''' is a coinfinite [[recursively enumerable set|recursively enumerable subset]] ''A'' of the [[natural number]]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 (order)|lattice]] of the recursively enumerable sets.