Definitionen und Sätze pdf
Part B: Universelle Algebra 1
Viele Hilfsmittel, welche die AWB zur Verfügung stellt, befassen sich mit Begriffen der Universellen Algebra. Deshalb sollen im folgenden Abschnitt die wichtigsten mathematischen Grundlagen aus diesem Gebiet erwähnt werden.
Unter einem Typ von Algebren versteht man ein geordnetes Paar (F, σ), wobei F eine Menge ist, deren Elemente Operationssymbole genannt werden, und σ :F → ℕ ∪ {0} eine Abbildung, die jedem f in F die Stelligkeit σ(f) zuordnet.
Man nennt f dann σ(f)-stelliges Operationssymbol.
Eine allgemeine Algebra (kurz: Algebra) vom Typ (F, σ) ist ein geordnetes Paar A = (A, F), bestehend aus einer Menge A und einer Menge F = (fA : f ∈ F) von Operationen auf A, wobei jedem Operationssymbol f ∈ F eine σ(f)-stellige Operation fA ∈ Op(A) zugeordnet wird.
Die Menge A heisst die Grundmenge von A, und die Elemente von F heissen fundamentale Operationen von A.
Eine Gruppe kann zum Beispiel als eine Algebra (G, *) vom Typ (2) oder eine Algebra (G, *, -1, e) vom Typ (2,1,0) verstanden werden. In ähnlicher Weise lassen sich nun natürlich auch Gruppoide, Halbgruppen oder Monoide definieren. Es ist jeweils zu überlegen, welche Operationen mit welchen Stelligkeiten benötigt werden, um den Typ der herzustellenden Algebra entsprechend anpassen zu können.
Ein weiteres prominentes Beispiel ist der Verband. Eine Möglichkeit, ihn zu definieren, haben wir unter Definition A.10 - Verband schon kennengelernt. Folgende Definition ist mit dieser äquivalent und bietet ein weiteres Beispiel einer Algebra.
Definition B.2 - Verband (cf. also Definition A.10 - Verband)
Ein Verband ist eine Algebra (L, ∨, ∧) vom Typ (2,2), die den folgenden Gleichungen genügt:
| (Kommutativität) | x ∨ y = y ∨ x, x ∧ y = y ∧ x |
| (Assoziativität) | x ∨ (y ∨ z) = (x ∨ y) ∨ z x ∧ (y ∧ z) = (x ∧ y) ∧ z |
| (Idempotenz) | x ∨ x = x, x ∧ x = x |
| (Absorption) | x ∨ (x ∧ y) = x, x ∧ (x ∨ y) = x |
Ein Verband mit 0 und 1 ist eine Algebra (L, ∨, ∧, 0, 1) vom Typ (2,2,0,0) so, dass (L, ∨, ∧) ein Verband ist und zusätzlich folgende Gleichung gilt:
| (0 und 1) | x ∧ 0 = 0, x ∨ 1 = 1 |
Definition B.3 - Distributiver Verband
Ein Verband (L, ∨, ∧) heisst distributiv, falls die folgenden Distributivgesetze erfüllt sind:
| (D1) | x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z) |
| (D2) | x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z) |
Definition B.4 - Modularer Verband
Ein Verband (L, ∨, ∧) ist genau dann modular wenn die folgende Implikation gilt, für alle x, y, z ∈ L:
| (M) | x ≥ z → x ∧ (y ∨ z ) = (x ∧ y) ∨ (x ∧ z ) |
Bemerkung B.5 - Distributive und modulare Verbände
Ein Verband L ist genau dann modular, wenn er in Spezialfällen (D1) erfüllt. Deswegen ist jeder distributive Verband auch modular.
Als letztes Algebra-Beispiel seien die Booleschen Algebren erwähnt. Boolesche Algebren, nach dem Mathematiker George Boole benannt, wurden entwickelt, um in der Aussagenlogik algebraische Methoden anwenden zu können. Die Operationen der Booleschen Algebra simulieren die logischen Operatoren AND, OR und NOT (oder die mengentheoretischen Verknüpfungen Durchschnitt, Vereinigung und Komplement).
Definition B.6 - Boolesche Algebra
Eine boolesche Algebra ist eine Algebra (B, ∨, ∧, ', 0, 1) vom Typ (2,2,1,0,0), falls (B, ∨, ∧) ein distributiver Verband mit 0 und 1 ist und ausserdem für jedes x ∈ B ein x' ∈ B existiert mit:
| (Komplement) | x ∧ x' = 0, x ∨ x' = 1 |
Definition B.7 - Schnitt- und Verein-Pseudokomplement (meet- and join-pseudocomplement
Sei (L, ∨, ∧) ein Verband mit 0 und 1. Dann heisst x∗ ∈ L das Schnitt-Pseudokomplement von x, falls x∗ = max{y ∈ L: y ∧ x = 0} gilt.
Analog heisst x★ ∈ L das Verein-Pseudokomplement von x, falls x★ = min{y ∈ L : y ∨ x = 1} gilt.
L heisst Schnitt-pseudokomplementiert resp. Verein-pseudokomplementiert, falls jedes Element x ∈ L ein Schnitt- resp. Verein-Pseudokomplement besitzt.
In der AWB werden für die Pseudokomplemente meist die Abkürzungen Schnitt-Komplement und Verein-Komplement verwendet.
Sei (L, ∨, ∧) ein Verband mit 0 und 1. Dann heisst x∗ ∈ L ein Komplement von x, falls gilt: x ∧ x∗ = 0 und x ∨ x∗ = 1.
Besitzt jedes Element x ∈ L ein Komplement x∗, so heisst der Verband komplementiert.
Bemerkung B.10 - Komplementbehauptung
Sei (B, ∨, ∧, ', 0, 1) eine Boolesche Algebra. Für jedes x ∈ B fallen das Schnitt-Pseudokomplement, das Verein-Pseudokomplement und das Komplement zusammen.
Der Beweis zu dieser Bemerkung ist in keiner der erwähnten Quellen zu finden. Deshalb haben wir ihn hier aufgeführt: Beweis einer Komplement-Behauptung.
Existiert in einem Poset S für jedes Paar x,y ∈ S das Infimum inf(x,y), dann nennt man S einen Schnitt-Halbverband (kurz: Halbverband).
Das Skelett eines pseudo-complemented semilattice S (short: PCS, p-semilattice) ist die Menge S∗ = {x∗ : x ∈ S} aller Pseudokomplemente von S.
Definition B.13 - Fast rigider PCS
Ein pseudokomplementierter Halbverband S wird fast rigid genannt, falls |End+(S)| = 1 gilt, wobei End+(S) definiert ist durch End+(S) := {φ ∈ Hom(S,S) : φ(S) ⊈ S∗}. In Worten: Der PCS S heisst fast rigid, falls genau ein Endomorphismus (nämlich die Identität) Bildelemente hat, welche nicht im Skelett von S liegen.
Wie für so manche mathematische Struktur dürfen auch von Algebren Unterstrukturen erwarten werden. Sie werden wie folgt definiert:
Definition B.14 - Unteralgebra
Es sei A = (A, F) eine Algebra vom Typ F, und B ⊆ A eine Teilmenge von A mit der Eigenschaft, dass fA(b1,... ,bn) ∈ B für alle f ∈ F und alle n-Tupel (b1,... ,bn) ∈ Bn (σ(f) = n gesetzt).
Die Algebra B = (B, (fB : f ∈ F)) heisst dann Unteralgebra von A, B ≤ A, wobei fB : Bn → B für alle f ∈ F als Einschränkung von fA auf die Menge B definiert ist.
Mit SubA wird die Menge aller Grundmengen von Unteralgebren von A bezeichnet, d.h. SubA = {B : B ≤ A}.
Es sei A eine Algebra. Dann gilt:
- A ∈ SubA,
- ∩ℬ ∈ SubA für jede nichtleere Teilmenge ℬ ⊆ SubA.
Satz B.16 - Unteralgebrenverband
Für jede Algebra A ist (SubA, ∨, ∧) ein Verband (der Unteralgebrenverband von A).