Jewiki unterstützen. Jewiki, die größte Online-Enzy­klo­pädie zum Judentum.

Helfen Sie Jewiki mit einer kleinen oder auch größeren Spende. Einmalig oder regelmäßig, damit die Zukunft von Jewiki gesichert bleibt ...

Vielen Dank für Ihr Engagement! (→ Spendenkonten)

How to read Jewiki in your desired language · Comment lire Jewiki dans votre langue préférée · Cómo leer Jewiki en su idioma preferido · בשפה הרצויה Jewiki כיצד לקרוא · Как читать Jewiki на предпочитаемом вами языке · كيف تقرأ Jewiki باللغة التي تريدها · Como ler o Jewiki na sua língua preferida

Äquivalenzrelation

Aus Jewiki
(Weitergeleitet von Repräsentant (Mathematik))
Zur Navigation springen Zur Suche springen

Unter einer Äquivalenzrelation versteht man in der Mathematik eine Relation, die reflexiv, symmetrisch und transitiv ist. Äquivalenzrelationen sind für die Logik und die Mathematik von großer Bedeutung.

  • Eine Äquivalenzrelation teilt eine Menge restlos in disjunkte (elementfremde) Untermengen, Äquivalenzklassen genannt.
  • Die Klassenbildung mit Hilfe des Äquivalenzbegriffes ermöglicht eine mathematische Begriffsbildung.

Äquivalenz – mathematische Gleichwertigkeit

In der Mathematik möchte man in vielen Zusammenhängen Objekte, die sich in gewissen Aspekten ähneln, als gleichwertig ansehen. Eine Formalisierung der Mindestanforderungen an einen solchen Gleichwertigkeitsbegriff ist der Begriff der Äquivalenzrelation.

So ist jeder Begriff, der als die Gleichheit gewisser Eigenschaften definiert werden kann, eine Äquivalenzrelation. Beispiele:

Gleichmächtigkeit endlicher Mengen
Zwei endliche Mengen heißen gleichmächtig, wenn sie dieselbe Anzahl von Elementen haben.
Kongruenz in der Geometrie
Zwei Dreiecke sind kongruent, wenn sie dieselben Seitenlängen haben.
Ähnlichkeit in der Geometrie
Zwei Dreiecke sind ähnlich, wenn sie dieselben Innenwinkel haben.
Kongruenz in der elementaren Zahlentheorie
Zwei ganze Zahlen heißen kongruent modulo , wenn sie bei ganzzahliger Division durch denselben Rest lassen.

Und letztlich gehört auch die Gleichheit selbst dazu.

Definition einer Äquivalenzrelation

Entscheidungsbaum zum Nachweis von Äquivalenzrelationen. Die Reihenfolge, in der man die drei Eigenschaften überprüft, ist natürlich vollkommen willkürlich und daher austauschbar.

Das Wort „äquivalent“ stehe im Folgenden für eine dieser Beziehungen zwischen zwei Objekten; dass zwei Objekte und äquivalent sind, sei durch symbolisiert.

Alle diese Begriffe haben die folgenden drei Eigenschaften:

Jedes Objekt ist zu sich selbst äquivalent.
  • Symmetrie:
Wenn zu äquivalent ist, dann ist auch äquivalent zu (und umgekehrt).
  • Transitivität:
Wenn zu äquivalent und zu äquivalent ist, dann ist äquivalent zu .

Jede Beziehung (zwischen Objekten), die diese Eigenschaften hat, heißt Äquivalenzrelation.

Formale Definition

Eine Äquivalenzrelation auf einer Menge ist eine Teilmenge , welche folgende Bedingungen erfüllt:

Reflexivität
Für alle ist .
Symmetrie
Für alle , für die gilt, ist auch .
Transitivität
Für alle mit und gilt, dass auch .

Üblicherweise schreibt man

oder einfach statt

und dann nehmen diese Forderungen genau die in der Einleitung genannte Form an.

(Hinweis: Eine Relation auf einer Menge ist nach obiger Definition gleich der Menge der in dieser Relation stehenden Paare. Danach ist eine Relation auf einfach eine Menge solcher Paare, das heißt eine Teilmenge des kartesischen Produktes von mit sich selbst.)

Unabhängigkeit der drei Eigenschaften

Tatsächlich sind die Eigenschaften Reflexivität, Symmetrie und 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 .)

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, aber nicht reflexiv: ( ist gleich und nicht 1.)
  • reflexiv und transitiv, aber nicht symmetrisch: ( ist kleiner oder gleich .)
  • reflexiv und symmetrisch, aber nicht transitiv: ( und sind gleich oder benachbart.)

Alle drei Eigenschaften sind erfüllt:

  • reflexiv, symmetrisch und transitiv:

Anschauliches Beispiel

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

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

Für je zwei Nutztiere und aus M soll genau dann gelten, wenn und Tiere derselben Art sind.

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

Reflexivität
Jedes Tier ist von derselben Art wie es selbst.
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.

Keine Äquivalenzrelation ist die Beziehung »ist Bruder von« auf der Menge aller Menschen. Diese Relation ist zwar transitiv, aber weder reflexiv (weil ich nicht mein eigener Bruder bin) noch symmetrisch (weil meine Schwester nicht mein Bruder ist, obwohl ich ihr Bruder bin).

Äquivalenzklassen

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

Die Äquivalenzklasse eines Objektes ist die Klasse der Objekte, die äquivalent zu sind.

Formal: Ist eine Äquivalenzrelation auf einer Menge , so nennt man für ein die Teilmenge

die -Äquivalenzklasse von . Ist aus dem Kontext klar, dass Äquivalenzklassen bezüglich gebildet werden, lässt man den Zusatz weg. Andere Schreibweisen sind

Gibt es für eine Äquivalenzrelation eine spezielle Bezeichnung, beispielsweise „Homotopierelation“, so verwendet man häufig an Stelle von „Äquivalenzklasse“ einen abgeleiteten Terminus, beispielsweise „Homotopieklasse“. Weitere Beispiele: Isomorphieklasse zur Isomorphierelation und Kongruenzklasse zur Kongruenzrelation (hier jedoch meist Restklasse).

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

Hat man für jede Äquivalenzklasse genau ein mit , dann nennt man die Teilmenge ein (vollständiges) Vertreter- oder Repräsentantensystem für .

Menge der Äquivalenzklassen und Index

Die Menge der Äquivalenzklassen (manchmal auch Faktormenge oder Quotientenmenge genannt) einer Äquivalenzrelation auf der Menge ist

In dieser Menge werden die Äquivalenzklassen als eigen- und selbstständige Elemente betrachtet. Die Menge der Äquivalenzklassen entsteht, wenn man äquivalente Elemente „gleichmacht“, indem man sie mittels der untenstehenden kanonischen Abbildung mit der Äquivalenzklasse identifiziert, in der sie liegen. Sie formalisiert also mathematisch den kognitiven Prozess der Identifizierungsabstraktion (siehe auch den Begriff der Teilidentität bei Löringhoff).

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

Es gibt eine kanonische surjektive Abbildung

die jedem Element seine Äquivalenzklasse zuordnet. Diese Abbildung ist nur dann injektiv, wenn es sich bei der Äquivalenzrelation auf M um die sogenannte Diagonale

handelt. ist dann der Graph einer Funktion, nämlich der identischen Abbildung auf M.

Weitere Beispiele

Schulklassen
Die zugrundeliegende Menge ist die Menge aller Schüler auf einer Schule; zwei Schüler seien äquivalent, wenn sie in dieselbe Klasse gehen.
  • Äquivalenzklasse eines Schülers ist die Menge aller seiner Mitschüler der gleichen Schulklasse – allerdings muss er selber mit eingeschlossen und als sein eigener Mitschüler angesehen werden, um Reflexivität zu erhalten.
  • Die Menge der Äquivalenzklassen ist die Menge der Schulklassen.
Gleichheit
Auf einer beliebigen Menge seien zwei Elemente äquivalent, wenn sie gleich sind:
  • Äquivalenzklasse eines Elementes ist die einelementige Menge .
  • Die Menge der Äquivalenzklassen ist die Menge der einelementigen Teilmengen von ; die Abbildung ist eine Bijektion.
Kongruenz in der Zahlentheorie
Die zugrundeliegende Menge ist die Menge der ganzen Zahlen; zwei Zahlen sind äquivalent, wenn sie denselben Rest bei Division durch 5 haben. Eine gleichwertige Formulierung ist: wenn ihre Differenz durch 5 teilbar ist.
  • Äquivalenzklasse einer ganzen Zahl ist die so genannte Restklasse
Brüche
Es sei die Menge der Paare ganzer Zahlen, deren zweiter Eintrag von Null verschieden ist. Zwei Paare und sollen äquivalent heißen, wenn gilt:
  • Die Äquivalenzklasse eines Paares besteht aus allen Paaren (Zähler, Nenner) für Bruchdarstellungen der rationalen Zahl .
  • Die Menge der Äquivalenzklassen wird durch
bijektiv auf die Menge der rationalen Zahlen abgebildet. Ein wichtiger Punkt ist hier die Wohldefiniertheit: wenn gilt, dann ist das Bild nach der obigen Vorschrift
einerseits , andererseits .
Die Äquivalenzrelation war aber gerade so gewählt, dass diese beiden rationalen Zahlen gleich sind.
-Raum
Auf dem Raum der -fach integrierbaren Funktionen kann eine Äquivalenzrelation wie folgt definiert werden: Seien , dann gilt genau dann, wenn bis auf eine Nullmenge gilt. Die Menge aller Äquivalenzklassen bezeichnet man als -Raum. Es gilt also .

Universelle Eigenschaft

Wenn eine Menge ist, so definiert jede Funktion in eine beliebige andere Menge eine Äquivalenzrelation , die manchmal auch als Kern von bezeichnet wird:

Umgekehrt ist jede Äquivalenzrelation Kern einer geeigneten Abbildung , etwa der kanonischen Abbildung , in dieser Schreibweise also .

Modulo

Besondere Bedeutung kommt Äquivalenzrelationen zu, die mit einer algebraischen Struktur auf einer Menge vergleichbar sind. In allen diesen Fällen gibt es einen „Modul“ (von lat. modulus Maß), d. h. eine mit einer algebraischen Verknüpfung in der Ausgangsmenge kompatible Unterstruktur , die die Äquivalenz vermittelt:

     (ggf. auch ),

man nehme nur mit als dem neutralen Element von . Ist stets , dann schreibt man auch

und sagt „ (ist) kongruent modulo [ˈmoːduloː] “ (von lat. modulō Ablativ zu modulus Maß). Grammatikalisch wird modulo im Deutschen verwendet wie eine Präposition, die den Genitiv regiert.

Ist der Modul einfach erzeugt in , bspw. mit einem , dann notiert man auch

.

Diese Sprechweise ist die fast ausschließliche im Ring der ganzen Zahlen .

Auch bei den Äquivalenzklassen oder Nebenklassen spricht man von Äquivalenzklassen modulo und bei der Faktormenge von modulo oder auch modulo und modulo .

Die Faktormenge kann algebraische Struktur von der Ausgangsmenge „erben“. Basiert das Definieren dieses Rechnens modulo auf den Elementen der Ausgangsmenge , also den sog. „Repräsentanten“ der Äquivalenzklassen, muss immer auch die Wohldefiniertheit dieses Rechnens sichergestellt werden. Gelingt dieses und ist die Unterstruktur, die die Äquivalenz vermittelt, so spricht man vom Rechnen modulo .

Beispiel

Sei die symmetrische Gruppe vom Grad 3 und in Zyklenschreibweise eine der 3 Untergruppen der Ordnung 2. Man kann zwar die 3 Nebenklassen

,   und  

bilden (Reihenfolge der Komposition der Zyklen wie im Artikel symmetrische Gruppe). Die geerbte Verknüpfung ist aber nicht von der Wahl des Repräsentanten unabhängig (s. Beispiel im Artikel Wohldefiniertheit).

Wäre jedoch nicht nur Untergruppe, sondern Normalteiler von , ließe sich die geerbte Gruppenoperation auf der Faktorgruppe wohldefinieren.

Weitere Äquivalenzbegriffe

Beispiele für Faktormengen:

Die folgenden Äquivalenzbegriffe entstehen aus der Forderung, dass ein Paar von Abbildungen mit gewissen Eigenschaften zwischen zwei Objekten existiert, die „mehr oder weniger“ invers zueinander sind:

Weitere Beispiele für Äquivalenzrelationen:

Literatur

  • Albrecht Beutelspacher: Lineare Algebra. Eine Einführung in die Wissenschaft der Vektoren, Abbildungen und Matrizen. Mit liebevollen Erklärungen, einleuchtenden Beispielen und lohnenden Übungsaufgaben, nicht ohne lustige Sprüche, launigen Ton und leichte Ironie, dargestellt zu Nutzen der Studierenden der ersten Semester. (Jetzt mit Tipps zur Lösung der Übungsaufgaben).6. durchgesehene und ergänzte Auflage. Vieweg-Verlag, Wiesbaden 2003, ISBN 3-528-56508-X.
  • Gerd Fischer: Lineare Algebra. (Eine Einführung für Studienanfänger). 14. durchgesehene Auflage. Vieweg-Verlag, Wiesbaden 2003, ISBN 3-528-03217-0.
  • Bruno von Freytag gen. Löringhoff: Logik. Ihr System und ihr Verhältnis zur Logistik.W. Europa-Verlag, Zürich u. a. 1955.
  • Matthias Schubert: Mathematik für Informatiker. Ausführlich erklärt mit vielen Programmbeispielen und Aufgaben. Vieweg-Verlag, Wiesbaden 2009, ISBN 978-3-8351-0157-9.

Weblinks

Dieser Artikel basiert ursprünglich auf dem Artikel Äquivalenzrelation aus der freien Enzyklopädie Wikipedia und steht unter der Doppellizenz GNU-Lizenz für freie Dokumentation und Creative Commons CC-BY-SA 3.0 Unported. In der Wikipedia ist eine Liste der ursprünglichen Wikipedia-Autoren verfügbar.