Maximal set

Maximal set

In recursion theory, the mathematical theory of computability, a maximal set is a coinfinite recursively enumerable subset A of the natural numbers 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;[clarification needed] 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.

References




Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Maximal — may refer to: Maximal element, a mathematical definition Maximal (Transformers), a faction of Transformers Maximalism, an artistic style Maximal set Maxim (magazine), a men s magazine marketed as Maximal in several countries See also Minimal… …   Wikipedia

  • Maximal intersecting family — A maximal intersecting family (MIF) of k sets (i.e., sets with cardinality k, where k is a natural number) is a family of sets Z satisfying the following: Every element of Z is a k set. Every pair of elements of Z has a nonempty intersection.… …   Wikipedia

  • Maximal function — Maximal functions appear in many forms in harmonic analysis (an area of mathematics). One of the most important of these is the Hardy–Littlewood maximal function. They play an important role in understanding, for example, the differentiability… …   Wikipedia

  • Maximal arc — Maximal arcs are (k,d) arcs in a projective plane, where k is maximal with respect to the parameter d and the ambient space. Definition Let π be a projective plane of order q (not necessarily desarguesian). Maximal arcs of degree d ( )are (k,d)… …   Wikipedia

  • Maximal independent set — This article is about the combinatorial aspects of maximal independent sets of vertices in a graph. For other aspects of independent vertex sets in graph theory, see Independent set (graph theory). For other kinds of independent sets, see… …   Wikipedia

  • Maximal element — In mathematics, especially in order theory, a maximal element of a subset S of some partially ordered set is an element of S that is not smaller than any other element in S. The term minimal element is defined dually. The notion of a maximal is… …   Wikipedia

  • Maximal ideal — In mathematics, more specifically in ring theory, a maximal ideal is an ideal which is maximal (with respect to set inclusion) amongst all proper ideals.[1][2] In other words, I is a maximal ideal of a ring R if I is an ideal of R, I ≠ R, and… …   Wikipedia

  • Maximal consistent set — In mathematics, a maximal consistent set is a set of formulae belonging to some formal language that satisfies the following constraints: * The set is consistent, that is, no formula is both provable and refutable. * The set is maximal , which… …   Wikipedia

  • Maximal torus — In the mathematical theory of compact Lie groups a special role is played by torus subgroups, in particular by the maximal torus subgroups. A torus in a Lie group G is a compact, connected, abelian Lie subgroup of G (and therefore isomorphic to… …   Wikipedia

  • Maximal evenness — The major scale is maximally even. For example, for every generic interval of a second there are only two possible specific intervals: 1 semitone (a minor second) or 2 semitones (a major second) …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”