Ä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:
 Jedes Objekt  ist zu sich selbst äquivalent:   .
 Wenn  äquivalent zu  ist, dann ist auch  äquivalent zu :   .
 Wenn  äquivalent zu  und  äquivalent zu  ist, dann ist auch  äquivalent zu :    und .

Äquivalenzrelation 

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

 Reflexivität
  für alle .

 Symmetrie
  für alle .

 Transitivität
  und  für alle .

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 

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

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
  für alle 
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:
    ( ist um 1 größer als ).

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:
    ( ist höchstens um 1 größer als ).

Symmetrisch, aber weder reflexiv noch transitiv:
    ( und  sind benachbart).

Transitiv, aber weder reflexiv noch symmetrisch:
    ( ist kleiner als ).

Genau zwei der drei Eigenschaften sind erfüllt 
Symmetrisch und transitiv (partielle Äquivalenzrelation), aber nicht reflexiv:
    ( ist gleich  und nicht 1).

Reflexiv und transitiv (Quasiordnung), aber nicht symmetrisch:
    ( ist kleiner oder gleich ).

Reflexiv und symmetrisch (Toleranzrelation), aber nicht transitiv:
    ( und  sind gleich oder benachbart).

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 je zwei Nutztiere  und  aus  soll  genau dann gelten, wenn  und  Tiere derselben Art sind.
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:

 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  und  Tiere derselben Art sind und ebenso  und  von derselben Art sind, dann sind auch  und  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.

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:
    (neutrales Element).

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:
    (absorbierendes Element).

Ä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
  und  sind einander ähnlich
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
  und  sind kongruent
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 L2-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  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
  offen in 
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:
  ist Äquivalenzrelation auf  mit 

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
  und  sind gleichmächtig
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
  und  sind isomorph.

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:
 Jedes  bildet eine eigene Äquivalenzklasse : 
 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
  für alle .

Umgekehrt liefert eine partielle Äquivalenzrelation auf  stets eine surjektive partielle Quotientenabbildung
  für alle .

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

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

Weblinks

Einzelnachweise und Anmerkungen 

Mathematischer Grundbegriff
Mengenlehre