Äquivalenzrelation

Grundidee und Bedingungen

Eine Äquivalenzrelation ist eine zweistellige Relation \sim\subseteq A\times A, mit der Elemente einer Menge A in einem bestimmten Zusammenhang als gleichwertig behandelt werden. Sie ist in Mathematik und Logik wichtig, weil sie eine Menge vollständig in voneinander getrennte Gruppen einteilt.

Für alle a,b,c\in A müssen drei Bedingungen gelten:

• Reflexivität: a\sim a, also (a,a)\in\sim.
• Symmetrie: a\sim b\Rightarrow b\sim a.
• Transitivität: Aus a\sim b und b\sim c folgt a\sim c.

Eine durch eine Funktion f\colon A\to B definierte Relation a\sim b\iff f(a)=f(b) erfüllt diese Bedingungen. Das Paar (A,\sim) heißt auch Setoid oder E-set (extensional set, Bishop set).

Äquivalenzklassen und Quotientenmenge

Die Äquivalenzklasse von a\in A enthält genau alle Elemente, die zu a äquivalent sind:

[a]_{\sim}:=\{b\in A\mid b\sim a\}.

Jedes Element von A liegt in genau einer Äquivalenzklasse. Für a,b\in A sind ihre Klassen entweder gleich oder disjunkt; genauer gilt:

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

Die Menge aller Klassen heißt Faktor- oder Quotientenmenge:

A/{\sim}:=\{[a]_{\sim}\mid a\in A\}.

Sie ist eine Partition, also eine Zerlegung von A in nicht überlappende Teilmengen. Umgekehrt erzeugt jede Partition \mathcal P von A eine Äquivalenzrelation durch a\sim b\iff\exists B\in\mathcal P:\ a,b\in B. Die Kardinalität |A/{\sim}| heißt manchmal Index der Relation.

Ein Repräsentantensystem S\subseteq A enthält aus jeder Äquivalenzklasse genau ein Element. Die kanonische Quotientenabbildung \mathrm q_{\sim}\colon A\twoheadrightarrow A/{\sim},\ a\mapsto[a]_{\sim}, ordnet jedem Element seine Klasse zu. Sie ist nur bei der Identitätsrelation injektiv.

Funktionen und Äquivalenzhüllen

Der Kern einer Funktion f\colon A\to B ist die Äquivalenzrelation

\ker f:=f^{-1}\circ f=\{(a,b)\in A\times A\mid f(a)=f(b)\}.

Dabei ist [a]_{\sim}=f^{-1}(\{f(a)\}): Eine Klasse besteht also aus allen Elementen mit demselben Funktionswert. Die Funktion lässt sich zerlegen als

f=\mathrm i_f\circ f^{\sim}\circ\mathrm q_{\sim},

wobei \mathrm q_{\sim} surjektiv auf die Quotientenmenge abbildet, f^{\sim}\colon A/{\sim}\to f(A),\ [a]_{\sim}\mapsto f(a), bijektiv ist und \mathrm i_f\colon f(A)\to B die Inklusionsabbildung ist.

Soll eine beliebige Relation R mindestens enthalten sein, verwendet man ihre Äquivalenzhülle, die kleinste Äquivalenzrelation mit R\subseteq R^{\text{äq}}:

R^{\text{äq}}=(R^{\leftrightarrow})^*=(R\cup R^{-1})^*=\bigcup_{n\in\mathbb N_0}(R\cup R^{-1})^n.

Sie entsteht somit als reflexiv-transitive Hülle der symmetrischen Hülle.

Abgrenzung der Eigenschaften

Reflexivität, Symmetrie und Transitivität sind vollständig unabhängig: Keine der Eigenschaften folgt aus den anderen beiden automatisch.

Auf \mathbb N ist a=b eine Äquivalenzrelation, da alle drei Eigenschaften gelten. Dagegen ist a\leq b reflexiv und transitiv, aber nicht symmetrisch; dies heißt Quasiordnung. Die Relation |a-b|\leq1 ist reflexiv und symmetrisch, aber nicht transitiv; sie ist eine Toleranzrelation. Die Relation b=a\ne1 ist symmetrisch und transitiv, aber nicht reflexiv; sie ist eine partielle Äquivalenzrelation.

Auch eine Relation kann keine der drei Eigenschaften haben, etwa a-b=1. Beispiele mit genau einer Eigenschaft sind: a-b\in\{0,1\} nur reflexiv, |a-b|=1 nur symmetrisch und a<b nur transitiv.

Typische Beispiele

Bei Nutztieren eines Betriebs kann t\sim v bedeuten, dass beide Tiere derselben Art angehören. Diese Relation ist reflexiv, symmetrisch und transitiv. Die Tiere jeder Art bilden eine Äquivalenzklasse; die Quotientenmenge ist die Menge der im Betrieb vorkommenden Tierarten.

Die Identitätsrelation auf A lautet \mathrm I_A=\{(a,b)\in A\times A\mid a=b\}. Ihre Klassen sind die einelementigen Mengen \{a\}, und A\to A/\mathrm I_A ist bijektiv. Die All- oder Universalrelation \mathrm U_A=A\times A fasst dagegen alle Elemente in der einzigen Klasse A zusammen; die Quotientenabbildung ist konstant.

Rationale Zahlen entstehen als Quotientenmenge. Für P=\{(z,n)\in\mathbb Z^2\mid n\ne0\} gilt (z_1,n_1)\sim(z_2,n_2)\iff z_1n_2=z_2n_1. Dann ist \frac zn=[(z,n)]_{\sim} und \mathbb Q=P/{\sim}. Auch Ähnlichkeit und Kongruenz geometrischer Figuren sind Äquivalenzrelationen.

Spezielle und verallgemeinerte Formen

Eine partielle Äquivalenzrelation ist symmetrisch und transitiv, aber nicht unbedingt reflexiv. Auf D_{\smallfrown}=\{a\in A\mid a\smallfrown a\} ist sie jedoch eine totale Äquivalenzrelation. Elemente außerhalb von D_{\smallfrown} können bei einer Fortsetzung entweder jeweils eigene Klassen bilden oder gemeinsam eine Klasse bilden.

Eine Quasiordnung ist reflexiv und transitiv. Sie erzeugt durch a\sim b\iff a\lesssim b und b\lesssim a eine Äquivalenzrelation: Äquivalent sind dann gegenseitig vergleichbare Elemente.

Eine Toleranzrelation ist reflexiv und symmetrisch. Weil Transitivität fehlen kann, bilden ihre Toleranzklassen keine Partition, sondern nur eine Überdeckung von A.

Weitere wichtige Äquivalenzen sind Gleichmächtigkeit von Mengen, also das Bestehen einer Bijektion, und Isomorphie von Strukturen, also eine strukturverträgliche Bijektion mit strukturverträglicher Umkehrung. Eine Kongruenzrelation ist eine Äquivalenzrelation auf einer strukturierten Menge, deren Quotientenabbildung ein Homomorphismus ist; dadurch besitzt die Quotientenmenge eine Struktur derselben Art.