Mathematische Grundlagen

Definition:  Sei M eine Menge. Eine Verknüpfung auf M ist eine Abbildung

 •   :  M × M → M,

die je zwei Elementen a, b ∈ M ein Element c ∈ M zuordnet. Die Schreibweise ist

a • b  =  c.

Definition:  Eine Ver­knüpfungstafel ist eine Tabelle, die für alle Elemente a, b ∈ M das Ergebnis der Verknüpfung a • b in Zeile a und Spalte b enthält.

Beispiel:  Sei M die Menge 𝔹 = {0, 1}. Auf 𝔹 sei eine Verknüpfung ⊕ in folgender Weise definiert:

Das Ergebnis von 1⊕0 beispiels­weise ergibt sich als Eintrag in Zeile 1 und Spalte 0, nämlich als 1⊕0 = 1.

Beispiel:  Die Menge M sei die Menge ℕ der natürlichen Zahlen. Dann sind + (Addition), · (Multi­plikation) und "hoch" (Potenzierung) Ver­knüpfungen.

Welche Zahl das Ergebnis der Verknüpfung etwa von 5 + 3 oder von 7·4 oder von 2³ ist, müssen wir im Allgemeinen ausrechnen (um 3 weiterzählen von 5 aus, die 7 viermal addieren, bzw. die 2 dreimal mit sich selbst multi­plizieren). Schneller geht es, wenn wir die Ver­knüpfungstafeln der einstelligen Zahlen auswendig lernen (z.B. kleines Einmaleins). Für die Verknüpfung von größeren Zahlen gibt es die Rechen­verfahren der Arithmetik (Kopfrechnen, schrift­liches Addieren und Multi­plizieren).

Definition:  Sei M eine Menge mit einer Verknüpfung  • . Die Verknüpfung  •  heißt kommutativ, wenn für alle Elemente a, b ∈ M gilt

a • b  =  b • a.

Beispiel:  Die oben angegebenen Ver­knüpfungen ⊕, + und · sind kommutativ. Die Verknüpfung "hoch" ist jedoch nicht kommutativ, denn es ist z.B. 2³ = 8, aber 3² = 9.

Definition:  Sei M eine Menge mit einer Verknüpfung  • . Die Verknüpfung  •  heißt assoziativ, wenn für alle Elemente a, b, c ∈ M gilt

(a • b) • c  =  a • (b • c).

Beispiel:  Die oben angegebenen Ver­knüpfungen ⊕, + und · sind assoziativ. Die Verknüpfung "hoch" ist jedoch nicht assoziativ, denn es ist z.B. (2²)³ = 4³ = 64, aber 2⁽²³⁾ = 2⁸ = 256.

Aufgabe 1:  Sei M die Menge ℤ der ganzen Zahlen. Welche Eigen­schaften hat die Verknüpfung "–"  (Subtraktion)?

assoziativ   ja   nein   kommutativ   ja   nein

Definition:  Eine Menge mit einer assoziativen Verknüpfung ist eine Halbgruppe.

Beispiel:  Sei A ein Alphabet und A⁺ die Menge der nichtleeren Wörter über dem Alphabet. Auf A⁺ sei die Verkettung von Wörtern als Verknüpfung  •  definiert. Zwei Wörter werden verkettet, indem sie einfach hintereinander geschrieben werden, z.B.

ab  •  aacc = abaacc.

Die Verknüpfung ist offen­sichtlich assoziativ. Die Menge A⁺ mit der Verkettung als Verknüpfung bildet daher eine Halbgruppe.

Die Menge der natürlichen Zahlen mit der Addition (ℕ, +) ist eine Halbgruppe. Ebenso ist (ℕ, ·) eine Halbgruppe.

Definition:  Eine Halbgruppe (M,  • ) ist ein Monoid, wenn sie ein neutrales Element enthält. Ein Element e ∈ M heißt neutrales Element, wenn für alle a ∈ M gilt

e • a  =  a • e  =  a.

Das neutrale Element wird auch als Nullelement oder als Einselement bezeichnet, je nach dem, ob die Verknüpfung als Addition oder als Multi­plikation verstanden wird.

Beispiel:  Die Menge A* der Wörter über einem Alphabet A (einschließ­lich des leeren Wortes ε) mit der Verkettung als Verknüpfung ist ein Monoid. Das leere Wort ε ist das neutrale Element, denn es gilt

ε • w  =  w • ε  =  w   für alle Wörter w ∈ A*.

Sei X eine Menge und ℘(X) die Potenzmenge von X, d.h. die Menge aller Teilmengen von X. Dann ist ℘(X) mit der Vereinigung von Mengen  ∪  als Verknüpfung und der leeren Menge  ∅  als neutralem Element ein Monoid.

Die Menge der natürlichen Zahlen mit der Multi­plikation (ℕ, ·) ist ein Monoid mit der 1 als neutralem Element. Die Menge der natürlichen Zahlen einschließ­lich der Null mit der Addition (ℕ₀, +) ist ein Monoid. Die Null ist das neutrale Element bezüglich der Addition. Ferner ist (𝔹, ⊕) ein Monoid mit der 0 als neutralem Element.

Satz:  Sei (M,  • ) ein Monoid. Dann ist das neutrale Element eindeutig bestimmt, d.h. es gibt nicht mehrere neutrale Elemente in (M,  • ).

Beweis:  Seien e und f neutrale Elemente. Dann gilt

f  =  e • f  =  e,

denn f  =  e • f, weil e neutral ist, und e • f  =  e, weil f neutral ist.

Definition:  Ein Monoid (M,  • , e) ist eine Gruppe, wenn es zu jedem Element a ∈ M ein inverses Element in M gibt. Ein Element a' ∈ M heißt invers zu a ∈ M, wenn

a • a'  =  e

ist, d.h. wenn die Verknüpfung von a und a' das neutrale Element e ergibt.

Beispiel:  Die Menge der ganzen Zahlen mit der Addition (ℤ, +, 0) ist eine Gruppe. Zu jeder Zahl a ist -a das inverse Element.

Die Menge (𝔹, ⊕, 0) ist eine Gruppe. Die 0 und die 1 sind jeweils zu sich selbst invers.

Satz:  Sei (M,  • , e) eine Gruppe. Für jedes a ∈ M gilt: wenn a' zu a invers ist, dann auch a zu a'.

Beweis:  Sei zunächst a'' das zu a' inverse Element, d.h. a' • a'' = e. Dann ist

d.h. a = a'' ist zu a' invers.

Definition:  Eine Gruppe (M,  • , e) heißt abelsche Gruppe (nach N.H. Abel), wenn die Verknüpfung  •  kommutativ ist, d.h. wenn für alle Elemente a, b ∈ M gilt

a • b  =  b • a.

Beispiel:  (ℤ, +, 0) ist abelsche Gruppe.

Die additive Gruppe modulo n (ℤ_n, +_n, 0) ist eine abelsche Gruppe. Die Menge ℤ_n besteht aus den ganzen Zahlen 0, ..., n-1. Die Verknüpfung +_n bezeichnet die Addition modulo n.

Die multi­plikative Gruppe modulo n (ℤ_n*, ·_n, 1) ist eine abelsche Gruppe. Die Menge ℤ_n* besteht aus allen Elementen von ℤ_n, die teilerfremd zu n sind. Die Verknüpfung ·_n bezeichnet die Multi­plikation modulo n.

Die Menge aller Permutationen von n Elementen mit der Komposition (Hinter­einanderausführung von Abbildungen) als Verknüpfung ist eine Gruppe, jedoch keine abelsche Gruppe.