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.

Definitionen

Ein Hüllenoperator ist eine extensive, monotone, idempotente Abbildung H, die jeder Teilmenge A einer gegebenen Menge X wiederum eine Teilmenge von X, nämlich die Hülle H(A), zuordnet. Im Einzelnen bedeuten die Anforderungen:

Extensivität
A \subseteq H(A), das heißt: die Hülle von A enthält mindestens die Menge A selbst.
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.
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. H \colon \mathcal{P}(X) \to \mathcal{P}(X) heißt Hüllenoperator, wenn für alle A, B \subseteq X gilt

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

Einen Hüllenoperator nennt man auch Abschlussoperator, weil ein zu einer strukturierten Menge (ein topologischer Raum, eine algebraische 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 abgeschlossen Teilmengen.

Hüllensysteme

Definition

Ein Hüllensystem ist ein unter beliebiger Schnittmengenbildung abgeschlossenes Mengensystem, d.h. ein Hüllensystem auf einer Menge X ist eine aus Teilmengen von X bestehende Menge S mit folgenden Eigenschaften:

Betrachtet man X als Grundmenge, so ist es in diesem Kontext sinnvoll, den allgemein mengentheoretisch nicht definierten Durchschnitt über die leere Menge als

\bigcap\emptyset := X

zu definieren, denn nur so wird X=\bigcap\{X\}\subseteq \bigcap\emptyset \subseteq X erreicht. Dadurch vereinfachen sich die beiden genannten Bedingungen zu der einzigen – gleichwertigen – Bedingung

Zusammenhang zwischen Hüllensystemen und Hüllenoperatoren

Hüllenoperatoren und Hüllensysteme entsprechen einander:

H_S(A) := \bigcap \{ Y \in S | 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.
S_H := \{ H(A) | A \subseteq X \}.

In vielen Anwendungsfällen hat man einen lediglich monotonen Operator F gegeben, d. h. für jede Teilmenge A\subseteq X ist auch F(A)\subseteq X und aus A\subseteq B folgt F(A)\subseteq F(B). Beispielsweise könnte F für einen topologischen Raum X jeder Punktmenge die Menge ihrer Häufungspunkte zuordnen, oder – falls X eine Halbgruppe ist – jeder Menge A die Menge aller Produkte von Elementen aus A. Einen zugehörigen Hüllenoperator erhält man dann auf eine von zwei Weisen:

Beide Varianten liefern denselben Hüllenoperator. Man spricht dann auch vom Abschluss unter F. Die erste Variante ist meist für theoretische, die zweite für praktische Anwendungen günstiger.

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 H_{hom}(\{L\}) = \{L' | \exist h, h \mbox{ ist Homomorphismus}: h[L]=L' \} \,\,\,\,\in\mathcal{C}
Wenn L\in\mathcal{C}, dann auch H_{inv-hom}(\{L\}) = \{L' | \exist h, h \mbox{ ist Homomorphismus}: h[L']=L \} \,\,\,\,\in\mathcal{C}
H_{\cup}(\mathcal{C}) = \{L | \exists L_1,L_2\in\mathcal{C} : L=L_1\cup L_2\}
H_{\cap}(\mathcal{C}) = \{L | \exists L_1,L_2\in\mathcal{C} : L=L_1\cap L_2\}
H_{\circ}(\mathcal{C}) = \{L | \exists L_1,L_2\in\mathcal{C} : L=L_1L_2\}
H_{kleene}(\mathcal{C}) = \{L | \exists L'\in\mathcal{C} : L=L'^*\}

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

Siehe auch

Kernoperator

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