Äquivalenzrelation

Relation, die reflexiv, symmetrisch und transitiv ist
(Weitergeleitet von Repräsentantensystem)

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

Bearbeiten

Äquivalenz

Bearbeiten

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

 .

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

Bearbeiten
 
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:

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).[1]

Äquivalenzklassen

Bearbeiten
 
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

  sowie  .

Repräsentantensysteme

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

 .[3]

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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

Reflexiv, symmetrisch und transitiv:

 .

Beispiele

Bearbeiten

Nutztiere in einem landwirtschaftlichen Betrieb

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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[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   ist diejenige Menge  , die   enthält.
  • Die Quotientenmenge ist die sechselementige Menge  .

Rationale Zahlen

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

  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

Bearbeiten

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  [5]

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

 .

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

Spezielle Äquivalenzen

Bearbeiten

Gleichmächtigkeit von Mengen

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

Partielle Äquivalenzrelation

Bearbeiten

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

  für alle  .

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

  für alle  .

Quasiordnung

Bearbeiten

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

Bearbeiten

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   eine Toleranzrelation auf der Menge (oder Klasse)  . Eine Teilmenge (oder -klasse)   heißt Verträglichkeits- oder Toleranzpräklasse, falls alle   miteinander tolerant sind:[8]

 .

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

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

Weitere Äquivalenzbegriffe

Bearbeiten

Literatur

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

Einzelnachweise und Anmerkungen

Bearbeiten
  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. a b c 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.