Abgeschlossene Mengen und Unterstrukturen

Wir definieren:

Definition (abgeschlossene Teilmenge)

Sei ∘ : A² → A eine Operation, und sei B ⊆ A. Dann heißt B abgeschlossen unter ∘, falls gilt:

∀a, b  ∈  B a ∘ b  ∈  B(Abgeschlossenheitsbedingung)

Ist allgemein g : Aⁿ → A eine n-stellige Operation auf A mit n ≥ 1, so heißt eine Teilmenge B von A abgeschlossen unter g, falls gilt:

∀a₁, …, a_n  ∈  B g(a₁, …, a_n)  ∈  B(allgemeine Abgeschlossenheitsbedingung)

Das Besondere einer unter ∘ abgeschlossenen Teilmenge B von A ist, dass die Anwendung der Operation auf je zwei Elemente von B nicht aus der Menge B herausführt. Negativ formuliert: B ist genau dann nicht abgeschlossen unter ∘, wenn es a, b  ∈  B gibt mit a ∘ b  ∈  A − B. Mit Hilfe des Mengenprodukts

BC = { b ∘ c | b  ∈  B, b  ∈  C }

können wir die Abgeschlossenheit sehr kompakt formulieren: Eine Teilmenge B von A ist genau dann abgeschossen, wenn gilt

BB ⊆ B.(Abgeschlossenheitsbedingung in Produktform)

Zur Abgeschlossenheit einer Menge B unter ∘: Die Anwendung der Operation auf je zwei Elemente von B führt nicht aus B heraus.

Notation: Einschränkungen von Operationen und Relationen

Ist g : Aⁿ → A eine n-stellige Operation, so schreiben wir g^B für die Einschränkung der Operation g auf Bⁿ, d. h. es gilt g^B = g↾Bⁿ. Analog setzen wir R^B = R ∩ Bⁿ für eine n-stellige Relation R auf A.

Ist B abgeschlossen unter g, so gilt g^B : Bⁿ → B. Für beliebige B ist R^B ⊆ Bⁿ.

Für eine Transformation g : A → A bedeutet die Abgeschlossenheit von B ⊆ A einfach, dass das Bild von B unter g eine Teilmenge von B ist, d. h. g[ B ] ⊆ B. Ist dies der Fall, so verläuft jeder Orbit eines Elements b von B innerhalb von B.

Nach diesen Vorbereitungen definieren wir nun:

Definition (Unterstruktur)

Sei (A, ∘) eine Struktur, und sei B ⊆ A abgeschlossen unter ∘. Dann heißt die Struktur (B, ∘^B) eine Unterstruktur von (A, ∘) und (A, ∘) eine Oberstruktur oder Erweiterung von (B, ∘^B). In Zeichen schreiben wir

(B, ∘^B) ⊆ (A, ∘).

Für allgemeine Strukturen definieren wir:

Definition (Unterstruktur, allgemeiner Fall)

Sei (A, g₁, …, e₁, …, R₁, …) eine Struktur mit Operationen g₁, …, Konstanten e₁, … und Relationen R₁, … (beliebiger Stellenzahl). Weiter sei B ⊆ A abgeschlossen unter allen Operationen und B enthalte alle Konstanten. Dann heißt (B, g₁^B, …, e₁, …, R₁^B, …) eine Unterstruktur der Struktur.

Eine Unterstruktur eines Monoids (M, ∘, e) enthält also per Definition das neutrale Element e. Eine Unterstruktur eines Körpers enthält 0 und 1.

Wir können die auf den ersten Blick vielleicht etwas technische Definition kurz so zusammenfassen:

Eine Unterstruktur erbt die Operationen, Konstanten und Relationen.

Damit das Erben möglich ist, muss die Teilmenge abgeschlossen unter den Operationen sein und alle Konstanten enthalten. Ohne diese Erbschaftsbedingungen würde keine Struktur des betrachteten Typs entstehen. Bei den Relationen werden keine Anforderungen an die Teilmenge gestellt, sie werden einfach zurechtgestutzt. Damit erzeugt zum Beispiel jede Teilmenge B einer partiellen Ordnung (A, <) die Unterstruktur (B, <^B) = (B, < ∩ B²). Analoges gilt für Äquivalenzrelationen und Graphen.

Eine Unterstruktur einer Struktur der Form (A, +, ·, 0, 1): B ist abgeschlossen unter + und · und enthält die Konstanten 0 und 1.

Konvention

(1)	Wir schreiben kurz (B, g₁, …, e₁, …, R₁, …) statt (B, g₁^B, …, e₁^B, …, R₁^B).

(2)	Wir nennen auch B selbst eine Unterstruktur von A (Verwechslung einer Struktur mit ihrem Träger).

Ein instruktives Beispiel ist:

Gerade und ungerade Zahlen

Seien G = { 2n | n  ∈  ℕ } und U = { 2n + 1 | n  ∈  ℕ }.

(1)	G und U sind nicht abgeschlossen unter der Nachfolgerbildung S : ℕ → ℕ auf ℕ mit S(n) = n + 1 für alle n.

(2)	G ist abgeschlossen unter der Addition und Multiplikation auf ℕ, sodass (G, +) und (G, ·) Unterstrukturen von (ℕ, +) bzw. (ℕ, ·) sind.

(3)	U ist nicht abgeschlossen unter +, da zum Beispiel 1 + 1 = 2 kein Element von U ist . Dagegen ist U abgeschlossen unter ·, sodass (U, ·) ⊆ (ℕ, ·).

(4)	Es gilt (G, +, 0) ⊆ (ℕ, +, 0), (U, ·, 1) ⊆ (ℕ, ·, 1). Die Menge G bildet mit der Multiplikation eine Unterstruktur von (ℕ, ·), nicht aber von (ℕ, ·, 1), da 1  ∉  G.

Weitere Beispiele sind:

Beispiele

(1)	Seien g : A → A, a  ∈  A, (a_n)_{n  ∈  ℕ} der Orbit von a unter g und B = { a_n \| n  ∈  ℕ } = { a, g(a), g²(a), … }. Dann ist B abgeschlossen unter der Transformation g.

(2)	Sei g : Aⁿ → A eine n-stellige Operation auf A. Dann sind A und ∅ abgeschlossen unter g.

(3)

Sei M = ^AA das Transformationsmonoid auf einer Menge A. Dann ist die Menge N der injektiven Funktionen in M abgeschlossen unter ∘, da die Komposition zweier Injektionen injektiv ist. Zudem ist id_A  ∈  N. Damit ist also N eine Unterstruktur von (M, ∘, id_A). Das Gleiche gilt für die surjektiven und bijektiven Funktionen in M.

(4)	Unterstrukturen von Unterstrukturen sind Unterstrukturen. Anders formuliert: Die Unterstrukturrelation ist transitiv. So bildet (ℕ, +, ·, 0, 1) ⊆ (ℤ, +, ·, 0, 1) ⊆ (ℚ, +, ·, 0, 1) ⊆ (ℝ, +, ·, 0, 1) ⊆ (ℂ, +, ·, 0, 1) eine Kette von Unterstrukturen.