Hüllenoperator

In der Mathematik versteht man unter der Hülle eine Art minimale Erweiterung eines Objektes zu einem Objekt eines speziellen Typs.

Definitionen

Ein Hüllenoperator ist eine Abbildung $H$, die jeder Teilmenge einer gegebenen Menge $X$ eine Teilmenge von $X$ zuordnet und dabei folgende Eigenschaften hat:

1. Für alle Teilmengen $A$ von $X$ gilt $A\subseteq H(A)$, das heißt das Bild $H(A)$ ist immer eine Obermenge von $A$ (Extensivität),
2. für zwei Teilmengen $A$ und $B$ von $X$ gilt $A\subseteq B\Rightarrow H(A)\subseteq H(B)$, das heißt die Teilmengenrelation wird von $H$ respektiert (Monotonie) und
3. für alle Teilmengen $A$ von $X$ gilt $H(A)=H(H(A))$, das heißt ist eine Menge bereits ein Bild unter $H$, so wird sie auf sich selbst abgebildet (Idempotenz).

Die Idempotenz führt dazu, dass man hier auch von einem Abschluss spricht, $H$ heißt dann auch Abschlussoperator.

Ein Hüllensystem $(X,S)$ ist eine Menge $X$ zusammen mit einer Menge $S$, die aus Teilmengen von $X$ besteht, mit folgenden Eigenschaften:

• $X$ ist Element von $S$.
• Für jede Teilmenge $T$ aus $S$ ist der Schnitt der Elemente von $T$ ein Element aus $S$, oder anders ausgedrückt: Der Durchschnitt von beliebig vielen Elementen von $S$ ist selbst ein Element von $S$.

Hüllenoperatoren und Hüllensysteme entsprechen einander:

• Ist ${\mathcal {H}}$ ein Hüllensystem auf $A$, dann kann man einen Hüllenoperator ${\mathcal {C}}_{\mathcal {H}}$ wie folgt definieren:

${\mathcal {C}}_{\mathcal {H}}(X):=\bigcap \{H\in {\mathcal {H}}|H\supseteq X\}$ für alle $X\subseteq A$.

• Umgekehrt kann aus jedem Hüllenoperator ${\mathcal {C}}$ auf $A$ ein Hüllensystem auf ${\mathcal {H}}_{\mathcal {C}}$ auf $A$ gewonnen werden durch:

${\mathcal {H}}_{\mathcal {C}}:=\{{\mathcal {C}}(X)|X\subseteq A\}$.

Beispiele

• Betrachten wir die Ebene R². Alle konvexen Teilmengen der Ebene bilden zusammen ein Hüllensystem, der zugehörige Hüllenoperator die Bildung der konvexen Hülle einer Teilmenge.
• Die abgeschlossenen Mengen eines topologischen Raumes bilden ein Hüllensystem. Der zugehörige Hüllenoperator ist die Bildung der abgeschlossenen Hülle einer Teilmenge und heißt Kuratowskischer Hüllenoperator.
• Ist eine Gruppe gegeben, so bilden ihre Untergruppen ein Hüllensystem. Der zugehörige Hüllenoperator ist die Bildung der Untergruppe, die von einer Teilmenge erzeugt wird.
• Die Normalteiler einer Gruppe bilden ein Hüllensystem.
• Die beiden Verkettungen $\sigma \tau$ und $\tau \sigma$ einer Galois-Verbindung $(\sigma ,\tau )$ sind Hüllenoperatoren.
• Die Bildung der Kleeneschen Hülle einer formalen Sprache ist ein Hüllenoperator.
• Der Sigma-Operator aus der Maßtheorie, der jeder Menge von Teilmengen eines Raumes die kleinste umfassende Sigma-Algebra zuordnet, ist ein Hüllenoperator.
• Die Inferenzoperation der formalen Logik ist ein Hüllenoperator.

Anwendungen auf Formale Sprachen und Komplexitätsklassen

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

• $H_{hom}$: Abschluss unter Homomorphismen:

Wenn $L\in {\mathcal {C}}$, dann auch $H_{hom}(\{L\})=\{L'|\exists h,h{\mbox{ ist Homomorphismus}}:h[L]=L'\}\,\,\,\,\in {\mathcal {C}}$

• $H_{e-hom}$: Abschluss unter $\varepsilon$-freien Homomorphismen, wie $H_{hom}$, aber $\forall x:h(x)\not =\varepsilon$

• $H_{inv-hom}$: Abschluss unter inversen Homomorphismen:

Wenn $L\in {\mathcal {C}}$, dann auch $H_{inv-hom}(\{L\})=\{L'|\exists h,h{\mbox{ ist Homomorphismus}}:h[L']=L\}\,\,\,\,\in {\mathcal {C}}$

• $H_{\cup }$: Abschluss unter Vereinigung:

$H_{\cup }({\mathcal {C}})=\{L|\exists L_{1},L_{2}\in {\mathcal {C}}:L=L_{1}\cup L_{2}\}$

• $H_{\cap }$: Abschluss unter Durchschnitt:

$H_{\cap }({\mathcal {C}})=\{L|\exists L_{1},L_{2}\in {\mathcal {C}}:L=L_{1}\cap L_{2}\}$

• $H_{\circ }$: Abschluss unter Konkatenation:

$H_{\circ }({\mathcal {C}})=\{L|\exists L_{1},L_{2}\in {\mathcal {C}}:L=L_{1}L_{2}\}$

• $H_{kleene}$: Abschluss unter Kleene-Stern:

$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: Mengensystem