Content deleted Content added
Paul August (talk | contribs) m paragraph |
Paul August (talk | contribs) Add reference |
||
Line 4:
Maximal sets have many interesting properties: they are [[simple set|simple]], [[hypersimple]], [[hyperhypersimple]]<!-- These terms should be defined and given context. --> 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 that are not maximal; some of them do even not have maximal supersets. Myhill (1956)<!-- I DON'T SEE A PAPER BY MYHILL CITED HERE. --> asked whether maximal sets exists and Frieberg (1958) constructed one. Soare (1974)<!-- SAME COMMENT HERE. --> 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.
{{math-stub}}
| |||