Äquivalenzrelation

In der Mathematik werden Objekte, die sich in einem bestimmten Zusammenhang gleichen, als gleichwertig bzw. äquivalent angesehen.

Ein solcher Zusammenhang lässt sich für alle Elemente einer Menge ${\displaystyle A}$ stets durch eine Funktion ${\displaystyle f\colon A\to B}$ herstellen, indem man genau dann zwei Elemente ${\displaystyle a,b\in A}$ als zueinander „äquivalent“ bezeichnet und diese Relation durch ${\displaystyle a\sim b}$ symbolisiert, wenn deren Bilder gleich sind:

${\displaystyle a\sim b\;:\!\iff f(a)=f(b)}$.

Diese Relation hat die folgenden drei Eigenschaften:

1. Jedes Objekt ${\displaystyle a}$ ist zu sich selbst äquivalent:   ${\displaystyle a\sim a}$.
2. Wenn ${\displaystyle a}$ äquivalent zu ${\displaystyle b}$ ist, dann ist auch ${\displaystyle b}$ äquivalent zu ${\displaystyle a}$:   ${\displaystyle a\sim b\implies b\sim a}$.
3. Wenn ${\displaystyle a}$ äquivalent zu ${\displaystyle b}$ und ${\displaystyle b}$ äquivalent zu ${\displaystyle c}$ ist, dann ist auch ${\displaystyle a}$ äquivalent zu ${\displaystyle c}$:   ${\displaystyle a\sim b\;}$ und ${\displaystyle \;b\sim c\implies a\sim c}$.

Menge von acht Buchexemplaren mit eingezeichneter Äquivalenzrelation „${\displaystyle a}$ und ${\displaystyle b}$ besitzen dieselbe ISBN“ als Pfeildiagramm

Eine Äquivalenzrelation auf einer Menge ${\displaystyle A\neq \emptyset }$ ist eine zweistellige Relation ${\displaystyle {\mathrel {\sim }}\subseteq A\times A}$, die folgende Bedingungen erfüllt:

Reflexivität

${\displaystyle (a,a)\in {\mathrel {\sim }}\;\;}$ für alle ${\displaystyle a\in A}$.

Symmetrie

${\displaystyle (a,b)\in {\mathrel {\sim }}\implies (b,a)\in {\mathrel {\sim }}\;\;}$ für alle ${\displaystyle a,b\in A}$.

Transitivität

${\displaystyle (a,b)\in {\mathrel {\sim }}}$ und ${\displaystyle (b,c)\in {\mathrel {\sim }}\implies (a,c)\in {\mathrel {\sim }}\;\;}$ für alle ${\displaystyle a,b,c\in A}$.

Wie bei zweistelligen Relationen üblich, schreibt man statt ${\displaystyle (a,b)\in {\mathrel {\sim }}}$ auch einfacher ${\displaystyle a\sim b}$, dann nehmen diese Eigenschaften die oben genannte Form an.

Das geordnete Paar ${\displaystyle (A,\sim )}$ nennt man in diesem Fall auch Setoid oder E-set (englische Bezeichnung: extensional set, auch Bishop set).[1]

Menge von acht Buchexemplaren mit eingezeichneter Äquivalenzrelation „${\displaystyle a}$ und ${\displaystyle b}$ besitzen dieselbe ISBN“ als Pfeildiagramm und den Äquivalenzklassen

Ist ${\displaystyle \sim }$ eine Äquivalenzrelation auf einer Menge (Klasse) ${\displaystyle A\neq \emptyset }$, so nennt man die Teilmenge (bzw. Teilklasse)

${\displaystyle [a]_{\sim }:=\{b\in A\mid b\sim a\}}$,

aller zu ${\displaystyle a\in A}$ äquivalenten Elemente, die ${\displaystyle \sim }$-Äquivalenzklasse von ${\displaystyle a}$.

Ist aus dem Kontext klar, dass Äquivalenzklassen bezüglich ${\displaystyle \sim }$ gebildet werden, lässt man den Zusatz ${\displaystyle \sim }$ weg:

${\displaystyle [a]}$,

andere Schreibweisen sind

${\displaystyle a/{\sim }\quad }$ sowie ${\displaystyle \quad {\bar {a}}}$.

Elemente einer Äquivalenzklasse werden ihre Vertreter oder Repräsentanten genannt. Jedes Element von ${\displaystyle A}$ ist in genau einer Äquivalenzklasse enthalten. Die Äquivalenzklassen zu je zwei Elementen ${\displaystyle a,b\in A}$ sind entweder gleich oder disjunkt. Ersteres genau dann, wenn die Elemente äquivalent sind:

${\displaystyle [a]=[b]\iff a\in [b]\iff a\sim b\iff b\in [a]}$.

Eine Teilmenge ${\displaystyle S\subseteq A}$ nennt man ein (vollständiges) Vertreter- oder Repräsentantensystem von ${\displaystyle \sim }$, wenn es für jede Äquivalenzklasse ${\displaystyle [a]}$ genau ein ${\displaystyle s\in S}$ gibt mit ${\displaystyle s\in [a]}$.

Für jede Äquivalenzrelation ${\displaystyle \sim }$ auf einer Menge ${\displaystyle A}$ lässt sich zu jedem Repräsentantensystem ${\displaystyle S}$ von ${\displaystyle \sim }$ eine Funktion ${\displaystyle f_{S}\colon \,A\to A}$ definieren, indem man

${\displaystyle f_{S}(a):=s\iff a\sim s\;\;}$ für alle ${\displaystyle a\in A,\,s\in S}$

setzt.

Die Faktor- oder Quotientenmenge einer Äquivalenzrelation ${\displaystyle \sim }$ auf der Menge ${\displaystyle A}$ ist die Menge aller Äquivalenzklassen:

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

Sie bildet eine Zerlegung oder Partition von ${\displaystyle A}$.

Ist umgekehrt ${\displaystyle {\mathcal {P}}}$ eine Partition von ${\displaystyle A}$, dann ist durch

${\displaystyle a\sim b\;:\!\iff \exists B\in {\mathcal {P}}\colon \;a,b\in B}$

eine Äquivalenzrelation gegeben.

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

Die surjektive Funktion

${\displaystyle \mathrm {q} _{\sim }\colon \,A\twoheadrightarrow A/{\sim },\,a\mapsto [a]_{\sim }}$,

die jedem Element seine Äquivalenzklasse zuordnet, heißt kanonische Abbildung oder Quotientenabbildung.

Diese Abbildung ist nur dann injektiv, wenn es sich bei der Äquivalenzrelation auf ${\displaystyle A}$ um die Identitätsrelation ${\displaystyle \mathrm {I} _{A}}$ handelt.

Man nennt die durch die Funktion ${\displaystyle f\colon \,A\to B}$ gegebene Äquivalenzrelation ${\displaystyle \sim }$ auch den Kern von ${\displaystyle f}$[2]

${\displaystyle \ker f:=f^{-1}\circ f=\{(a,b)\in A\times A\mid f(a)=f(b)\}={\mathrel {\sim }}}$.[3]

Insbesondere ist die Äquivalenzklasse von jedem ${\displaystyle a\in A}$ das Urbild von dessen Bild ${\displaystyle f(a)\in B}$:

${\displaystyle [a]_{\sim }=f^{-1}(\{f(a)\})=f^{-1}(f(\{a\}))=\ker f(\{a\})}$.

${\displaystyle f}$ lässt sich dann wie folgt in eine surjektive, eine bijektive sowie eine injektive Funktion zerlegen:

${\displaystyle f=\mathrm {i} _{f}\circ f^{\sim \!}\circ \mathrm {q} _{\sim }}$

mit ${\displaystyle f^{\sim }\colon \,A/{\sim }\;{\!\;\twoheadrightarrow \;\!\!\!\!\!\!\!\!\!\!\;\rightarrowtail }\;f(A),\,[a]_{\sim }\mapsto f(a),}$ und der Inklusionsabbildung ${\displaystyle \mathrm {i} _{f}\colon \;f(A)\rightarrowtail B,\,f(a)\mapsto f(a)}$.

Weder reflexiv noch symmetrisch noch transitiv:

${\displaystyle \{(a,b)\in \mathbb {N} \times \mathbb {N} \mid a-b=1\}}$   (${\displaystyle a}$ ist um 1 größer als ${\displaystyle b}$).

Ein weiteres Beispiel hierfür ist die Beziehung „ist ein Bruder von“ auf der Menge aller Menschen. Sie ist weder reflexiv (weil niemand sein eigener Bruder ist) noch symmetrisch (weil die Schwester eines Mannes nicht sein Bruder ist, obwohl er ein Bruder von ihr ist) noch transitiv (weil ein Mann kein Bruder seiner selbst ist, obwohl er – wenn er einen Bruder hat – ein Bruder seines Bruders ist und dieser ein Bruder von ihm ist).

Reflexiv, aber weder symmetrisch noch transitiv:

${\displaystyle \{(a,b)\in \mathbb {N} \times \mathbb {N} \mid a-b\in \{0,1\}\}}$   (${\displaystyle a}$ ist höchstens um 1 größer als ${\displaystyle b}$).

Symmetrisch, aber weder reflexiv noch transitiv:

${\displaystyle \{(a,b)\in \mathbb {N} \times \mathbb {N} \mid |a-b|=1\}}$   (${\displaystyle a}$ und ${\displaystyle b}$ sind benachbart).

Transitiv, aber weder reflexiv noch symmetrisch:

${\displaystyle \{(a,b)\in \mathbb {N} \times \mathbb {N} \mid a<b\}}$   (${\displaystyle a}$ ist kleiner als ${\displaystyle b}$).

Symmetrisch und transitiv (partielle Äquivalenzrelation), aber nicht reflexiv:

${\displaystyle \{(a,b)\in \mathbb {N} \times \mathbb {N} \mid b=a\neq 1\}}$   (${\displaystyle a}$ ist gleich ${\displaystyle b}$ und nicht 1).

Reflexiv und transitiv (Quasiordnung), aber nicht symmetrisch:

${\displaystyle \{(a,b)\in \mathbb {N} \times \mathbb {N} \mid a\leq b\}}$   (${\displaystyle a}$ ist kleiner oder gleich ${\displaystyle b}$).

Reflexiv und symmetrisch (Toleranzrelation), aber nicht transitiv:

${\displaystyle \{(a,b)\in \mathbb {N} \times \mathbb {N} \mid |a-b|\leq 1\}}$   (${\displaystyle a}$ und ${\displaystyle b}$ sind gleich oder benachbart).

Reflexiv, symmetrisch und transitiv:

${\displaystyle \{(a,b)\in \mathbb {N} \times \mathbb {N} \mid a=b\}}$.

Ein anschauliches Beispiel aus der Landwirtschaft soll die eingeführten Begriffe verdeutlichen. Betrachtet wird eine Menge ${\displaystyle T}$ von Nutztieren in einem landwirtschaftlichen Betrieb. Wir definieren die folgende zweistellige Relation ${\displaystyle \sim }$ auf ${\displaystyle T}$:

Für je zwei Nutztiere ${\displaystyle t}$ und ${\displaystyle v}$ aus ${\displaystyle T}$ soll ${\displaystyle t\sim v}$ genau dann gelten, wenn ${\displaystyle t}$ und ${\displaystyle v}$ Tiere derselben Art sind.

Für die Kuh ${\displaystyle k}$ und den Ochsen ${\displaystyle o}$ gilt immer ${\displaystyle k\sim o}$. Für das Huhn ${\displaystyle h}$ dagegen gilt dies aber nicht: ${\displaystyle h\nsim o}$. Die Relation ${\displaystyle \sim }$ erfüllt die drei Forderungen für Äquivalenzrelationen:

Reflexivität

Jedes Tier ist von derselben Art wie es selbst (im Sinne von: Jedes Tier gehört einer Art an).

Symmetrie

Ist ein Tier von derselben Art wie ein zweites, dann ist das zweite auch von derselben Art wie das erste.

Transitivität

Wenn ${\displaystyle k}$ und ${\displaystyle o}$ Tiere derselben Art sind und ebenso ${\displaystyle o}$ und ${\displaystyle b}$ von derselben Art sind, dann sind auch ${\displaystyle k}$ und ${\displaystyle b}$ von derselben Art (nämlich von der Art, zu der dann jedes der drei Tiere gehört).

Eine Äquivalenzklasse besteht hier aus den Tieren einer Art. Die Rinder bilden eine und die Hühner eine andere Äquivalenzklasse. Die Quotientenmenge ist die Menge der Tierarten des landwirtschaftlichen Betriebes.

Auf einer beliebigen Menge ${\displaystyle A}$ seien zwei Elemente äquivalent, wenn sie gleich sind. Diese durch den Graphen der identischen Abbildung ${\displaystyle \operatorname {id} _{A}}$ auf ${\displaystyle A}$ gegebene Äquivalenzrelation nennt man die Gleichheits- oder Identitätsrelation

${\displaystyle \mathrm {I} _{A}:=\{(a,b)\in A\times A\mid a=b\}=\{(a,a)\mid a\in A\}\!}$.

Es gilt:

• Die Äquivalenzklasse eines Elementes ${\displaystyle a}$ ist die einelementige Menge ${\displaystyle \{a\}}$.
• Die Quotientenmenge ist die Menge der einelementigen Teilmengen von ${\displaystyle A}$. Die Abbildung ${\displaystyle A\to A/\mathrm {I} _{A}}$ ist bijektiv.
• Für die Verkettung ${\displaystyle \circ }$ mit beliebigen Relationen ${\displaystyle R}$ auf ${\displaystyle A}$ gilt:

${\displaystyle \mathrm {I} _{A}\circ R=R\circ \mathrm {I} _{A}=R}$   (neutrales Element).

Auf einer Menge ${\displaystyle A}$ seien nun jeweils zwei beliebige Elemente äquivalent. Auch dadurch ist eine Äquivalenzrelation auf ${\displaystyle A}$ gegeben, die sogenannte All- oder Universalrelation

${\displaystyle \mathrm {U} _{A}:=A\times A=\{(a,b)\mid a,b\in A\}}$.

Es gilt:

• Die Äquivalenzklasse jedes Elementes ${\displaystyle a}$ ist die ganze Menge ${\displaystyle A}$.
• Die Quotientenmenge ist die einelementige Menge ${\displaystyle \{A\}}$. Die Abbildung ${\displaystyle A\to A/\mathrm {U} _{A}}$ ist konstant.
• Für die Verkettung ${\displaystyle \circ }$ mit beliebigen reflexiven Relationen ${\displaystyle R}$ auf ${\displaystyle A}$ gilt:

${\displaystyle \mathrm {U} _{A}\circ R=R\circ \mathrm {U} _{A}=\mathrm {U} _{A}}$   (absorbierendes Element).

Zwei geometrische Figuren ${\displaystyle F}$ und ${\displaystyle G}$ in der euklidischen Ebene sind genau dann einander ähnlich, wenn sie durch eine Ähnlichkeitsabbildung ineinander überführt werden können. Durch die Ähnlichkeit ist eine Äquivalenzrelation

${\displaystyle F\sim G\;:\!\iff F}$ und ${\displaystyle G}$ sind einander ähnlich

auf der Menge ${\displaystyle \mathbf {F} }$ aller Figuren der Ebene gegeben.

Darüber hinaus sind ${\displaystyle F}$ und ${\displaystyle G}$ genau dann kongruent, wenn sie durch eine Kongruenzabbildung, also eine längentreue Ähnlichkeitsabbildung, ineinander überführt werden können. Auch durch

${\displaystyle F\cong G\;:\!\iff F}$ und ${\displaystyle G}$ sind kongruent

ist eine Äquivalenzrelation auf ${\displaystyle \mathbf {F} }$ gegeben.

Wir definieren zunächst sechs Mengen von natürlichen Zahlen von 1 bis 23:

${\displaystyle A_{1}:=\{1,7,10,13,17\}}$,

${\displaystyle A_{2}:=\{2,5,8,16\}}$,

${\displaystyle A_{3}:=\{3,4,6,11,18,22\}}$,

${\displaystyle A_{4}:=\{9,12,14,15,23\}}$,

${\displaystyle A_{5}:=\{19\}}$,

${\displaystyle A_{6}:=\{20,21\}}$.

Sie haben die Eigenschaft, dass jede Zahl aus dem Bereich von 1 bis 23 in genau einer der sechs Mengen vorkommt, die damit eine Zerlegung oder Partition der Menge ${\displaystyle A=\{1,\dotsc ,23\}}$ bilden. Wie jede Partition von ${\displaystyle A}$ sind sie die Äquivalenzklassen einer Äquivalenzrelation ${\displaystyle \sim }$ auf ${\displaystyle A}$, nämlich

${\displaystyle a\sim b\;:\!\iff \exists i\in \{1,\ldots ,6\}\colon \;a,b\in A_{i}}$.

Die Mengen wurden durch Würfeln ermittelt, also willkürlich aus den rund 44 Billiarden[4] Partitionen – und damit ebenso vielen Äquivalenzrelationen – dieser 23-elementigen Menge ausgewählt. Äquivalente Zahlen nach dieser Relation weisen keine einfach beschreibbaren Gemeinsamkeiten auf.

• Äquivalenzklasse eines Elementes ${\displaystyle a}$ ist diejenige Menge ${\displaystyle A_{i}}$, die ${\displaystyle a}$ enthält.
• Die Quotientenmenge ist die sechselementige Menge ${\displaystyle \{A_{1},A_{2},A_{3},A_{4},A_{5},A_{6}\}}$.

Es sei ${\displaystyle P:=\{(z,n)\in \mathbb {Z} ^{2}\mid n\neq 0\}}$ die Menge der Paare ganzer Zahlen, deren zweiter Eintrag von Null verschieden ist. Für zwei Paare ${\displaystyle (z_{1},n_{1}),(z_{2},n_{2})\in P}$ soll folgende Äquivalenz gelten:

${\displaystyle (z_{1},n_{1})\sim (z_{2},n_{2})\;:\!\iff z_{1}\cdot n_{2}=z_{2}\cdot n_{1}}$.

• Die Äquivalenzklasse des Paares ${\displaystyle (z,n)}$ ist dann der Bruch oder (totale) Quotient ${\displaystyle \,{\tfrac {z}{n}}:=[(z,n)]_{\sim }}$.
• Mit der Quotientenmenge erhält man gerade die Menge der rationalen Zahlen ${\displaystyle \,\mathbb {Q}$ :=P/{\sim }=\left\{{\tfrac {z}{n}}\;{\big |}\;(z,n)\in P\right\}} .

Zwei reelle Zahlen ${\displaystyle x}$ und ${\displaystyle y}$ heißen kommensurabel, wenn sie ganzzahlige Vielfache einer geeigneten dritten reellen Zahl ${\displaystyle z}$ sind. Kommensurabilität ist eine Äquivalenzrelation, wenn man die Null gesondert betrachtet:

${\displaystyle x\sim y\;:\!\iff {\begin{cases}{\frac {x}{y}}\in \mathbb {Q} ^{\times },&{\text{falls }}\;x,y\neq 0,\\x=y=0,&{\text{falls }}\;x\cdot y=0\end{cases}}}$

mit ${\displaystyle \mathbb {Q} ^{\times }:=\mathbb {Q} \setminus \{0\}}$ als der multiplikativen Gruppe von ${\displaystyle \mathbb {Q} }$.

• Äquivalenzklasse einer reellen Zahl ${\displaystyle x}$ ist die Menge ${\displaystyle x\cdot \mathbb {Q} ^{\times }}$ der mit ${\displaystyle x}$ kommensurablen Zahlen, die für ${\displaystyle x\neq 0}$ abzählbar unendlich ist.
• Die Quotientenmenge ist überabzählbar. Anders als bei anderen ähnlich einfachen Äquivalenzrelationen bietet sich hier jedoch kein Repräsentantensystem an.
• Die Multiplikation ist mit ${\displaystyle \sim }$ verträglich, denn ist ${\displaystyle x\sim y}$ und ${\displaystyle x^{\prime }\sim y^{\prime }}$, dann folgt ${\displaystyle xx^{\prime }\sim yy^{\prime }}$ z. B. aus ${\displaystyle {\tfrac {xx^{\prime }}{yy^{\prime }}}\in \mathbb {Q} ^{\times }.}$
• Die reelle Addition ist jedoch nicht mit ${\displaystyle \sim }$ verträglich, denn z. B. ist ${\displaystyle -1\sim 1}$, aber ${\displaystyle {\tfrac {{\sqrt {2}}-1}{{\sqrt {2}}+1}}=3-2{\sqrt {2}}\;\notin \mathbb {Q} ^{\times },}$ also ${\displaystyle {\sqrt {2}}-1\;\not \sim {\sqrt {2}}+1.}$

Sei ${\displaystyle {\mathcal {F}}}$ eine Sigma-Algebra auf einer Menge ${\displaystyle \Omega }$ und ${\displaystyle \mu {\text{: }}{\mathcal {F}}\rightarrow [0,\infty ]}$ ein vollständiges Maß. Es kann leicht gezeigt werden, dass für messbare Funktionen ${\displaystyle f_{1},f_{2}:\Omega \rightarrow \mathbb {R} }$ die Abbildung

${\displaystyle \langle f_{1}|f_{2}\rangle$ :=\int \limits _{\Omega }f_{1}\cdot f_{2}{\text{ d}}\mu }

eine positiv semidefinite Bilinearform darstellt, falls

${\displaystyle f_{1},f_{2}\in {\mathcal {L}}^{2}:=\left\{f:\Omega \rightarrow \mathbb {R}$ :\int \limits _{\Omega }f^{2}{\text{ d}}\mu <\infty \right\}}

gilt.

Der Grund dafür, dass im Allgemeinen keine strikte positive Definitheit gilt, liegt darin, dass für ein ${\displaystyle f\in {\mathcal {L}}^{2}}$ auch ${\displaystyle \langle f|f\rangle =0}$ gelten kann, ohne dass ${\displaystyle f}$ die Nullfunktion ist – nämlich genau dann, wenn ${\displaystyle \mu (\{x\in \Omega :f(x)\neq 0\})=0}$ (d. h. wenn ${\displaystyle f}$ nur auf einer Menge ungleich 0 ist, welche eine ${\displaystyle \mu }$-Nullmenge darstellt).

Abhilfe verschafft das Einführen einer Äquivalenzrelation: Man definiert, dass ${\displaystyle f_{1}\sim f_{2}:\Leftrightarrow \langle f_{1}-f_{2}|f_{1}-f_{2}\rangle =0}$ und gibt der Menge der Äquivalenzklassen die Bezeichnung ${\displaystyle L^{2}}$.

Dann ist ${\displaystyle \langle \cdot |\cdot \rangle }$ zusätzlich zu den oben genannten Eigenschaften auch noch positiv definit, also ein Skalarprodukt und ${\displaystyle \|\cdot \|:={\sqrt {\langle \cdot |\cdot \rangle }}}$ damit eine Norm. Somit handelt es sich bei ${\displaystyle (L^{2},\|\cdot \|)}$ um einen normierten Raum. Schließlich folgt aus dem Satz von Fischer-Riesz, dass dieser Raum vollständig ist, sodass er ein Banachraum und insbesondere (da die Norm von einem Skalarprodukt induziert wird) ein Hilbertraum ist. Dieser findet seine Anwendung z. B. in der Quantenmechanik, aber auch beim Erwartungswert.

Hierbei ist zu beachten, dass es sich bei einem Element aus ${\displaystyle L^{2}}$ nicht um eine Funktion handelt, sondern um eine Äquivalenzklasse von Funktionen bezüglich der obigen Äquivalenzrelation. Da sich die Repräsentanten dieser Klasse jedoch nur auf einer ${\displaystyle \mu }$-Nullmenge unterscheiden, ist dies für praktische Verwendungen unerheblich.

${\displaystyle (X,d)}$ sei ein metrischer Raum und

${\displaystyle {\mathcal {T}}_{d}:=\{O\subseteq X\mid O}$ offen in ${\displaystyle (X,d)\}}$

die zu ${\displaystyle d}$ gehörende Topologie. Ist ${\displaystyle d^{\prime }}$ eine weitere Metrik auf ${\displaystyle X}$ und ${\displaystyle {\mathcal {T}}_{d^{\prime }}}$ deren zugehörige Topologie, dann heißen ${\displaystyle d}$ und ${\displaystyle d^{\prime }}$ topologisch äquivalent, wenn ${\displaystyle {\mathcal {T}}_{d}}$ und ${\displaystyle {\mathcal {T}}_{d^{\prime }}}$ übereinstimmen:

${\displaystyle d\sim d^{\prime }\;:\!\iff {\mathcal {T}}_{d}={\mathcal {T}}_{d^{\prime }}}$.

Zwei beliebige Mengen ${\displaystyle A}$ und ${\displaystyle B}$ sind gleichmächtig genau dann, wenn es eine Bijektion ${\displaystyle f\colon \,A\;{\!\;\twoheadrightarrow \;\!\!\!\!\!\!\!\!\!\!\;\rightarrowtail }\;B}$ gibt. Durch die Festlegung

${\displaystyle A\sim B\;:\!\iff A}$ und ${\displaystyle B}$ sind gleichmächtig

ist eine Äquivalenz auf der Klasse aller Mengen gegeben.

Strukturen ${\displaystyle \mathbf {A} }$ und ${\displaystyle \mathbf {B} }$ nennt man isomorph genau dann, wenn es eine strukturverträgliche Bijektion ${\displaystyle \varphi \colon \,\mathbf {A} \;{\!\;\twoheadrightarrow \;\!\!\!\!\!\!\!\!\!\!\;\rightarrowtail }\;\mathbf {B} }$ gibt, für die auch ${\displaystyle \varphi ^{-1}}$ strukturverträglich ist. Die Isomorphie von Strukturen ist eine Äquivalenz

${\displaystyle \mathbf {A} \cong \mathbf {B} \;:\!\iff \mathbf {A} }$ und ${\displaystyle \mathbf {B} }$ sind isomorph.

Eine Äquivalenzrelation auf einer Menge ${\displaystyle A}$ hat nicht notwendigerweise etwas mit der Struktur zu tun, die darauf definiert ist. Von besonderem Interesse sind jedoch solche Äquivalenzrelationen ${\displaystyle \equiv }$, deren Quotientenabbildung

${\displaystyle \mathrm {q} _{\equiv }\colon \,A\to A/{\equiv },\,a\mapsto [a]_{\equiv },}$

mit der Struktur auf ${\displaystyle A}$ verträglich bzw. ein Homomorphismus ist, weil dann die von ${\displaystyle \mathrm {q} _{\equiv }}$ erzeugte Struktur auf der Quotientenmenge ${\displaystyle A/{\equiv }}$ von der gleichen Art ist wie die von ${\displaystyle A}$. Eine solche Äquivalenzrelation ${\displaystyle \equiv }$ nennt man eine Kongruenzrelation auf der strukturierten Menge ${\displaystyle A}$.

Insbesondere sind dann auch alle zur Struktur gehörenden Funktionen mit ${\displaystyle \equiv }$ verträglich.

Eine zweistellige Relation ${\displaystyle \smallfrown }$ auf einer Menge ${\displaystyle A}$ nennt man beschränkte oder partielle Äquivalenzrelation, wenn sie symmetrisch und transitiv ist.

Jede partielle Äquivalenzrelation ${\displaystyle \smallfrown }$ auf einer Menge ${\displaystyle A}$ ist auf der Untermenge

${\displaystyle D_{\smallfrown }:=\{a\in A\mid a\smallfrown a\}\subseteq A}$

eine totale Äquivalenzrelation. Die durch die Äquivalenzklassen ${\displaystyle [a]_{\smallfrown }}$ definierte Zerlegung von ${\displaystyle D_{\smallfrown }}$ heißt auch partielle Zerlegung von ${\displaystyle A}$.

Eine partielle Äquivalenzrelation ${\displaystyle \smallfrown }$ kann auf verschiedene Weise zu einer (totalen) Äquivalenzrelation ${\displaystyle \sim }$ fortgesetzt werden:

1. Jedes ${\displaystyle a\in A\setminus D_{\smallfrown }}$ bildet eine eigene Äquivalenzklasse ${\displaystyle \{a\}}$: ${\displaystyle \quad \,\quad a\sim b\;:\!\iff {\begin{cases}a\smallfrown b,&{\text{falls }}\;a,b\in D_{\smallfrown },\\a=b,&{\text{sonst}}.\end{cases}}}$
2. Alle ${\displaystyle a\in A\setminus D_{\smallfrown }}$ bilden eine einzige Äquivalenzklasse ${\displaystyle A\setminus D_{\smallfrown }}$: ${\displaystyle \quad a\sim b\;:\!\iff {\begin{cases}a\smallfrown b,&{\text{falls }}\;a,b\in D_{\smallfrown },\\a,b\in A\setminus D_{\smallfrown },&{\text{sonst}}.\end{cases}}}$

Das Ergebnis ist jeweils eine totale Zerlegung von ${\displaystyle A}$.

Jede partielle Funktion ${\displaystyle f\colon \,A\rightharpoonup B}$ nach einer beliebigen anderen Menge ${\displaystyle B}$ erzeugt eine partielle Äquivalenzrelation

${\displaystyle a_{1}\smallfrown a_{2}\;:\!\iff \exists b\in B\colon \;f(a_{1})=f(a_{2})=b\;\;}$ für alle ${\displaystyle a_{1},a_{2}\in A}$.

Umgekehrt liefert eine partielle Äquivalenzrelation auf ${\displaystyle A}$ stets eine surjektive partielle Quotientenabbildung

${\displaystyle \mathrm {q} _{\smallfrown }\colon \,A\rightharpoonup D_{\smallfrown }/{\smallfrown },\,a\mapsto [a]_{\smallfrown }}$ für alle ${\displaystyle a\in D_{\smallfrown }}$.

Eine zweistellige Relation ${\displaystyle \lesssim }$ auf einer Menge ${\displaystyle A}$ heißt Prä- oder Quasiordnung, wenn sie reflexiv und transitiv ist.

Eine Relation ${\displaystyle \lesssim }$ auf ${\displaystyle A}$ ist genau dann eine Quasiordnung, wenn für alle ${\displaystyle a,b\in A}$ gilt:

${\displaystyle a\lesssim b\iff \forall c\in A\colon \,(c\lesssim a\implies c\lesssim b)}$.

Durch jede Quasiordnung ${\displaystyle \lesssim }$ auf ${\displaystyle A}$ ist eine Äquivalenzrelation ${\displaystyle \sim }$ auf ${\displaystyle A}$ gegeben durch die Festlegung

${\displaystyle a\sim b\;:\!\iff a\lesssim b\,}$ und ${\displaystyle b\lesssim a}$.

Zwei Elemente sind also äquivalent, wenn sie gegenseitig vergleichbar sind.

Eine zweistellige reflexive und symmetrische Relation wird Verträglichkeits-[7] oder Toleranzrelation[8] genannt (im endlichen Fall auch Abhängigkeitsrelation). Da eine Toleranzrelation nicht transitiv sein muss, ist Toleranz eine schwächere Forderung als Äquivalenz. Sie spielt eine Rolle in der Biomathematik und der Modelltheorie, in der Fuzzylogik wird sie zudem noch weiter verallgemeinert.[9]

Bezeichne ${\displaystyle \smallsmile }$ eine Toleranzrelation auf der Menge (oder Klasse) ${\displaystyle A}$. Eine Teilmenge (oder -klasse) ${\displaystyle P\subseteq A}$ heißt Verträglichkeits- oder Toleranzpräklasse, falls alle ${\displaystyle a,b\in P}$ miteinander tolerant sind:[8]

${\displaystyle a\smallsmile b}$.

Eine maximale Präklasse ${\displaystyle K\subseteq A}$,[8] also wenn jedes ${\displaystyle a\in A\setminus K}$ mit mindestens einem ${\displaystyle k\in K}$ nicht tolerant ist, nennt man wiederum eine Verträglichkeits- bzw. Toleranzklasse.

Die Menge der Toleranzklassen[10] einer Toleranzrelation auf der Menge ${\displaystyle A}$ ist eine Überdeckung von ${\displaystyle A}$.