Kongruenzrelationen

Sei A eine Menge und ≡ eine Äquivalenz auf A. Ist nun f : A → A eine Funktion, so stellt sich die Frage, ob die Funktion f die Äquivalenzklassenbildung [ a ] im folgenden Sinne „mitmacht“ oder „respektiert“:

Wird durch [ a ] ↦ [ f (a) ] für alle a  ∈  A eine Funktion F : A/≡ → A/≡ definiert?

Weniger formal:

Kann f auch als Funktion auf den Äquivalenzklassen aufgefasst werden?

Macht f die Abstraktion von A zu A/≡ mit?

Wegen

[ a ] ↦ [ f (a) ] und [ b ] ↦ [ f (b) ]

muss im Fall [ a ] = [ b ] auch stets [ f (a) ] = [ f (b) ] gelten, aufgrund der Eindeutigkeit eines Funktionswerts. Diese Bedingung ist aber gleichwertig zu

Für alle a, b  ∈  A gilt: a ≡ b impliziert f (a) ≡ f (b).

Diese Überlegungen motivieren:

Definition (Kongruenzrelation für einstellige Operationen)

Seien ≡ eine Äquivalenz auf A und f : A → A. Dann heißt ≡ eine Kongruenzrelation oder kurz Kongruenz für f, falls gilt:

∀a, b  ∈  A (a ≡ b → f (a) ≡ f (b))(Kongruenzbedingung)

In diesem Fall heißt die Funktion F : A/≡ → A/≡ mit

F([ a ]) = [ f (a) ] für alle a  ∈  A

die durch f definierte oder induzierte Operation auf der Faktorisierung A/≡ .

Statt

„Die Äquivalenz ≡ ist eine Kongruenz für die Operation f“

sagen wir gleichwertig auch

„Die Operation f respektiert die Äquivalenz ≡ “,

je nachdem, ob wir die Relation oder die Operation betonen möchten.

Zur Definition von F durch „F([ a ]) = [ f (a) ]“ wird auf der rechten Seite ein Repräsentant a der Äquivalenzklasse und nicht die Äquivalenzklasse [ a ] verwendet. Die Kongruenzbedingung stellt sicher, dass der Wert [ f (a) ] nicht von der Wahl von a abhängt. Wir sagen hierzu auch, dass F wohldefiniert ist oder dass die Definition von F unabhängig von der Wahl der Repräsentanten ist. Die Kongruenzbedingung ist immer zu überprüfen, wenn eine Funktion auf der Faktorisierung durch Verwendung von Repräsentanten eingeführt wird.

Die Kongruenzbedingung lässt sich anschaulich visualisieren:

Eine Operation f auf A erfüllt die Kongruenzbedingung, wenn alle Elemente einer Äquivalenzklasse nach Anwendung von f in einer gemeinsamen Äquivalenzklasse landen (möglicherweise der alten). Die Operation f muss weder injektiv noch surjektiv sein.

Für die in der Algebra besonders wichtigen zweistelligen Operationen können wir analoge Überlegungen durchführen. Wir definieren:

Definition (Kongruenzrelation für zweistellige Operationen)

Seien ≡ eine Äquivalenz auf A und f : A × A → A. Dann heißt ≡ eine Kongruenzrelation für f, falls gilt:

∀a, b, c, d  ∈  A (a ≡ c ∧ b ≡ d → f(a, b) ≡ f(c, d))(Kongruenzbedingung)

In diesem Fall heißt die Funktion F : A/≡ × A/≡ → A/≡ mit

F([ a ], [ b ]) = [ f(a, b) ] für alle a, b  ∈  A

die durch f definierte oder induzierte Operation auf A/≡ .

Vollkommen analog können Kongruenzrelationen für beliebige n-stellige Operationen f : Aⁿ → A definiert werden.

Die zweistellige Kongruenzbedingung können wir in eine einfache und suggestive Form bringen, wenn wir die Operation als Verknüpfung notieren, wie wir es von den Operationen + und · gewohnt sind. Bezeichnen wir die Operation mit ∘ und schreiben wir a ∘ b statt ∘(a, b), so besagt die Kongruenzbedingung, dass durch die Setzung

[ a ] ∘ [ b ] = [ a ∘ b ] für alle a, b  ∈  A

eine Operation auf den Äquivalenzklassen, die wir der Einfachheit halber ebenfalls wieder mit ∘ bezeichnen, definiert werden kann.

Beispiele

Sei m ≥ 1, und sei ≡ = ≡ _m die Kongruenz modulo m.

(1)

Die Addition + : ℤ × ℤ → ℤ respektiert die Äquivalenz ≡ , denn für alle ganzen Zahlen a, b, c, d gilt:

(+) a ≡ b ∧ c ≡ d → a + c ≡ b + d.

Damit können wir eine Addition auf ℤ_m = { [ 0 ], …, [ m − 1 ] } erklären:

[ a ] + [ b ] = [ a + b ] für alle a, b  ∈  ℤ.

Diese Addition ist wohldefiniert: Für alle a, b hängt der Wert [ a + b ] aufgrund der Gültigkeit der Kongruenzbedingung (+) nicht von der Wahl der Repräsentanten a und b der Klassen [ a ] bzw. [ b ] ab. Analoges gilt für die Multiplikation. Die Äquivalenz ≡ ist also eine Kongruenzrelation sowohl für die Addition als auch für die Multiplikation auf ℤ.

Visualisierung der zweistelligen Kongruenzbedingung für die Multiplikation auf ℤ und die Kongruenz ≡ ₅. Die Zahlen werden modulo 5 eingefärbt. Die Kongruenzbedingung besagt, dass Paare mit der gleichen Farbkombination stets auf die gleiche Farbe abgebildet werden.

Zwei Darstellungen der Wertetafel der induzierten Multiplikation auf ℤ₅.

Links wurden die durch die Multiplikation auf ℤ gegebenen Repräsentanten der Äquivalenzklassen verwendet, rechts die kanonischen Repräsentanten.

(2)

Sei sgn : ℤ → ℤ mit sgn(a) = 1 für a > 0, sgn(0) = 0 und sgn(a) = − 1 für a < 0 die Signum- oder Vorzeichenfunktion auf ℤ. Im Fall m ≥ 2 ist ≡ keine Kongruenzrelation für sgn. Denn es gilt 0 ≡ m, aber

sgn(0) = 0 ≢ 1 = sgn(m).

Damit kann die Signumfunktion für m ≥ 2 nicht auf der Faktorisierung ℤ/≡ erklärt werden. Im Fall m = 1 ist die Kongruenzbedingung erfüllt. Wir können hier setzen: sgn([ a ]) = [ 1 ] (= [ 0 ]) für alle a  ∈  ℤ, was aber nicht als Vorzeichenfunktion überzeugt. Wir können also zusammenfassen: Restklassen können wie ganze Zahlen addiert und multipliziert werden, sie erben aber von den ganzen Zahlen kein Vorzeichen.

Die Sprechweise, dass ein mathematisches Objekt wohldefiniert ist, ist auch in anderen Kontexten nützlich. Sie besagt letztendlich nur, dass eine korrekte mathematische Definition vorliegt. So ist zum Beispiel

„f : ℕ → ℕ mit f (n) = n/2 für alle n“

nicht wohldefiniert, da n/2 für ungerade Zahlen kein Element des angegebenen Wertevorrats ℕ ist. Definieren wir eine Funktion g : A → B durch

g(a) = „das eindeutige b  ∈  B mit der Eigenschaft ℰ(a, b)“ für alle a  ∈  A,

so ist dies nur dann wohldefiniert, wenn tatsächlich für alle a genau ein b  ∈  B mit ℰ(a, b) existiert. Dies muss vor oder unmittelbar nach der Definition bewiesen werden.