1.2 Äquivalenzrelationen

Definition (Äquivalenzrelation, Äquivalenzklasse, Repräsentantensystem)

Äquivalenzrelationen

Eine Relation ∼ auf A heißt eine Äquivalenzrelation oder kurz eine Äquivalenz, falls ∼ reflexiv, symmetrisch und transitiv ist. Gilt a ∼ b für a, b  ∈  A, so sagen wir, dass a und b äquivalent (bzgl. ∼) sind.

Äquivalenzklassen und Faktorisierung

Wir setzen

a/∼ = { b  ∈  A | a ∼ b } für alle a  ∈  A, (Äquivalenzklasse von a, a modulo ∼)

A/∼ = { a/∼ | a  ∈  A }. (Faktorisierung, A modulo ∼)

Repräsentanten und Repräsentantensysteme

Gilt b ∼ a, so heißt b ein Repräsentant der Äquivalenzklasse a/∼. Eine Menge B ⊆ A heißt ein (vollständiges) Repräsentantensystem für die Äquivalenz ∼, falls es für alle a  ∈  A genau ein b  ∈  B mit a ∼ b gibt.

Die Kongruenz modulo 3 auf ℤ besitzt drei Äquivalenzklassen. Die Mengen { 0, 1, 2 } und { 0, −2, 8 } sind zwei Beispiele für vollständige Repräsentantensysteme.

Eine Äquivalenzrelation bringt eine „Ähnlichkeit“, „Gleichwertigkeit“, „Gleichheit in bestimmter Hinsicht“ zum Ausdruck. Sie beschreibt das Absehen von als unwesentlich erachteten Eigenschaften und damit das Abstrahieren. Die Begriffsbildung ist die „Abstraktion der Abstraktion“.

Das Trio „reflexiv, symmetrisch, transitiv“ lässt sich durch die Eigenschaften der Gleichheit motivieren. Denn für alle a, b, c gilt

a = a, a = b impliziert b = a,

a = b und b = c impliziert b = c.

Notationen

(1)	Statt a/∼ schreibt man auch [ a ]_∼ oder auch nur [ a ], wenn ∼ aus dem Kontext heraus klar ist. Daneben ist auch a für [ a ] üblich.

(2)	Äquivalenzrelationen können auch mit R, S, … bezeichnet werden. Meistens werden jedoch Zeichen wie ∼, ∼*, ≈, ≡ , ≃, ≅ verwendet, die an das Gleichheitssymbol = erinnern.

Die Faktorisierung A/∼ ist ein Mengensystem. Jedes Element a/∼ von A/∼ ist eine Teilmenge von A und damit gilt A/∼ ⊆ ℘(A). Es gilt

(#) a/∼ ≠ ∅; a/∼ ∩ b/∼ = ∅ genau dann, wenn non(a ∼ b); ⋃ A/∼ = A.

Wie die Menge der Schüler einer Schule in Schulklassen zerfällt, so zerfällt A in Äquivalenzklassen. Weitere Alltagsbeispiele sind die Einteilung von Kleidungsstücken in die Größenklassen XS, S, M, L, XL, die Zustandsbeschreibungen „neu, wie neu, gebraucht, akzeptabel“, die Einteilung der Welt in Länder und jede Form der Teambildung im Sport.

Die drei Eigenschaften in (#) besagen, dass 𝒜 = A/∼ eine Zerlegung der Menge A bildet (vgl. 0. 4). Ist umgekehrt 𝒜 eine Zerlegung von A, so definiert

a ∼ b, falls es gibt ein A  ∈  𝒜 mit a, b  ∈  A für alle a, b  ∈  A

eine Äquivalenzrelation auf A mit A/∼ = 𝒜. Damit gilt:

Äquivalenzrelationen und Zerlegungen entsprechen einander.

Wählen wir aus jeder Äquivalenzklasse a/∼ genau ein Element aus und fassen wir die ausgewählten Elemente zu einer Menge B ⊆ A zusammen, so erhalten wir ein Repräsentantensystem (vgl. 1.11 zu „wählen“). Im Schulbeispiel: Klassensprecherversammlung.

Beispiele

(1)

Für alle m ≥ 1 ist die Kongruenz ≡ _m eine Äquivalenz auf ℤ (vgl. 1.1). Wir schreiben kurz [ a ]_m oder [ a ] statt a/≡ _m und ℤ_m statt ℤ/≡ _m. Für m = 3 gilt

[ 0 ] = [ 3 ] = [ −3 ] = … = { …, −6, −3, 0, 3, 6, … },

[ 1 ] = [ 4 ] = [ −2 ] = … = { …, −5, −2, 1, 4, 7, … },

[ 2 ] = [ 5 ] = [ −1 ] = … = { …, −4, −1, 2, 5, 8, … }.

Die Menge { 0, 1, 2 } ist ein Repräsentantensystem. Man nennt es „kanonisches“ oder „Standard-Repräsentantensystem“, da sich 0, 1, 2 bei Division durch 3 als Reste anbieten. Aber auch { 0, −1, −2 } und { 3, 7, −7 } sind prinzipiell gleichwertige Repräsentantensysteme. Es gilt

ℤ₃ = ℤ/≡ ₃ = { [ a ] | a  ∈  ℤ } = { [ 0 ], [ 1 ], [ 2 ] } = { [ 0 ], [ −1 ], [ −2 ] } usw.

(2)	Die geometrische Kongruenz (Deckungsgleichheit) zweier Teilmengen A, B der Ebene ℝ² ist eine Äquivalenz auf ℘(ℝ²) = { A \| A ⊆ ℝ² }. Ebenso ist die Ähnlichkeit von Dreiecken eine Äquivalenz auf der Menge aller Dreiecke.

(3)	Die Relation ∼ = { (a, a) \| a  ∈  A } ist eine Äquivalenzrelation auf A (Motto: „Jeder ist anders.“, „Einzelunterricht“). Es gilt a/∼ = { a } für alle a  ∈  A und A/∼ = { { a } \| a  ∈  A }. Die Menge A ist das einzige Repräsentantensystem.

(4)	Die Relation ∼ = { (a, b) \| a, b  ∈  A } = A² ist eine Äquivalenz auf A (Motto: „Alle sind gleich.“, „Dorfschule mit einer Klasse“). Es gilt a/∼ = A für alle a  ∈  A und A/∼ = { A }. Für alle a  ∈  A ist { a } ein Repräsentantensystem.