Maximal set (computability theory): Difference between revisions

Revision as of 03:06, 13 April 2009

Revision as of 23:20, 2 September 2009

Line 1:

{{Orphan|date=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.