Definitions and Propositions pdf
Part B: Universal 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 - Modular Lattice
A lattice (L, ∨, ∧) is called modular if, for all x, y, z ∈ L, it satisfies the following implication:
| (M) | x ≥ z → x ∧ (y ∨ z ) = (x ∧ y) ∨ (x ∧ z ) |
Remark B.5 - Distributive and Modular Lattices
L is modular if and only if it satisfies (D1) in special cases; hence, every distributive lattice is 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 - Meet- und Join-Pseudokomplement
Sei (L, ∨, ∧) ein Verband mit 0 und 1. Dann heisst x∗ ∈ L das Meet-Pseudokomplement von x, falls x∗ = max{y ∈ L: y ∧ x = 0} gilt.
Analog heisst x★ ∈ L das Join-Pseudokomplement von x, falls x★ = min{y ∈ L : y ∨ x = 1} gilt.
L heisst meet-pseudokomplementiert resp. join-pseudokomplementiert, falls jedes Element x ∈ L ein Meet- resp. Join-Pseudokomplement besitzt.
In der AWB werden für die Pseudokomplemente meist die Abkürzungen Meet-Komplement und Join-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.
Remark B.10 - Komplementbehauptung
Sei (B, ∨, ∧, ', 0, 1) eine Boolesche Algebra. Für jedes x ∈ B fallen das Meet-Pseudokomplement, das Join-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 pseudokomplementierten Halbverbandes S (kurz: PCS (pseudo-complemented semilattice, 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.
Proposition B.16 - Unteralgebrenverband
Für jede Algebra A ist (SubA, ∨, ∧) ein Verband (der Unteralgebrenverband von A).