Maximal set (computability theory): Difference between revisions

Revision as of 05:24, 10 July 2008

Revision as of 04:57, 13 July 2008

Line 1:

{{articleissues|context=July 2008|refimprove=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|natural numbers]]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.

Maximal sets have many interesting properties: they are [[simple set|simple]], [[hypersimple]], [[hyperhypersimple]] and r-maximal;{{clarifyme}} 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){{factFact|date=July 2008}} asked whether maximal sets exists and Frieberg (1958){{factFact|date=July 2008}} constructed one. Soare (1974){{factFact|date=July 2008}} showed that the maximal sets form an orbit with respect to [[automorphism]] of the recursively enumerable sets under inclusion ([[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 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. ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1.

<br />{{math-stub}}

[[Category:Recursion theory]]

{{math-stub}}