Äquivalenzrelationen

 In der Mathematik tauchen häufig Situationen auf, in denen Objekte, die sich nur in als unwesentlich betrachteten Eigenschaften unterscheiden, einander gleichgestellt werden. Kommt es uns zum Beispiel nur auf den ganzzahligen Rest der Division einer natürlichen Zahl durch 7 an, so betrachten wir die Zahlen 4, 11, 18, … als äquivalent, oder, wie man in diesem Fall sagt, als kongruent modulo 7. Derartige Gleichstellungen sind mathematisch von großer Bedeutung, denn sie sind das Ergebnis von Abstraktionsvorgängen. Wenn wir abstrahieren, sehen wir von bestimmten Merkmalen der betrachteten Objekte ab (das lateinische „abstrahere“ bedeutet „absehen von, wegnehmen“). Nach diesem Abstreifen von gewissen Eigenschaften sind zwei Objekte a und b, die sich nur in diesen Eigenschaften unterscheiden, gleichwertig und austauschbar geworden − vorausgesetzt, unsere weiteren Betrachtungen kehren nicht zu den vergessenen Merkmalen zurück.

 Auch außerhalb der Mathematik ist diese Form der Gleichstellung nicht unbekannt. Unsere zyklische Einteilung der Wochentage entspricht dem oben erwähnten Rechnen „modulo 7“. Weiter sagen wir zum Beispiel: „Sie fahren das gleiche Auto wie ich“. Dabei meinen wir den Typ des Autos, auf das Nummernschild kommt es uns dabei nicht an. Eine Antwort könnte sein: „Ja, wenn man von der Farbe absieht“. Der Angesprochene äußert damit ein etwas feineres Verständnis von „gleiches Auto“, das vom Merkmal der Farbe nicht absehen will. Allgemein kennt unsere Umgangssprache den feinen Unterschied zwischen „das Gleiche“ und „dasselbe“. Man kann im Restaurant das gleiche Essen bestellen wie der Nachbar, nicht aber dasselbe. (In der Mathematik wird diese Unterscheidung vermieden, „gleich“ und „identisch“ werden hier synonym verwendet und mit dem Zeichen „=“ ausgedrückt.)

 Auch Klassifikationen kennen wir aus dem Alltag: Wir teilen auf in Männer und Frauen, in Kinder, Berufstätige und Rentner, in Selbständige und Arbeitnehmer, in Notenstufen von „sehr gut“ bis „ungenügend“. Jeden Klassifizierungsvorgang können wir auch als Abstraktionsvorgang auffassen. Wenn wir zum Beispiel von der individuellen Person absehen und uns nur für ihr Geschlecht interessieren, so erhalten wir eine Klasseneinteilung einer betrachteten Gruppe in Männer und Frauen. Umgekehrt führt jede Klassifikation zu einer Abstraktion, indem genau diejenigen Objekte einander gleichgestellt werden, die einer gemeinsamen Klasse angehören.

 Mathematisch wird der Abstraktionsvorgang durch den Begriff der Äquivalenzrelation und der Begriff der Klassifikation durch den Begriff der Zerlegung einer Menge gefasst. Beide Begriffe hängen, wie obige informale Diskussion schon andeutet, eng miteinander zusammen.

 Wir beginnen mit dem Äquivalenzbegriff. Er versammelt genau die Eigenschaften, die wir von jedem Abstraktionsvorgang erwarten dürfen:

 Ist ∼ eine Äquivalenzrelation auf A, so setzen wir für alle Elemente a von A:

Damit setzen wir dann:

 Eine Äquivalenzklasse a/∼ ist also eine nichtleere Teilmenge von A, und die Faktorisierung A/∼ ist ein Mengensystem auf A. Die wesentlichen Eigenschaften dieser Objekte sind:

 Eine Äquivalenzrelation auf A teilt also die Menge A in gewisse nichtleere und paarweise disjunkte „Bereiche“ oder „Regionen“ ein (die Äquivalenzklassen der Relation). Die Faktorisierung ist die Menge all dieser Bereiche. Elemente, die demselben Bereich angehören, sehen wir als gleichwertig an. Eine Äquivalenzrelation ist damit wie gewünscht eine „unscharfe“ oder „vergröberte“ mathematische Gleichheit.

 Wir diskutieren nun noch den engen Zusammenhang zwischen Gleichsetzungen und Klassifikationen. Hierzu definieren wir:

 Eine Zerlegung von A ist also ein System von nichtleeren und paarweise disjunkten Mengen derart, dass jedes Element von A in einem (und folglich genau einem) Element der Zerlegung vorkommt.

 Nach den obigen Eigenschaften (i) − (iii) ist für jede Äquivalenzrelation ∼ auf A die Faktorisierung A/∼ eine Zerlegung von A. Ist nun 𝒵 eine beliebige Zerlegung von A, so setzen wir für alle a, b  ∈  A:

a ∼_𝒵 b,  falls  „es gibt ein Z  ∈  𝒵 mit a, b  ∈  Z“.

Es ist leicht zu sehen, dass ∼_𝒵 eine Äquivalenzrelation auf A ist. Zudem liefert die Faktorisierung wieder die ursprüngliche Zerlegung, d. h. es gilt A/∼_𝒵 = 𝒵.

 In der Faktorisierung A/∼ = { a/∼ | a  ∈  A } tauchen im Allgemeinen die „Beiträge“ a/∼ der Mengenkomprehension mehrfach auf. Gilt a ∼ b, so ist a/∼ = b/∼ und wir können die Komprehension z. B. auch ohne b durchführen. Diese Beobachtung führt uns zur Frage der „minimalen Erzeugung“ von A/∼. Hierzu definieren wir:

 Für ein vollständiges Repräsentantensystem S gilt also:

Die Menge S ist also ein minimaler Erzeuger der Faktorisierung A/∼.

 In vielen Fällen lässt sich ein vollständiges Repräsentantensystem einfach finden. So ist zum Beispiel 0, 1, …, 5, 6 ein derartiges System für das Rechnen modulo 7. Manchmal ist ein vollständiges Repräsentantensystem allerdings nicht zu sehen. Ein Beispiel ist die sog. Vitali-Äquivalenzrelation auf den reellen Zahlen, die definiert wird durch

x ∼ y,  falls  „der Abstand zwischen x und y ist rational“.

 In der Tat ist der Satz, dass jede Äquivalenzrelation ein vollständiges Repräsentantensystem besitzt, ein Axiom der Mathematik. (Er ist elementar äquivalent zum sog. Auswahlaxiom.) Damit hat uns der Begriff der Äquivalenzrelation schon zu Fragen geführt, die die Grundlagen der Mathematik betreffen.

 Wir betrachten zur Illustration und Visualisierung der Begriffe eine Zerlegung 𝒵 einer Menge A in sieben nichtleere Teilmengen:

 Es gilt also 𝒵 = { A₁, …, A₇ }, ⋃ 𝒵 = A₁ ∪ … ∪ A₇ = A, A_i ≠ ∅ für alle i und A_i ∩ A_j = ∅ für alle i ≠ j.

 Weiter sei ∼ die durch die Zerlegung 𝒵 definierte Äquivalenzrelation ∼ auf A, d. h. wir setzen für alle a, b  ∈  A:

a ∼ b,  falls  „es gibt ein 1 ≤ i ≤ 7 mit a, b  ∈  A_i“.

Dann gilt

A/∼  =  𝒵  =  { A₁, …, A₇ },

d. h. die Faktorisierung A/∼ ist gerade wieder die Zerlegung 𝒵.

 Zur Bildung eines vollständigen Repräsentantensystems wählen wir aus jedem „Land“ der Zerlegung genau einen „Bewohner“ aus:

Für jede solche Wahl a₁  ∈  A₁, …, a₇  ∈  A₇ ist die Menge { a₁, …, a₇ } ⊆ A ein vollständiges Repräsentantensystem unserer Äquivalenzrelation. Es gilt a_i/∼ = A_i für alle i, also A/∼  =  { a₁/∼,  …,  a₇/∼ }.