Äquivalenzrelation

Unter einer Äquivalenzrelation versteht man in der Mathematik eine zweistellige Relation, die reflexiv, symmetrisch und transitiv ist. Äquivalenzrelationen sind für die Mathematik und für die Logik von großer Bedeutung. Eine Äquivalenzrelation teilt eine Menge restlos in disjunkte (elementfremde) Untermengen, Äquivalenzklassen genannt. Die Klassenbildung mit Hilfe des Äquivalenzbegriffes ist grundlegend für viele mathematische Begriffsbildungen.

Definitionen

Äquivalenz

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 stets durch eine Funktion von herstellen, indem man genau dann zwei Elemente als zueinander „äquivalent“ bezeichnet und diese Relation durch symbolisiert, wenn deren Bilder gleich sind:

Allgemeiner hat man eine Eigenschaft , dann sind , wenn genau dann wahr ist, wenn auch wahr ist und umgekehrt.

Diese Relation hat die folgenden drei Eigenschaften:

1. Jedes Objekt ist zu sich selbst äquivalent:   .
2. Wenn äquivalent zu ist, dann ist auch äquivalent zu :   .
3. Wenn äquivalent zu und äquivalent zu ist, dann ist auch äquivalent zu :   und .

Äquivalenzrelation

Menge von acht Buchexemplaren mit eingezeichneter Äquivalenzrelation „ und besitzen dieselbe ISBN“ als Pfeildiagramm

Eine Äquivalenzrelation auf einer Menge ist eine zweistellige Relation , die folgende Bedingungen erfüllt:

Wie bei zweistelligen Relationen üblich, schreibt man statt auch einfacher , dann nehmen diese Eigenschaften die oben genannte Form an.

Das geordnete Paar nennt man in diesem Fall auch Setoid oder E-set (englische Bezeichnung: extensional set, auch Bishop set).

Äquivalenzklassen

Menge von acht Buchexemplaren mit eingezeichneter Äquivalenzrelation „ und besitzen dieselbe ISBN“ als Pfeildiagramm und den Äquivalenzklassen

Ist eine Äquivalenzrelation auf einer Menge (Klasse) , so nennt man die Teilmenge (bzw. Teilklasse)

aller zu äquivalenten Elemente, die -Äquivalenzklasse von .

Ist aus dem Kontext klar, dass Äquivalenzklassen bezüglich gebildet werden, lässt man den Zusatz weg:

andere Schreibweisen sind

Repräsentantensysteme

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

Eine Teilmenge nennt man ein (vollständiges) Vertreter- oder Repräsentantensystem von , wenn es für jede Äquivalenzklasse genau ein gibt mit .

Für jede Äquivalenzrelation auf einer Menge lässt sich zu jedem Repräsentantensystem von eine Funktion definieren, indem man

setzt.

Quotientenmenge und Partition

Die Faktor- oder Quotientenmenge einer Äquivalenzrelation auf der Menge ist die Menge aller Äquivalenzklassen:

Sie bildet eine Zerlegung oder Partition von .

Ist umgekehrt eine Partition von , dann ist durch

eine Äquivalenzrelation gegeben.

Die Mächtigkeit (Kardinalität) wird manchmal auch als der Index der Äquivalenzrelation bezeichnet. Ein Spezialfall ist der Index einer Untergruppe.

Quotientenabbildung

Die surjektive Funktion

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 um die Identitätsrelation handelt.

Kern einer Funktion

Man nennt die durch die Funktion gegebene Äquivalenzrelation auch den Kern von

Insbesondere ist die Äquivalenzklasse von jedem das Urbild von dessen Bild :

lässt sich dann wie folgt in eine surjektive, eine bijektive sowie eine injektive Funktion zerlegen:

mit und der Inklusionsabbildung .

Unabhängigkeit der drei Eigenschaften

Tatsächlich sind die Eigenschaften der Reflexivität, der Symmetrie und der Transitivität vollständig unabhängig voneinander und müssen alle einzeln überprüft werden. So ist zum Beispiel eine reflexive und symmetrische Relation nicht etwa automatisch schon transitiv. Um das nachzuweisen, genügt es, für jeden der acht möglichen Fälle ein Beispiel anzugeben, was im Folgenden mit Relationen auf der Menge der natürlichen Zahlen geschieht.

Keine der drei Eigenschaften ist erfüllt

Weder reflexiv noch symmetrisch noch transitiv:

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).

Genau eine der drei Eigenschaften ist erfüllt

Reflexiv, aber weder symmetrisch noch transitiv:

Symmetrisch, aber weder reflexiv noch transitiv:

Transitiv, aber weder reflexiv noch symmetrisch:

Genau zwei der drei Eigenschaften sind erfüllt

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

Reflexiv und transitiv (Quasiordnung), aber nicht symmetrisch:

Reflexiv und symmetrisch (Toleranzrelation), aber nicht transitiv:

Alle drei Eigenschaften sind erfüllt

Reflexiv, symmetrisch und transitiv:

Beispiele

Nutztiere in einem landwirtschaftlichen Betrieb

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

Für die Kuh und den Ochsen gilt immer . Für das Huhn dagegen gilt dies aber nicht: . Die Relation erfüllt die drei Forderungen für Äquivalenzrelationen:

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.

Identitätsrelation

Auf einer beliebigen Menge seien zwei Elemente äquivalent, wenn sie gleich sind. Diese durch den Graphen der identischen Abbildung auf gegebene Äquivalenzrelation nennt man die Gleichheits- oder Identitätsrelation

Es gilt:

• Die Äquivalenzklasse eines Elementes ist die einelementige Menge .
• Die Quotientenmenge ist die Menge der einelementigen Teilmengen von . Die Abbildung ist bijektiv.
• Für die Verkettung mit beliebigen Relationen auf gilt:

Allrelation

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

Es gilt:

• Die Äquivalenzklasse jedes Elementes ist die ganze Menge .
• Die Quotientenmenge ist die einelementige Menge . Die Abbildung ist konstant.
• Für die Verkettung mit beliebigen reflexiven Relationen auf gilt:

Ähnlichkeit und Kongruenz geometrischer Figuren

Zwei geometrische Figuren und 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

auf der Menge aller Figuren der Ebene gegeben.

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

ist eine Äquivalenzrelation auf gegeben.

Partition einer endlichen Zahlenmenge

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

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 bilden. Wie jede Partition von sind sie die Äquivalenzklassen einer Äquivalenzrelation auf , nämlich

Die Mengen wurden durch Würfeln ermittelt, also willkürlich aus den rund 44 Billiarden 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 ist diejenige Menge , die enthält.
• Die Quotientenmenge ist die sechselementige Menge .

Rationale Zahlen

Es sei die Menge der Paare ganzer Zahlen, deren zweiter Eintrag von Null verschieden ist. Für zwei Paare soll folgende Äquivalenz gelten:

• Die Äquivalenzklasse des Paares ist dann der Bruch oder (totale) Quotient .
• Mit der Quotientenmenge erhält man gerade die Menge der rationalen Zahlen .

Kommensurabilität reeller Zahlen

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

mit als der multiplikativen Gruppe von .

• Äquivalenzklasse einer reellen Zahl ist die Menge der mit kommensurablen Zahlen, die für 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 verträglich, denn ist und , dann folgt z. B. aus
• Die reelle Addition ist jedoch nicht mit verträglich, denn z. B. ist , aber also

Hilbertraum der L²-integrierbaren Funktionen

Sei eine Sigma-Algebra auf einer Menge und ein vollständiges Maß. Es kann leicht gezeigt werden, dass für messbare Funktionen die Abbildung

eine positiv semidefinite Bilinearform darstellt, falls

gilt.

Der Grund dafür, dass im Allgemeinen keine strikte positive Definitheit gilt, liegt darin, dass für ein auch gelten kann, ohne dass die Nullfunktion ist – nämlich genau dann, wenn (d. h. wenn nur auf einer Menge ungleich 0 ist, welche eine -Nullmenge darstellt).

Abhilfe verschafft das Einführen einer Äquivalenzrelation: Man definiert, dass und gibt der Menge der Äquivalenzklassen die Bezeichnung .

Dann ist zusätzlich zu den oben genannten Eigenschaften auch noch positiv definit, also ein Skalarprodukt und damit eine Norm. Somit handelt es sich bei 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 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 -Nullmenge unterscheiden, ist dies für praktische Verwendungen unerheblich.

Topologische Äquivalenz von Metriken

sei ein metrischer Raum und

die zu gehörende Topologie. Ist eine weitere Metrik auf und deren zugehörige Topologie, dann heißen und topologisch äquivalent, wenn und übereinstimmen:

Erzeugung von Äquivalenzrelationen

Eine Äquivalenzrelation explizit zu beschreiben ist manchmal nicht einfach. Oft möchte man eine Äquivalenzrelation konstruieren, die gewisse vorgegebene Elemente miteinander identifiziert und zugleich gewisse Eigenschaften erhält, beispielsweise eine Kongruenzrelation ist (siehe unten).

Sei eine beliebige Relation auf der Menge . Als Äquivalenzhülle von bezeichnet man die kleinste Äquivalenzrelation, die als Teilrelation enthält, in Zeichen:

Es gilt: Die Äquivalenzhülle ist die reflexiv-transitive Hülle der symmetrischen Hülle, formal:

Dabei bezeichnet die symmetrische Hülle, die konverse (inverse) Relation und Potenzen von Relationen werden vermöge Verkettung gebildet.

Spezielle Äquivalenzen

Gleichmächtigkeit von Mengen

Zwei beliebige Mengen und sind gleichmächtig genau dann, wenn es eine Bijektion gibt. Durch die Festlegung

ist eine Äquivalenz auf der Klasse aller Mengen gegeben.

Isomorphie von Strukturen

Strukturen und nennt man isomorph genau dann, wenn es eine strukturverträgliche Bijektion gibt, für die auch strukturverträglich ist. Die Isomorphie von Strukturen ist eine Äquivalenz

Kongruenzrelation

→ Hauptartikel: Kongruenzrelation

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

mit der Struktur auf verträglich bzw. ein Homomorphismus ist, weil dann die von erzeugte Struktur auf der Quotientenmenge von der gleichen Art ist wie die von . Eine solche Äquivalenzrelation nennt man eine Kongruenzrelation auf der strukturierten Menge .

Insbesondere sind dann auch alle zur Struktur gehörenden Funktionen mit verträglich.

Verallgemeinerungen

Partielle Äquivalenzrelation

Eine zweistellige Relation auf einer Menge nennt man beschränkte oder partielle Äquivalenzrelation, wenn sie symmetrisch und transitiv ist.

Jede partielle Äquivalenzrelation auf einer Menge ist auf der Untermenge

eine totale Äquivalenzrelation. Die durch die Äquivalenzklassen definierte Zerlegung von heißt auch partielle Zerlegung von .

Eine partielle Äquivalenzrelation kann auf verschiedene Weise zu einer (totalen) Äquivalenzrelation fortgesetzt werden:

1. Jedes bildet eine eigene Äquivalenzklasse :
2. Alle bilden eine einzige Äquivalenzklasse :

Das Ergebnis ist jeweils eine totale Zerlegung von .

Jede partielle Funktion nach einer beliebigen anderen Menge erzeugt eine partielle Äquivalenzrelation

Umgekehrt liefert eine partielle Äquivalenzrelation auf stets eine surjektive partielle Quotientenabbildung

Quasiordnung

→ Hauptartikel: Quasiordnung

Eine zweistellige Relation auf einer Menge heißt Prä- oder Quasiordnung, wenn sie reflexiv und transitiv ist.

Eine Relation auf ist genau dann eine Quasiordnung, wenn für alle gilt:

Durch jede Quasiordnung auf ist eine Äquivalenzrelation auf gegeben durch die Festlegung

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

Toleranzrelation

Eine zweistellige reflexive und symmetrische Relation wird Verträglichkeits- oder Toleranzrelation 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.

Bezeichne eine Toleranzrelation auf der Menge (oder Klasse) . Eine Teilmenge (oder -klasse) heißt Verträglichkeits- oder Toleranzpräklasse, falls alle miteinander tolerant sind:

Eine maximale Präklasse , also wenn jedes mit mindestens einem nicht tolerant ist, nennt man wiederum eine Verträglichkeits- bzw. Toleranzklasse.

Die Menge der Toleranzklassen einer Toleranzrelation auf der Menge ist eine Überdeckung von .

Weitere Äquivalenzbegriffe

• Äquivalenz von Kategorien
• Logische Äquivalenz von Aussagen

Literatur

• Marcel Erné: Einführung in die Ordnungstheorie. Bibliographisches Institut, Mannheim/Wien/Zürich 1982, ISBN 3-411-01638-8. 
• Gerd Fischer: Lineare Algebra. Eine Einführung für Studienanfänger. 14. durchgesehene Auflage. Vieweg, Wiesbaden 2003, ISBN 3-528-03217-0. 
• Udo Hebisch, Hanns Joachim Weinert: Halbringe. Algebraische Theorie und Anwendungen in der Informatik. Teubner, Stuttgart 1993, ISBN 3-519-02091-2. 
• Thomas Ihringer: Allgemeine Algebra. Mit einem Anhang über Universelle Coalgebra von H. P. Gumm (= Berliner Studienreihe zur Mathematik. Band 10). Heldermann, Lemgo 2003, ISBN 3-88538-110-9. 
• Boto von Querenburg: Mengentheoretische Topologie. 3., neu bearb. und erw. Auflage. Springer, Berlin/Heidelberg/New York 2001, ISBN 978-3-540-67790-1, doi:10.1007/978-3-642-56860-2. 
• Fritz Reinhardt, Heinrich Soeder: dtv-Atlas zur Mathematik. Tafeln und Texte. Bände 1 und 2. 9. und 8. Auflage. Deutscher Taschenbuch Verlag, München 1991 und 1992, ISBN 3-423-03007-0 und ISBN 3-423-03008-9. 
• Matthias Schubert: Mathematik für Informatiker. Ausführlich erklärt mit vielen Programmbeispielen und Aufgaben. 2. Auflage. Vieweg+Teubner, Wiesbaden 2012, ISBN 978-3-8348-1848-5, doi:10.1007/978-3-8348-1995-6. 
• Siegfried Wendt: Nichtphysikalische Grundlagen der Informationstechnik. Interpretierte Formalismen. 2. Auflage. Springer, Berlin/Heidelberg 1991, ISBN 978-3-540-54452-4 (Verträglichkeitsrelation in der Google-Buchsuche). 

Weblinks

Commons: Äquivalenzrelation – Sammlung von Bildern, Videos und Audiodateien

Wikiversity: Äquivalenzrelationen im Rahmen einer Vorlesung über lineare Algebra – Kursmaterialien

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

Einzelnachweise und Anmerkungen

1. Alexandre Buisse, Peter Dybjer: The Interpretation of Intuitionistic Type Theory in Locally Cartesian Closed Categories – an Intuitionistic Perspective. In: Electronic Notes in Theoretical Computer Science. Band 218, 22. Oktober 2008, S. 21–32, hier S. 24, doi:10.1016/j.entcs.2008.10.003. 
2. Man unterscheide den Begriff des Kerns einer Menge: Kern als Bild eines Kernoperators.
3. bezeichnet hier die Verkettung von Relationen.
4. Folge A000110 in OEIS
5. Johannes Köbler: Einführung in die Theoretische Informatik. Humboldt-Universität zu Berlin, S. 38 (WS 2011/12 [PDF; abgerufen am 10. Dezember 2018] Vorlesungsskript). 
6. Notation wie in Symmetric Closure, auf: ProofWiki vom 12. September 2016
7. Man unterscheide den Begriff der mit Relationen verträglichen Abbildung: Homomorphismus als strukturverträgliche Abbildung.
8. Vladimir Borschev, Barbara H. Partee: Linguistics 726: Mathematical Linguistics. Fall semester 2006. University of Massachusetts Amherst, S. 16 (Lectures 1-3. Basic Concepts of Set Theory, Functions and Relations; and Trees [PDF; abgerufen am 10. Dezember 2018] Course script). 
9. M. Das, M. K. Chakraborty, T. K. Ghoshal: Fuzzy tolerance relation, fuzzy tolerance space and basis. In: Fuzzy Sets and Systems. Band 97, Nr. 3, 1. August 1998, S. 361–369, doi:10.1016/S0165-0114(97)00253-4. 
10. Diese lassen sich bei jeder symmetrischen Relation (= partielle Toleranzrelation) bilden.

Normdaten (Sachbegriff): GND: 4141500-0 (lobid, OGND)