Äquivalenzrelation

Äquivalenzrelation bezeichnet eine Relation, die die Eigenschaft hat, gleichzeitig reflexiv, symmetrisch und transitiv zu sein.

Die Äquivalenzrelation ist für die Logik und die Mathematik von großer Bedeutung.

• Sie teilt eine Menge restlos in nichtleere und disjunkte (elementfremde) Untermengen, Äquivalenzklassen genannt.
• Die Klassenbildung mit Hilfe des Äquivalenzbegriffes ermöglicht eine mathematische Begriffsbildung.

Äquivalenz – mathematische Gleichwertigkeit

In der Mathematik möchte man in vielen Zusammenhängen Objekte, die sich in gewissen Aspekten ähneln, als gleichwertig ansehen. Eine Formalisierung der Mindestanforderungen an einen solchen Gleichwertigkeitsbegriff ist der Begriff der Äquivalenzrelation.

So ist jeder Begriff, der als die Gleichheit gewisser Eigenschaften definiert werden kann, eine Äquivalenzrelation.

Gleichmächtigkeit endlicher Mengen

zwei endliche Mengen heißen gleichmächtig, wenn sie dieselbe Anzahl von Elementen haben.

Kongruenz in der Geometrie

zwei Dreiecke sind kongruent, wenn sie dieselben Seitenlängen haben.

Ähnlichkeit in der Geometrie

zwei Dreiecke sind ähnlich, wenn sie dieselben Innenwinkel haben;

Kongruenz in der elementaren Zahlentheorie

zwei ganze Zahlen heißen kongruent modulo n, wenn sie bei ganzzahliger Division durch n denselben Rest lassen.

Und letzlich gehört auch die Gleichheit selbst dazu.

Definition einer Äquivalenzrelation

Entscheidungsbaum zum Nachweis von Äquivalenzrelationen

Das Wort „äquivalent“ stehe im Folgenden für eine dieser Beziehungen zwischen zwei Objekten; dass zwei Objekte a und b äquivalent sind, sei durch a ~ b symbolisiert.

Alle diese Begriffe haben die folgenden drei Eigenschaften:

• Reflexivität: a∼a

Jedes Objekt ist zu sich selbst äquivalent.

• Symmetrie: $a\sim b \ \Rightarrow\ b\sim a$

Wenn a zu b äquivalent ist, dann ist auch b äquivalent zu a (und umgekehrt).

• Transitivität: $a\sim b\ \mathrm{und}\ b\sim c\ \Rightarrow\ a\sim c$

Wenn a zu b äquivalent und b zu c äquivalent ist, dann ist a äquivalent zu c.

Jede Beziehung (zwischen Objekten), die diese Eigenschaften hat, heißt Äquivalenzrelation.

Formale Definition

Eine Äquivalenzrelation auf einer Menge M ist eine Teilmenge $R \subseteq M \times M$, welche folgende Bedingungen erfüllt:

• Reflexivität: Für alle $a\in M$ ist $(a,a)\in R$.
• Symmetrie: Für alle $a,b\in M$, für die $(a,b)\in R$ gilt, ist auch $(b,a) \in R$.
• Transitivität: Für alle $a,b,c \in M$ mit $(a,b) \in R$ und $(b,c) \in R$ gilt, dass auch $(a,c) \in R$.

Üblicherweise schreibt man

a∼_Rb oder einfach $a\sim b$ statt $(a,b)\in R,$

und dann nehmen diese Forderungen genau die in der Einleitung genannte Form an.

(Hinweis: Eine Relation auf einer Menge M kann mit der Menge der in dieser Relation stehenden Paare identifiziert werden. Danach ist eine Relation auf M einfach eine Menge solcher Paare, das heißt eine Teilmenge des kartesischen Produktes von M mit sich selbst.)

Anschauliches Beispiel

Menge von acht Buchexemplaren mit eingezeichneter Äquivalenzrelation „x und y besitzen dieselbe ISBN-Nummer“ als Pfeildiagramm.

Ein Beispiel aus der Landwirtschaft soll die eingeführten Begriffe verdeutlichen. Betrachten wir die Menge aller Nutztiere in einem landwirtschaftlichen Betrieb. Wir definieren nun eine Relation: Wir sagen, zwei Tiere stehen in Relation zueinander, wenn sie von derselben Art sind. Die Kuh Kathrin steht mit dem Ochsen Otto in Relation, aber nicht mit dem Huhn Heidi. Diese Relation ist eine Äquivalenzrelation:

Reflexivität: Jedes Tier ist von derselben Art wie es selbst.

Symmetrie: ist ein Tier von derselben Art wie das andere, dann ist das andere auch von derselben Art wie das eine.

Transitivität: Wenn Kathrin und Lisa von derselben Art sind und Lisa und Otto von derselben Art, dann sind Kathrin und Otto von derselben Art – alle drei sind Rinder.

Eine Äquivalenzklasse: besteht hier also aus den Tieren einer Art. Zum Beispiel bilden die Rinder eine Äquivalenzklasse und Hühner eine andere Äquivalenzklasse.

Äquivalenzklassen

Menge von acht Buchexemplaren mit eingezeichneter Äquivalenzrelation „x und y besitzen dieselbe ISBN-Nummer“ als Pfeildiagramm und den Äquivalenzklassen.

Die Äquivalenzklasse eines Objektes a ist die Klasse der Objekte, die äquivalent zu a sind.

Formal: Ist R eine Äquivalenzrelation auf einer Menge M, so nennt man für ein a ∈ M die Teilmenge

$[a]_R = \{x\in M\mid x\sim_R a\} \subseteq M$

die R-Äquivalenzklasse von a. Ist aus dem Kontext klar, dass Äquivalenzklassen bezüglich R gebildet werden, lässt man den Zusatz R weg. Andere Schreibweisen sind

$[a],\quad[a]_\sim,\quad\bar a,\quad a/R,\quad a/{\sim_R}.$

Elemente einer Äquivalenzklasse werden ihre Vertreter oder Repräsentanten genannt. Jedes Element von M ist in genau einer Äquivalenzklasse enthalten. Die Äquivalenzklassen bilden somit eine Partition von M. Die Äquivalenzklassen zu zwei Elementen sind entweder gleich oder disjunkt, ersteres genau dann, wenn die Elemente äquivalent sind:

$[a]=[b]\quad\iff\quad a\sim b\quad\iff\quad a\in[b]\quad\iff\quad b\in[a].$

Hat man für jede Äquivalenzklasse [a]_R genau ein $y \in B$ mit $y \in [a]_R$, dann nennt man die Teilmenge $B \subseteq M$ vollständiges Repräsentantensystem für R.

Menge der Äquivalenzklassen und Index

Die Menge der Äquivalenzklassen (manchmal auch Faktormenge oder Quotientenmenge genannt) ist

$M/{\sim} := \{[a] \mid a \in M\}.$

In dieser Menge werden die Äquivalenzklassen nun nicht mehr als Untermengen von M, sondern als eigen- und selbstständige Elemente betrachtet. Die Menge der Äquivalenzklassen entsteht, wenn man äquivalente Elemente „gleich macht“. Sie formalisiert (mathematisch) den kognitiven Prozess der Identifizierungsabstraktion (siehe auch den Begriff der Teilidentität bei Löringhoff).

Die Mächtigkeit (Kardinalität) $\left|{M/{\sim}}\right|$ wird manchmal auch als der Index der Äquivalenzrelation R bezeichnet. (Ein Spezialfall ist der Index einer Untergruppe.)

Es gibt eine kanonische surjektive Abbildung

$M\to M/{\sim},\quad m\mapsto[m],$

die jedem Element seine Äquivalenzklasse zuordnet. Sie ist nur injektiv, wenn die Äquivalenzrelation die Identität ist.

Weitere Beispiele

• Schulklassen: die zugrundeliegende Menge M ist die Menge aller Schüler auf einer Schule; zwei Schüler seien äquivalent, wenn sie in dieselbe Klasse gehen.

• • Äquivalenzklasse eines Schülers ist die Menge aller seiner Mitschüler der gleichen Schulklasse. (Ihn selbst mit eingeschlossen → Reflexivität)
  • Die Menge der Äquivalenzklassen ist die Menge der Schulklassen.

• Gleichheit: auf einer beliebigen Menge M seien zwei Elemente äquivalent, wenn sie gleich sind:

$m\sim n\quad:\Longleftrightarrow\quad m=n$

• Äquivalenzklasse eines Elementes m ist die einelementige Menge {m}.
• Die Menge der Äquivalenzklassen ist die Menge der einelementigen Teilmengen von M; die Abbildung $M\to M/{\sim}$ ist eine Bijektion.

• Kongruenz in der Zahlentheorie: Die zugrundeliegende Menge ist die Menge Z der ganzen Zahlen, zwei Zahlen sind äquivalent, wenn sie denselben Rest bei Division durch 5 haben. Eine gleichwertige Formulierung ist: wenn ihre Differenz durch 5 teilbar ist.

• Äquivalenzklasse einer ganzen Zahl k ist die so genannte Restklasse

$[k] = \bar k=k+5\mathbb Z=\{k+5z\mid z\in\mathbb Z\}=\{\ldots,k-10,k-5,k,k+5,k+10,\ldots\}.$

• Die Menge der Äquivalenzklassen ist der Restklassenring

$\mathbb Z/5\mathbb Z = \mathbb Z/_{(5)} =\{\bar0,\bar1,\bar2,\bar3,\bar4\} = \{[0], [1], [2], [3], [4]\}.$

• Brüche: Es sei $M:=\{(z,n)\in\mathbb Z^2\mid n\not=0\}$ die Menge der Paare ganzer Zahlen, deren zweiter Eintrag von Null verschieden ist. Zwei Paare (z₁,n₁) und (z₂,n₂) sollen äquivalent heißen, wenn gilt:

$\frac{z_1}{n_1}=\frac{z_2}{n_2}.$

• Die Äquivalenzklasse eines Paares (z,n) besteht aus allen Paaren (Zähler, Nenner) für Bruchdarstellungen der rationalen Zahl $\frac zn$.
• Die Menge der Äquivalenzklassen wird durch

$M/{\sim}\to\mathbb Q,\quad [(z,n)]\mapsto\frac zn$

bijektiv auf die Menge der rationalen Zahlen abgebildet. Ein wichtiger Punkt ist hier die Wohldefiniertheit: wenn [(z₁,n₁)] = [(z₂,n₂)] gilt, dann ist das Bild nach der obigen Vorschrift

einerseits $\frac{z_1}{n_1}$, andererseits $\frac{z_2}{n_2}$.

Die Äquivalenzrelation war aber gerade so gewählt, dass diese beiden rationalen Zahlen gleich sind.

• L^p-Raum: Auf dem Raum der p-fach integrierbaren Funktionen $\mathcal{L}^p$ kann eine Äquivalenzrelation wie folgt definiert werden: Seien $f,g \in \mathcal{L}^p$, dann gilt $f{\sim}g\,$ genau dann, wenn f = g bis auf eine Nullmenge gilt. Die Menge aller Äquivalenzklassen bezeichnet man als L^p-Raum. Es gilt also $L^p=\mathcal{L}^p/\sim$.

Universelle Eigenschaft

Ist M eine Menge, R eine Äquivalenzrelation auf M und N eine weitere Menge, so vermittelt die Abbildung $M\to M/{\sim_R},\ x\mapsto [x]_R$ eine Bijektion zwischen folgenden Mengen:

• Abbildungen $M\to N$, bei denen R-äquivalente Elemente dasselbe Bild haben

und

• Abbildungen $M/{\sim_R}\to N.$

Modulo

Besondere Bedeutung kommt Äquivalenzrelationen zu, die mit einer algebraischen Struktur auf einer Menge vergleichbar sind. In allen diesen Fällen gibt es einen „Modul“ $U \,$ (von lat. modulus Maß), d. h. eine mit einer algebraischen Verknüpfung $\cdot \,$ in der Ausgangsmenge $(M, \cdot) \,$ kompatible Unterstruktur $U \subseteq M \,$, die die Äquivalenz $\sim \,$ vermittelt:

$x \sim y \quad \Longleftrightarrow \quad x \in y \cdot U \,$      (ggf. auch $\Longleftrightarrow \quad x \in U \cdot y \quad$),

man nehme nur $U := \left\{x \in M \mid x \sim n \right\}\,$ mit $n \,$ als dem neutralen Element von $(M, \cdot) \,$. Ist stets $y \cdot U = U \cdot y \,$, dann schreibt man auch

$x \equiv y \mod U \,$

und sagt „x (ist) kongruent y modulo [ˈmoːduloː] U“ (von lat. modulō Ablativ zu modulus Maß). Grammatikalisch wird modulo im Deutschen verwendet wie eine Präposition, die den Dativ regiert.

Ist der Modul $U \,$ einfach erzeugt in $M \,$, bspw. $U = M \cdot u \,$ mit einem $u \in M \,$, dann notiert man auch

$x \equiv y \mod u \,$.

Diese Sprechweise ist die fast ausschließliche im Ring der ganzen Zahlen $\Z \,$.

Auch bei den Äquivalenzklassen oder Nebenklassen spricht man von Äquivalenzklassen modulo $U \,$ und bei der Faktormenge $M/U \,$ von $M \,$ modulo $U \,$ oder auch $M \,$ modulo $R \,$ und $M \,$ modulo $\sim \,$.

Die Faktormenge kann algebraische Struktur von der Ausgangsmenge „erben“. Basiert das Definieren dieses Rechnens modulo auf den Elementen der Ausgangsmenge $(M, \cdot) \,$, also den sog. „Repräsentanten“ der Äquivalenzklassen, muss immer auch die Wohldefiniertheit dieses Rechnens sichergestellt werden. Gelingt dieses und ist $U \subseteq M \,$ die Unterstruktur, die die Äquivalenz vermittelt, so spricht man vom Rechnen modulo $U \,$.

Beispiel

Sei $M:=\mathfrak{S}_3 \,$ die symmetrische Gruppe vom Grad 3 und $U := \{(1), (12)\} \,$ in Zyklenschreibweise eine der 3 Untergruppen der Ordnung 2. Man kann zwar die 3 Nebenklassen

$(1) \circ U = \{(1), (12)\} \;$,   $(13) \circ U = \{(13), (123)\} \;$ und   $(23) \circ U = \{(23), (132)\} \;$

bilden (Reihenfolge der Komposition der Zyklen wie im Artikel symmetrische Gruppe). Die geerbte Verknüpfung ist aber nicht von der Wahl des Repräsentanten unabhängig (s. Beispiel $\mathfrak{S}_3 \,$ im Artikel Wohldefiniertheit).

Wäre $U \,$ jedoch nicht nur Untergruppe, sondern Normalteiler von $M \,$, ließe sich die geerbte Gruppenoperation auf der Faktorgruppe $M/U \,$ wohldefinieren.

Weitere Äquivalenzbegriffe

Beispiele für Faktormengen:

• Faktorraum (für Vektorräume)
• Faktorgruppe (für Gruppen)
• Faktorring (für Ringe)
• Kongruenzrelation (für allgemeine algebraische Strukturen)

Die folgenden Äquivalenzbegriffe entstehen aus der Forderung, dass ein Paar von Abbildungen mit gewissen Eigenschaften zwischen zwei Objekten existiert, die „mehr oder weniger“ invers zueinander sind:

• Isomorphie
• Homöomorphie
• Homotopieäquivalenz
• Äquivalenz von Kategorien

Weitere Beispiele für Äquivalenzrelationen:

• Vervollständigung durch Äquivalenzklassen von Cauchy-Folgen

Literatur

• Gerd Fischer: Lineare Algebra. Vieweg-Verlag, ISBN 3-528-03217-0.
• Albrecht Beutelspacher: Lineare Algebra. Vieweg-Verlag, ISBN 3-528-56508-X.
• Matthias Schubert: Mathematik für Informatiker. Vieweg-Verlag, ISBN 978-3-8351-0157-9.
• Bruno von Freytag-Löringhoff: LOGIK Ihr System und ihr Verhältnis zur Logistik, 3., verbesserte, Auflage, W. Kohlhammer Verlag, Stuttgart 1955

Weblinks

 Wikibooks: Mathe für Nicht-Freaks: Relation: Äquivalenzrelation – Lern- und Lehrmaterialien