Maximal set
Encyclopedia
In recursion theory
, the mathematical
theory of computability, a maximal set is a coinfinite 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
of the recursively enumerable 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 that are not maximal; some of them do even not have maximal supersets. Myhill (1956) asked whether maximal sets exists and Friedberg (1958) constructed 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.
Recursion theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
, the mathematical
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
theory of computability, a maximal set is a coinfinite recursively enumerable subset
Recursively enumerable set
In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing-recognizable if:...
A of the natural number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s such that for every further recursively enumerable subset B of the natural numbers, either B is cofinite
Cofinite
In mathematics, a cofinite subset of a set X is a subset A whose complement in X is a finite set. In other words, A contains all but finitely many elements of X...
or B is a finite variant of A or B is not a superset of A. This gives an easy definition within the lattice
Lattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
of the recursively enumerable sets.
Maximal sets have many interesting properties: they are simple
Simple set
In recursion theory a subset of the natural numbers is called a simple set if it is recursively enumerable, but every infinite subset of its complement fails to be enumerated recursively...
, 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 that are not maximal; some of them do even not have maximal supersets. Myhill (1956) asked whether maximal sets exists and Friedberg (1958) constructed one. Soare (1974) showed that the maximal sets form an orbit with respect to automorphism
Automorphism
In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphisms of an object forms a group, called the automorphism...
of the recursively enumerable sets under inclusion (modulo
Modulo (jargon)
The word modulo is the Latin ablative of modulus which itself means "a small measure."It was introduced into mathematics in the book Disquisitiones Arithmeticae by Carl Friedrich Gauss in 1801...
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.