Hüllenoperator

Eine Menge aus 8 Punkten und ihre konvexe Hülle

In der Mathematik versteht man unter der Hülle einer Menge eine Obermenge, die groß genug ist, um bestimmte Anforderungen zu erfüllen, und zugleich die kleinste Menge ist, die diese Anforderungen erfüllt. Beispiele sind die konvexe Hülle einer Teilmenge eines Vektorraums, die abgeschlossene Hülle einer Teilmenge eines topologischen Raums oder die transitive Hülle einer zweistelligen Relation. Hüllenoperator bezeichnet die Vorschrift, durch die jeder Menge von Objekten ihre Hülle zugeordnet wird. Die durch einen Hüllenoperator gegebenen Hüllen bilden ein Hüllensystem, also ein Mengensystem mit bestimmten Eigenschaften.

Definitionen

Hüllenoperatoren

Über einer gegebenen Grundmenge X ist ein Hüllenoperator eine extensive, monotone, idempotente Abbildung {\displaystyle H\colon \;{\mathcal {P}}(X)\to {\mathcal {P}}(X)} auf der Potenzmenge von X, welche jeder Teilmenge A\subseteq X eine weitere Teilmenge von X, nämlich die Hülle {\displaystyle H(A)\subseteq X}, zuordnet, wobei folgende Bedingungen erfüllt sind:

(Et) Extensivität: A\subseteq H(A), das heißt: Die Hülle von A enthält mindestens die Menge A selbst.
(M) Monotonie bzw. Isotonie: A\subseteq B\ \Rightarrow \ H(A)\subseteq H(B), das heißt: Wenn A Teilmenge von B ist, so gilt das entsprechend auch für ihre Hüllen.
(Ip) Idempotenz: H(H(A))=H(A), das heißt: Bildet man von der Hülle einer Menge nochmals die Hülle, so bleibt diese unverändert.

Aufgrund der beiden anderen Anforderungen genügt es auch, an Stelle der Idempotenz nur H(H(A))\subseteq H(A) zu fordern, das heißt: Bildet man von der Hülle einer Menge nochmals die Hülle, so wird nichts mehr hinzugefügt.

Äquivalent zu den drei genannten Einzelforderungen ist folgende. {\displaystyle H\colon \;{\mathcal {P}}(X)\to {\mathcal {P}}(X)} heißt Hüllenoperator, wenn für alle A,B\subseteq X gilt:

(Oh): H(A)\subseteq H(B)\Longleftrightarrow A\subseteq H(B).

Einen Hüllenoperator nennt man auch Abschlussoperator, weil ein zu einer strukturierten Menge (einem topologischen Raum, einer algebraischen Struktur) gehörender Hüllenoperator jede Teilmenge dieser strukturierten Menge auf die kleinste Unterstruktur abbildet, die diese Teilmenge enthält. Die Unterstrukturen (abgeschlossene Mengen im topologischen Raum, algebraische Unterstrukturen) bilden aber gerade die bezüglich der gegebenen Struktur abgeschlossenen Teilmengen.

Algebraische Hüllenoperatoren

Die in der Algebra, der Universellen Algebra, der Geometrie und verwandten Teilgebieten auftretenden Hüllenoperatoren sind in der Regel algebraische Hüllenoperatoren. Dies ist gleichbedeutend damit, dass die diesen Hüllenoperatoren zugehörigen Hüllensysteme algebraisch sind und damit die folgende Endlichkeitsbedingung erfüllen:

(Oa): Zu jeder Teilmenge A\subseteq X und für jedes beliebige Element {\displaystyle a\in H(A)} gibt es stets eine endliche Teilmenge {\displaystyle A_{0}\subseteq A} mit {\displaystyle a\in H(A_{0})}.

Diese Begriffsbildung ist vor allem aus der Linearen Algebra wohlbekannt, wo in jedem Vektorraum die lineare Hülle einer beliebigen Teilmenge von Vektoren mit der Menge aller Linearkombinationen dieser Vektoren übereinstimmt.

Hüllensysteme

Ein Hüllensystem ist ein unter beliebiger Schnittmengenbildung abgeschlossenes Mengensystem, d.h., ein Hüllensystem über einer Menge X ist eine aus Teilmengen der Grundmenge X bestehende Menge \mathcal{S} mit folgenden Eigenschaften:

(Sh0): \mathcal{S} enthält die Grundmenge: {\displaystyle X\in {\mathcal {S}}}.
(Sh1): Für jede nichtleere Teilmenge {\mathcal  {T}} von \mathcal{S} ist der Durchschnitt der Elemente von {\mathcal  {T}} ein Element aus \mathcal{S}, oder kurz: {\displaystyle \forall \;{\mathcal {T}}\subseteq {\mathcal {S}},\,{\mathcal {T}}\neq \emptyset \colon \;\bigcap {\mathcal {T}}\in {\mathcal {S}}}.

Mit X als Grundmenge ist es sinnvoll, den allgemein mengentheoretisch nicht definierten Durchschnitt über die leere Menge als \bigcap \emptyset :=X zu definieren, denn nur so wird {\displaystyle X=\bigcap \{X\}\subseteq \bigcap \emptyset \subseteq X} erreicht. Dadurch lassen sich die beiden genannten Bedingungen zu einer einzigen äquivalenten Bedingung vereinfachen:

(Sh): Für jede Teilmenge {\mathcal  {T}} von \mathcal{S} ist der Durchschnitt der Elemente von {\mathcal  {T}} ein Element aus \mathcal{S}, oder kurz: {\displaystyle \forall \;{\mathcal {T}}\subseteq {\mathcal {S}}\colon \;\bigcap {\mathcal {T}}\in {\mathcal {S}}}.

Zusammenhang zwischen Hüllensystemen und Hüllenoperatoren

Hüllensysteme und Hüllenoperatoren entsprechen einander:

{\displaystyle H_{\mathcal {S}}(A):=\bigcap \{Y\in S\mid Y\supseteq A\}} für alle A\subseteq X.
Die Menge, über die hier der Durchschnitt gebildet wird, ist wegen X\in S nicht leer.
{\displaystyle {\mathcal {S}}_{H}:=\{H(A)\mid A\subseteq X\}}.

Es gibt einen einfachen und schnellen Algorithmus zur Erzeugung aller Hüllen eines gegebenen Hüllenoperators (Algorithmus 1 in ).

Beispiele

Anwendungen auf formale Sprachen und Komplexitätsklassen

Es sei {\mathcal {C}} eine Klasse von formalen Sprachen. Wir betrachten folgende Hüllenoperatoren auf {\mathcal {C}}:

Wenn L\in {\mathcal  {C}}, dann auch {\displaystyle H_{\text{hom}}(\{L\})=\{L'\mid \exists h\colon h{\text{ ist Homomorphismus}}:h[L]=L'\}\in {\mathcal {C}}}
Wenn L\in {\mathcal  {C}}, dann auch {\displaystyle H_{\text{inv-hom}}(\{L\})=\{L'\mid \exists h\colon h{\text{ ist Homomorphismus}}:h[L']=L\}\in {\mathcal {C}}}
{\displaystyle H_{\cup }({\mathcal {C}})=\{L\mid \exists L_{1},L_{2}\in {\mathcal {C}}\colon L=L_{1}\cup L_{2}\}}
{\displaystyle H_{\cap }({\mathcal {C}})=\{L\mid \exists L_{1},L_{2}\in {\mathcal {C}}\colon L=L_{1}\cap L_{2}\}}
{\displaystyle H_{\circ }({\mathcal {C}})=\{L\mid \exists L_{1},L_{2}\in {\mathcal {C}}\colon L=L_{1}L_{2}\}}
{\displaystyle H_{\text{kleene}}({\mathcal {C}})=\{L\mid \exists L'\in {\mathcal {C}}\colon L=L'^{*}\}}

Wenn eine Klasse {\mathcal {C}} und einer der obigen Hüllenoperatoren H die Eigenschaft {\displaystyle H({\mathcal {C}})={\mathcal {C}}} haben, dann heißt {\mathcal {C}} unter der entsprechenden Operation (Homomorphismus, \varepsilon -freier Homomorphismus, inverser Homomorphismus, Vereinigung, Durchschnitt, Konkatenation bzw. Kleene-Stern) abgeschlossen.

Siehe auch

Literatur

Trenner
Basierend auf einem Artikel in: Wikipedia.de
Seitenende
Seite zurück
© biancahoegel.de
Datum der letzten Änderung: Jena, den: 16.10. 2022