Hull operator

from Wikipedia, the free encyclopedia
A set of 8 points and their convex hull

In mathematics , the envelope of a set is understood to be a superset that is large enough to meet certain requirements and is also the smallest set that meets these requirements. Examples are the convex hull of a subset of a vector space , the closed hull of a subset of a topological space or the transitive hull of a two-digit relation . Shell operator describes the rule by which every set of objects is assigned its shell. The envelopes given by an envelope operator form a system of envelopes , i.e. a system of sets with certain properties.

Definitions

Hull operators

Over a given basic set , a hull operator is an extensive , monotonic , idempotent mapping to the power set of , which assigns a further subset of , namely the hull , to each subset , where the following conditions are met:

(Et) Extensiveness:, that is: The shell of contains at least the set itself.
(M) Monotony or isotony:, that means: If is a subset of , this also applies accordingly to its envelopes.
(Ip) Idempotence:, that means: If one forms the envelope of a set again, this remains unchanged.

Because of the other two requirements, it is also sufficient to only demand instead of idempotence , that is: If one forms the cover again from the cover of a set, nothing more is added.

The following is equivalent to the three named individual claims. is called an envelope operator if the following applies to all :

(Oh) .

A cover operator is also called a closure operator because a cover operator belonging to a structured set (a topological space , an algebraic structure ) maps each subset of this structured set to the smallest substructure that contains this subset. The substructures ( closed sets in topological space, algebraic substructures ) form the subsets closed with regard to the given structure .

Algebraic Hull Operators

The envelope operators occurring in algebra , universal algebra , geometry and related sub-areas are usually algebraic envelope operators . This is equivalent to saying that this shell operators associated envelope systems algebraically are and thus satisfy the finiteness condition:

(Oa): For every subset and for any element there is always a finite subset with .

This concept formation is especially well known from linear algebra , where in every vector space the linear envelope of any subset of vectors corresponds to the set of all linear combinations of these vectors.

Envelope systems

A shell system is a set system closed with arbitrary intersection formation , i. That is, a shell system over a set is a set consisting of subsets of the basic set with the following properties:

(Sh 0 ): contains the basic set: .
(Sh 1 ): For each non-empty subset of the average of the elements of is an element of , or in short .

With the basic set, it makes sense to define the average over the empty set, which is not generally defined in set theory, because this is the only way to achieve it. This simplifies the two conditions mentioned to a single equivalent condition:

(Sh): For each subset of the average of the elements of is an element of , or in short .

Relationship between envelope systems and envelope operators

Hull systems and hull operators correspond to one another:

  • Is a cover system , then you can have a closure operator to define as follows:
for everyone .
The set, over which the average is formed here, is not empty because of .
  • Conversely, from any closure operator on a containment system over are obtained:
.

There is a simple and fast algorithm for generating all hulls of a given hull operator (algorithm 1 in).

Examples

  • Let's look at the plane . The convex subsets of the plane form an envelope system, the associated envelope operator is the formation of the convex envelope of a subset.
  • The minimally surrounding rectangle is a shell in the sense of this concept formation.
  • The closed sets of a topological space form an envelope system. The associated hull operator creates the closed hull of a subset of the underlying topological space and is sometimes referred to as the Kuratowski hull operator after the Polish mathematician Kuratowski . The closed envelope of a subset of a topological space is the smallest superset that is closed with limit value formation of networks on the respective set.
  • If a group is given, its subgroups form a shell system. The associated hull operator is the formation of the subgroup, which is generated by a subset .
  • The normal divisors of a group form an envelope system.
  • Every ideal system is a shell system.
  • The formation of the transitive envelope of a relation is an envelope operator.
  • The two concatenations and a Galois connection are envelope operators.
  • The formation of the Kleene shell of a formal language is a shell operator.
  • The σ-operator from measure theory , which assigns the smallest comprehensive σ-algebra to every set of subsets of a space , is an envelope operator. There are also shell operators for creating Dynkin systems and monotonic classes .
  • The inference operation of formal logic is an envelope operator.
  • For the envelope body to a set of numbers is required that at all elements of the set always their sum, their product, their difference and their quotient (except division by zero) and the numbers 1 and 0 belong to the set. The envelope of the set {0} is thus already the set of all rational numbers . Only when the set of numbers contains at least one irrational number (for example ) does a field arise that truly encompasses.
  • In every subcategory of Set that contains only inclusion maps as morphisms , every monad is an envelope operator.

Applications to formal languages ​​and complexity classes

It is a class of formal languages . We consider the following envelope operators on :

  • : Degree under homomorphisms :
    If so , then too
  • : Conclusion under -free homomorphisms, like , but
  • : Conclusion under inverse homomorphisms:
    If so , then too
  • : Degree under Association:
  • : Graduation below average:
  • : Conclusion under concatenation :
  • : Graduation under Kleene star :

If a class and one of the above envelope operators have the property , then under the corresponding operation (homomorphism, homomorphism, -free homomorphism, inverse homomorphism, union, intersection, concatenation or Kleene star) is called closed.

See also

literature

  • Marcel Erné: Introduction to Order Theory . Bibliographisches Institut, Mannheim u. a. 1982, ISBN 3-411-01638-8 .
  • John L. Kelley : General Topology (=  Graduate Texts in Mathematics . Volume 27 ). Reprinted edition. Springer, New York a. a. 1975, ISBN 3-540-90125-6 .
  • Heinrich Werner: Introduction to general algebra (=  BI university pocket books . Volume 120 ). Bibliographisches Institut, Mannheim u. a. 1978, ISBN 3-411-00120-8 .

Individual evidence

  1. Ganter, Bernhard and Obiedkov, Sergei (2016): Conceptual exploration . Springer, ISBN 978-3-662-49290-1