Maximal set (computability theory): Difference between revisions

Revision as of 17:25, 3 July 2007

Latest revision as of 10:23, 28 August 2025

(50 intermediate revisions by 25 users not shown)

Line 1:

In [[computability theory]], a '''maximal set''' is a coinfinite [[computably enumerable set|computably enumerable subset]] ''A'' of the [[natural number]]s such that for every further computably 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 computably enumerable sets.

{{deadend|July 2007}}

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 set|simple]], [[hypersimple set|hypersimple]], [[hyperhypersimple]] and r-maximal; the latter property says that every recursivecomputable 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 whichthat are not maximal; some of them do even not have maximal supersets. Myhill (1956) asked whether maximal sets existsexist and FriebergFriedberg (1958) constrcutedconstructed one. Soare (1974) showed that the maximal sets form an orbit with respect to [[automorphism]] of the recursivelycomputably enumerable sets under inclusion ([[Modulo (jargon)|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 recursivelycomputably enumerable sets such that ''A'' is mapped to ''B''.

{{wikify|date=July 2007}}

==References==

* {{Citation | last1=Friedberg | first1=Richard M. | title=Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication |mr=0109125 | year=1958 | journal=The Journal of Symbolic Logic | volume=23 | pages=309–316 | doi=10.2307/2964290 | issue=3 | publisher=Association for Symbolic Logic | jstor=2964290| s2cid=25834814 }}

* {{Citation | last1=Myhill | first1=John | title=Solution of a problem of Tarski |mr=0075894 | year=1956 | journal=The Journal of Symbolic Logic | volume=21 | pages=49–51 | doi=10.2307/2268485 | issue=1 | publisher=Association for Symbolic Logic | jstor=2268485| s2cid=19695459 }}

* 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}}.

* {{Citation | last1=Soare | first1=Robert I. | title=Automorphisms of the lattice of recursively enumerable sets. I. Maximal sets | doi=10.2307/1970842 |mr=0360235 | year=1974 | journal=[[Annals of Mathematics]] |series=Second Series | volume=100 | pages=80–120 | issue=1 | publisher=Annals of Mathematics | jstor=1970842}}

<br />

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.

{{Uncategorized|date=June 2007}}

[[Category:Computability theory]]

{{mathlogic-stub}}