This July 2007 does not contain any links to other Wikipedia articles. |
Template:Wikify is deprecated. Please use a more specific cleanup template as listed in the documentation. |
A maximal set is a coinfinite recursively enumerable (r.e.) subset A of the natural numbers such that for every further r.e. 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 lattic of the r.e. sets. Maximal sets have many interesting properties: they are simple, 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 which are not maximal; some of them do even not have maximal supersets. Myhill (1956) asked whether maximal sets exists and Frieberg (1958) constrcuted one. Soare (1974) 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.
This article has not been added to any content categories. Please help out by adding categories to it so that it can be listed with similar articles. (June 2007) |