Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 10

Die Entscheidung fiel aber ohne längere Diskussion auf Vorli, weil sie zugewandt, feinfühlig, verständnisvoll, lieb, zuvorkommend, aufmunternd, hilfsbereit, aufmerksam und wuschelig ist.




Äquivalenzrelationen

In der Mathematik sind Formulierungen, dass mathematische Objekte „äquivalent“ sind, allgegenwärtig. Zumeist geht es um Situationen, wo Objekte zwar nicht gleich, aber doch in gewisser Hinsicht, unter einem bestimmten Gesichtspunkt, als gleichwertig zu betrachten sind. In solchen Kontexten darf man Objekte durch gleichwertige Objekte ersetzen, um eine Situation zu vereinfachen. Es gibt keine allgemeine Definition von „äquivalent“, da es im Allgemeinen eine Vielzahl von konkurrierenden Gesichtspunkten gibt, unter denen man Objekte als äquivalent ansehen möchte oder nicht. Man kann aber strukturelle Bedingungen herausarbeiten, die zueinander äquivalente Objekte stets erfüllen. Insofern ist Äquivalenz eine spezielle Art einer Relation auf einer Menge.


Definition  

Eine Äquivalenzrelation auf einer Menge ist eine Relation , die die folgenden drei Eigenschaften besitzt (für beliebige ).

  1. Es ist (reflexiv).
  2. Aus folgt (symmetrisch).
  3. Aus und folgt (transitiv).

Dabei bedeutet , dass das Paar zu gehört.


Beispiel  

Das Urbeispiel für eine Äquivalenzrelation ist die Gleichheit auf einer beliebigen Menge . Unter der Gleichheit ist jedes Element nur mit sich selbst äquivalent.



Beispiel  

Auf jeder Menge gibt es die Äquivalenzrelation, unter der alle Elemente zueinander in Relation stehen.


Gnus bilden eine Äquivalenzklasse (eine vollständige Menge aus zueinander äquivalenten Elemente, siehe die nächste Vorlesung für die Definition) bezüglich der Äquivalenzrelation der Gleichartigkeit, ebenso Zebras.

Beispiel  

Häufig interessiert man sich gar nicht so genau für einzelne Objekte, sondern nur für bestimmte Eigenschaften davon. Objekte, die sich bezüglich einer bestimmten, genau definierten Eigenschaft gleich verhalten, kann man dann (bezüglich dieser Eigenschaft) als äquivalent betrachten. Offenbar handelt es sich dabei um eine Äquivalenzrelation. Wenn man sich beispielsweise nur für die Farbe von Objekten interessiert, so sind alle Objekte, die (exakt) gleichfarbig sind, zueinander äquivalent. Wenn man sich bei Tieren nicht für irgendwelche individuellen Eigenschaften interessiert, sondern nur für ihre Art, so sind gleichartige Tiere äquivalent, d.h. zwei Tiere sind genau dann äquivalent, wenn sie zur gleichen Art gehören. Studierende kann man als äquivalent ansehen, wenn sie die gleiche Fächerkombination studieren. Vektoren kann man als äquivalent ansehen, wenn sie zum Nullpunkt den gleichen Abstand besitzen, etc. Eine Äquivalenzrelation ist typischerweise ein bestimmter Blick auf bestimmte Objekte, der unter Bezug auf eine gewisse Eigenschaft gewisse Objekte als gleich ansieht.


Bei den zuletzt genannten „alltäglichen“ Beispielen muss man etwas vorsichtig sein, da im Allgemeinen die Eigenschaften nicht so genau definiert werden. Im Alltag spielt Ähnlichkeit eine wichtigere Rolle als Gleichheit hinsichtlich einer bestimmten Eigenschaft. Die Ähnlichkeit ist aber keine Äquivalenzrelation, da sie zwar reflexiv und symmetrisch ist, aber nicht transitiv. Wenn und zueinander (knapp) ähnlich sind und und ebenso, so kann und schon knapp unähnlich sein (ebenso: lebt in der Nachbarschaft von, ist verwandt mit, etc.).


Beispiel  

In der Wohnung liegt eine große Menge von Wäsche herum, die gewaschen werden soll. Natürlich kann nicht alles in den gleichen Waschgang, sondern nur Sachen, die sowohl gleichfarbig sind als auch die gleiche Waschtemperatur vertragen. Dies definiert insgesamt die Äquivalenzrelation der Waschgangverträglichkeit. Man kann jetzt die Wäsche dadurch sortieren, dass man waschgangverträgliche Sachen jeweils zu einem Haufen zusammenfasst. So entstehen verschiedene Haufen, die jeweils aus untereinander waschgangverträglichen Sachen bestehen, und zwei Sachen landen genau dann auf dem gleichen Haufen, wenn sie waschgangverträglich sind. Eine wichtige Beobachtung dabei ist, dass die Haufen nicht anhand einer vorgegebenen Liste von möglichen Waschkombinationen entstehen, sondern allein durch die Verträglichkeitsüberprüfung der Objekte untereinander.



Beispiel  

Es sei eine Menge von geometrischen Objekten, beispielsweise eine Menge von -Ecken, gegeben, die sortiert werden sollen. Die Sortierung soll vollständig sein und jedem Objekt genau einen Typ zuweisen. Objekte, die den gleichen Typ repräsentieren, heißen äquivalent (im Sinne der Sortierung). Dafür gibt es verschiedene Möglichkeiten, die mehr oder weniger natürlich sind. Eine naheliegende Möglichkeit bei den -Ecken ist es, sie nach der Anzahl der Ecken zu sortieren. Zwei Objekte sind genau dann äquivalent, wenn sie die gleiche Anzahl an Ecken besitzen. Man kann sie aber auch nach der Farbe oder gemäß der Person, die die Figur gemalt hat, oder nach dem Flächeninhalt sortieren.

Oder man kann eine Menge von gegebenen Vierecken gemäß gewisser (geometrisch relevanter) Eigenschaften sortieren. Wenn man sich nur auf eine Eigenschaft konzentriert, beispielsweise, ob ein Viereck ein Rechteck ist oder nicht, so gibt es nur zwei Typen bzw. Klassen. Man kann natürlich auch eine feinere Einteilung vornehmen. Man beachte dabei allerdings, dass die mathematischen Begriffe inklusiv sind (ein Quadrat ist insbesondere ein Rechteck), eine vollständige Aufteilung ergibt sich also nur dann, wenn man Konzepte wie Quadrat, Rechteck, aber kein Quadrat, Parallelogramm, aber kein Rechteck, etc. verwendet. Es gibt keine natürliche optimale Aufteilung der Menge aller Vierecke. Ein typisches Phänomen bei solchen Klassifikationen ist, dass es einen großen Rest von Objekten gibt, der außerhalb jedes Regularitätskonzeptes liegt.



Beispiel  

Es sei eine Menge von Aussagen. Dann ist die Äquivalenz, also die logische Gleichwertigkeit, von Aussagen eine Äquivalenzrelation auf dieser Menge. Beispielsweise ist die Aussage aufgrund des Kontrapositionsprinzips äquivalent zu , oder die Aussage „ ist ein Teiler von “ ist äquivalent zu „ ist ein Vielfaches von “ oder zu „“.



Beispiel  

Es sei eine Menge von Termen. Zwei Terme sind nur dann gleich, wenn sie Zeichen für Zeichen gleich sind. Wenn man allerdings einen mathematischen Kontext zugrunde legt, wie, dass sich alle Terme auf einen kommutativen Halbring beziehen sollen, so ergibt sich auf der Menge der Terme eine Äquivalenzrelation dadurch, dass man Terme als äquivalent (gleichwertig) ansieht, wenn sie bei jeder (oder einer bestimmten) Interpretation in einem kommutativen Halbring das gleiche Element liefern. In diesem Sinne sind und oder und gleichwertige Terme. Ebenso sind die Bruchterme und als Terme verschieden, ihr Zahlwert in ist aber gleich.



Beispiel  

Es sei ein Körper und eine Variablenmenge fixiert. Wir betrachten die Menge der (endlichen) linearen Gleichungssysteme in diesen Variablen über diesem Körper. Die Äquivalenz von linearen Gleichungssystemen, also die Übereinstimmung der Lösungsmengen (als Teilmengen im ), ist dann offenbar eine Äquivalenzrelation auf dieser Menge.


Die Gleichheit bezüglich einer Eigenschaft wird durch folgende mathematische Konstruktion präzisiert.



Lemma

Es seien und Mengen und sei eine Abbildung.

Dann wird durch die Festlegung

wenn

eine Äquivalenzrelation auf definiert.

Beweis

Siehe Aufgabe 10.9.


Prinzipiell kann man jede Äquivalenzrelation mit Hilfe einer Abbildung beschreiben, siehe die nächste Vorlesung. Wenn die Abbildung injektiv ist, so ist die durch auf definierte Äquivalenzrelation die Gleichheit. Wenn die Abbildung konstant ist, so sind unter der zugehörigen Äquivalenzrelation alle Elemente aus untereinander äquivalent.


Beispiel  

Es sei ein Körper. Wir sagen, dass zwei Zahlen „bis (eventuell) auf das Vorzeichen“ übereinstimmen, wenn oder ist. Dafür schreiben wir kurz

Dies ist eine Äquivalenzrelation. Dabei ist die Reflexivität unmittelbar klar, die Symmetrie erhält man, indem man die Gleichung mit multipliziert und ausnutzt. Ähnlich wird auch die Transitivität begründet. Diese Äquivalenzrelation lässt sich auch einfach im Sinne von Lemma 10.10 beschreiben. Es ist nämlich genau dann, wenn gilt. Dabei ist die Hinrichtung klar. Für die Rückrichtung sei also . Bei ist auch und die Aussage gilt, seien also die Zahlen von verschieden. Durch Division durch erhält man

Wegen und Lemma 5.14 sind aber und die einzigen Lösungen der Gleichung

in einem Körper, und somit ist und . In einem angeordneten Körper gilt darüber hinaus auch genau dann, wenn gilt. Es gibt also im Allgemeinen mehrere Funktionen, mit denen man eine Äquivalenzrelation erfassen kann.



Beispiel  

Es sei ein archimedisch angeordneter Körper. Wir betrachten die Gaußklammer auf , also die Abbildung

Eine Zahl wird also auf die größte ganze Zahl abgebildet, die kleiner oder gleich ist (die „Vorkommazahl“, falls die Zahl positiv ist[1]). Dabei wird das gesamte ganzzahlige einseitig offene Intervall

auf abgebildet. Bezüglich dieser Abbildung sind also zwei Zahlen genau dann äquivalent, wenn sie im gleichen ganzzahligen Intervall liegen.

Statt dem ganzzahligen Anteil kann man auch den (nichtnegativen) Bruchanteil (bei positiven Zahlen die „Nachkommazahl“) betrachten. Das ist die Abbildung

Unter der durch diese Abbildung definierten Äquivalenzrelation sind zwei Zahlen genau dann gleich, wenn sie den gleichen Bruchanteil besitzen, und das ist genau dann der Fall, wenn ihre Differenz eine ganze Zahl ist.

Wenn man rationale Zahlen als gemischte Brüche schreibt, so geht es um die Frage, ob der ganzzahlige Anteil oder ob der Bruchanteil übereinstimmt.


Unter der Äquivalenzrelation „erreichbar auf dem Landweg“ sind Inseln und Kontinente die Äquivalenzklassen.

Beispiel  

Es sei eine Situation gegeben, wo gewisse Orte (oder Objekte) von gewissen anderen Orten aus erreichbar sind oder nicht. Die Erreichbarkeit kann dabei durch die Wahl eines Verkehrsmittels oder durch eine abstraktere (Bewegungs)-Vorschrift festgelegt sein. Solche Erreichbarkeitsrelationen liefern häufig eine Äquivalenzrelation. Dass ein Ort von sich selbst aus erreichbar ist, sichert die Reflexivität. Die Symmetrie der Erreichbarkeit besagt, dass wenn man von nach kommen kann, dass man dann auch von nach kommen kann. Das ist nicht für jede Erreichbarkeit selbstverständlich, für die meisten aber schon. Die Transitivität gilt immer dann, wenn man die Bewegungsvorgänge hintereinander ausführen kann, also zuerst von nach und dann von nach . Wenn erreichbar beispielsweise dadurch gegeben ist, dass man auf dem Landweg von einem Ort zu einem anderen kommen kann, so sind zwei Ortspunkte genau dann äquivalent, wenn sie auf der gleichen Insel (oder dem gleichen Kontinent) liegen.



Beispiel  

Es sei fixiert. Wir betrachten auf die Äquivalenzrelation , bei der zwei Zahlen als äquivalent betrachtet werden, wenn ihre Differenz ein Vielfaches von ist. Zwei Zahlen sind also zueinander äquivalent, wenn man von der einen Zahl zu der anderen durch Sprünge der Sprungweite gelangen kann. Unter Verwendung der Division mit Rest bedeutet dies, dass zwei Zahlen zueinander äquivalent sind, wenn sie bei Division durch den gleichen Rest ergeben.


Mit Hilfe der Abbildung , die jeder ganzen Zahl den Rest bei Division durch zuordnet, kann man das vorstehende Beispiel auch direkt mit Lemma 10.10 erfassen.


Beispiel  

Visualisierung des Beispiels

Wir betrachten die Produktmenge , die wir uns als ein Punktgitter vorstellen. Wir fixieren die Sprünge (man denke an Springmäuse, die alle diese Sprünge ausführen können)

und sagen, dass zwei Punkte äquivalent sind, wenn man ausgehend von den Punkt mit einer Folge von solchen Sprüngen erreichen kann. Dies ist eine Äquivalenzrelation (dafür ist entscheidend, dass bei den Sprüngen auch der entgegengesetzte Sprung dazu gehört). Typische Fragestellungen sind: Wie kann man äquivalente Felder charakterisieren, wie entscheiden, ob zwei Felder äquivalent sind oder nicht?



Beispiel  

Es sei die Menge aller Dreiecke (in der reellen Ebene). Zwei Dreiecke und heißen kongruent, wenn es eine (eventuell uneigentliche) Bewegung gibt, die das eine Dreieck in das andere Dreieck überführt. Eine Bewegung soll dabei die Längen und die Winkel erhalten. Eine solche Bewegung setzt sich zusammen aus einer Verschiebung, einer Achsenspiegelung und einer Drehung[2] (in beliebiger Reihenfolge, beliebig oft angewendet). Die Kongruenz von Dreiecken ist eine Äquivalenzrelation. Ein Dreieck ist zu sich selbst kongruent, da es durch die identische Bewegung in sich überführt wird. Wenn durch eine bestimmte Bewegung in überführt wird, so wird durch die entgegengesetzte Bewegung, also , das zweite Dreieck in überführt. Die Kongruenz ist also symmetrisch. Wenn drei Dreiecke gegeben sind, wobei zu und zu kongruent sind, so gibt es eine Bewegung , die in überführt, und eine Bewegung , die in überführt. Dann hat die Gesamtbewegung die Eigenschaft, dass sie insgesamt in überführt. Ebenso ist die eigentliche Kongruenz, bei der nur eigentliche Bewegungen (also keine Achsenspiegelungen) erlaubt sind, eine Äquivalenzrelation.




Fußnoten
  1. Mit dieser Formulierung muss man bei negativen Zahlen vorsichtig sein. Die Zahl besitzt die Gaußklammer und den Bruchanteil .
  2. Diese Abbildungen sind aus der Schule bekannt.


<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)