Der Abschluss einer Menge

Ist (A, ∘) eine Struktur und B ⊆ A nicht abgeschlossen unter ∘, da die Anwendung der Operation für gewisse Elemente von B aus B herausführt, so stellt sich die Frage, wie wir B durch Hinzunahme möglichst weniger Elemente zu einer abgeschlossenen Menge B* erweitern können. Hierzu müssen wir zwingend alle Elemente c = a ∘ b mit a, b  ∈  B zu B hinzufügen. Dadurch entstehen neue Verknüpfungsmöglichkeiten wie zum Beispiel

c ∘ c = (a ∘ b) ∘ (a ∘ b),

und nichts garantiert uns, dass die Vergrößerung

B ∪ { a ∘ b | a, b  ∈  B } = B ∪ BB

von B abgeschlossen ist. In der Tat ist aber eine minimale Erweiterung B zu einer abgeschlossenen Menge immer möglich. Sie lässt sich auf zwei Arten erzeugen. Wir wählen die kürzere Art zur Definition und diskutieren danach die zweite Art, die sich als schrittweise Vergrößerung beschreiben lässt. Da das Problem allgemeiner Natur ist, formulieren wir die Begriffe für beliebige n-stellige Operationen.

Definition (Abschluß einer Menge)

Seien A eine Menge, n ≥ 1 und f : Aⁿ → A. Dann setzen wir für alle B ⊆ A:

〈  B  〉 = 〈  B  〉_f = ⋂ { C ⊆ A | B ⊆ C und C ist abgeschlossen unter f }.

Wir nennen 〈  B  〉 den Abschluss von B unter f. Weiter schreiben wir kurz 〈  b₁, …, b_n  〉 für 〈  { b₁, …, b_n }  〉.

Analog ist der Abschluss von B unter Operationen f, g, h, … definiert durch

〈  B  〉_{f, g, h, …} = ⋂ { C ⊆ A | B ⊆ C und C ist abgeschlossen unter f, g, h, … }.

Da der Träger A abgeschlossen unter f ist, ist die Menge der Schnittbildung stets nichtleer, sodass 〈  B  〉 immer definiert ist. Die Menge 〈  B  〉 ist die kleinste unter der Operation f abgeschlossene Obermenge von B (Übung).

Beispiel

Sei G eine Gruppe und B ⊆ G beliebig. Sei U der Abschluss von B ∪ { e } unter der Operation g : G² → G mit

g(a, b) = a ∘ b⁻¹ für alle a, b  ∈  G.

Dann ist U die kleinste Untergruppe von G mit U ⊇ B (nach dem Untergruppenkriterium). Alternativ kann U als Durchschnitt aller Untergruppen H von G mit H ⊇ B definiert werden. Die Untergruppe U heißt die von B erzeugte Untergruppe. Sie wird mit 〈 B 〉_G oder kurz 〈 B 〉 bezeichnet.

Die rekursive Definition des Abschlusses

Die Schnitt-Definition des Abschlusses ist elegant und auch in vielen Beweisen nützlich, aber der Aufbau der Menge 〈  B  〉 wird nicht besonders klar. Anders ist dies bei der folgenden äquivalenten Konstruktion des Abschlusses „von unten“:

Satz (rekursive Konstruktion des Abschlusses)

Sei f : Aⁿ → A, und sei B ⊆ A. Weiter seien B₀ = B und

B_k + 1 = B_k ∪ f [ B_kⁿ] = B_k ∪ { f(a₁, …, a_n) | a₁, …, a_n  ∈  B_k } für alle k  ∈  ℕ.

Dann ist 〈 B 〉 = ⋃_{k  ∈  ℕ} B_k.

Beweis

Sei B* = ⋃_{k  ∈  ℕ} B_k. Seien a₁, …, a_n  ∈  B*. Nach Konstruktion gilt

B₀ ⊆ B₁ ⊆ … ⊆ B_k ⊆ …,

sodass ein k mit a₁, …, a_n  ∈  B_k existiert. Dann ist f(a₁, …, a_n)  ∈  B_k + 1 ⊆ B*. Damit ist Menge B* abgeschlossen unter f, sodass 〈  B  〉 ⊆ B*.

Für die umgekehrte Inklusion sei C ⊇ B unter f abgeschlossen. Eine Induktion nach k zeigt, dass B_k ⊆ C für alle k ≥ 0. Folglich ist B* ⊆ 〈  B  〉 nach der Schnitt-Definition des Abschlusses. Insgesamt gilt 〈  B  〉 = B*.

Für eine zweistellige assoziative Operation können wir den Abschluss von B auch in der Form

〈  B  〉 = B ∪ BB ∪ BBB ∪ … = ⋃_n ≥ 1 Bⁿ = { a₁ ∘ … ∘ a_n | n ≥ 1, a_i  ∈  B }

darstellen. Ist die Struktur ein Monoid und e  ∈  B, so gilt B ⊆ BB ⊆ BBB ⊆ …, sodass wir auch hier eine schrittweise Annäherung „von unten“ erreichen. Im Vergleich zur Konstruktion des Satzes ist diese Annäherung langsamer, da zum Beispiel a⁴  ∈  B₂, während im Allgemeinen lediglich a⁴  ∈  B⁴ gilt.

Beispiele

(1)	Sei S die Nachfolgerfunktion auf ℤ mit S(a) = a + 1 für alle a  ∈  ℤ. Dann gilt für B = B₀ = { −2, 1 }: B₁ = { −2, −1, 1, 2 }, B₂ = { −2, −1, 0, 1, 2, 3 }, B₃ = { −2, …, 4 }, … Insgesamt ergibt sich 〈 −2, 1 〉 = { −2, −1, 0, … }.

(2)	Seien f : A → A, a₀  ∈  A und (a_n)_{n  ∈  ℕ} der Orbit von a₀ unter f, sodass a_n + 1 = f (a_n) für alle n. Dann ist 〈  a₀  〉 = { a_n \| n  ∈  ℕ }. Für die rekursive Konstruktion des Abschlusses gilt B_n = { a₀, …, a_n } für alle n  ∈  ℕ.

(3)	Ist f : A → A und { b₁, …, b_n } ⊆ A, so gilt 〈  b₁, …, b_n  〉 = 〈  b₁  〉 ∪ … ∪ 〈  b_n  〉. Allgemein ist 〈  B  〉 = ⋃_{b  ∈  B} 〈  b  〉.

Für Transformationen lässt sich der Abschluss mit Hilfe von Orbits also einfach beschreiben. Für zweistellige Operationen ist der Abschluss komplizierter. Veranschaulichen lässt er sich durch die rekursive schrittweise Erweiterung B₀, B₁, B₂, … wie im obigen Satz oder im assoziativen Fall durch die Darstellung 〈  B  〉 = ⋃_n ≥ 1 Bⁿ. Wir erhalten eine Schichtung der Elemente des Abschlusses nach dem „Zeitpunkt des Findens“: Für jedes a  ∈  〈  B  〉 sind

g(a) = min_n ≥ 0 a  ∈  B_n bzw. h(a) = min_n ≥ 0 a  ∈  Bⁿ

Maße dafür, wie weit das Element a von der Menge B entfernt ist.

Der Abschluss 〈 B 〉 einer Menge B = B₀ unter ∘. Es gilt

a  ∈  B₁ − B₀, b  ∈  B₂ − B₁, a ∘ b  ∈  B₃ − B₂.