„Äquivalenzrelation“ – Versionsunterschied
[gesichtete Version] | [gesichtete Version] |
K Änderungen von 87.77.139.87 (Diskussion) auf die letzte Version von Ernsts zurückgesetzt Markierung: Zurücksetzung |
Ernsts (Diskussion | Beiträge) Neuer Abschnitt Verallgemeinerungen: Verträglichkeitsrelationen |
||
Zeile 235: | Zeile 235: | ||
Eine solche Konstruktion wird in vielen Gebieten der Mathematik benutzt und ist eine der wichtigsten Anwendungen von Äquivalenzklassen. |
Eine solche Konstruktion wird in vielen Gebieten der Mathematik benutzt und ist eine der wichtigsten Anwendungen von Äquivalenzklassen. |
||
== Verallgemeinerungen == |
|||
Eine reflexive und symmetrische Relation wird auch als ''Verträglichkeitsrelation'' oder ''Toleranzrelation''bezeichnet. Eine verträgliche Relation ist nicht notwendig transitiv, Verträglichkeit ist eine schwächere forderung als Äquivalenz.<ref>Man unterscheide den Begriff ''[[Verträglichkeit (Mathematik)|verträglich]]'' von Abbildungen zwischen relationalen oder algebraischen Strukturen: Homomrphismen als strukturverträgliche Abbildungen.</ref><ref>Wendt 2013, Siegfried Wendt: [https://books.google.de/books?id=dwmgBgAAQBAJ&printsec=frontcover&hl=de#v=onepage Nichtphysikalische Grundlagen der Informationstechnik - Interpretierte Formalismen], Springer-Verlag Berlin Heidelberg, Zeite Auflge 2013, 487 Seiten,{{DOI|10.1007/978-3-642-87627-1}}, ISBN=978-3-540-54452-4. Hier [https://books.google.de/books?id=dwmgBgAAQBAJ&pg=PA31&lpg=PA31&dq=verträglichkeitsrelation&source=bl&ots=E0TyEX16x4&sig=GNw9DT2gBHaPRXJhY2DjZ2hWcg8&hl=de&sa=X&ved=0ahUKEwj-xa_eq9raAhVS6KQKHUptDtEQ6AEIVDAE#v=onepage&q=verträglichkeitsrelation Seite 31]</ref><ref>Zheng Zheng, Hong Hu, Zhongzhi Shi: [http://sourcedb.ict.cas.cn/cn/ictthesis/200907/P020090722606539059923.pdf Tolerance Relation Based Granular Space], Institute of Computing |
|||
Technology, Chinese Academy of Sciences, Beijing, China, 2009, Seiten 682-691, hier: Seite 683, Definition 2.3</ref> (englisch: im finiten Fall ''[[:en:Dependency relation|dependency relation]]'', im transfiniten Fall ''[[:en:Tolerance relation|tolerance relation]]''). Der Begriff wurde von Zeeman und Kalmer eingeführt und spielt eine Rolle in der Biomathematik, Fuzzy-Theorie und Modelltheorie.<ref>M. Das, M.K. Chakraborty, T.K. Ghoshal: [https://www.sciencedirect.com/science/article/pii/S0165011497002534 Fuzzy tolerance relation, fuzzy tolerance space and basis], in: Fuzzy Sets ans Systems, Vol. 97, Issue 3, 1. August 1998, Seiten 361-369, {{DOI|10.1016/S0165-0114(97)002}} [https://www.sciencedirect.com/user/login?targetURL=%2Fscience%2Farticle%2Fpii%2FS0165011497002534%2Fpdf PDF]</ref> |
|||
Anstelle von Äquivalenzklassen und Zerlegungen (Partitionierungen) spricht man hier von Verträglichkeits- oder Toleranzklassen und [[Überdeckung (Mathematik)|Überdeckungen]] (engl.: covering). Sei <math>R</math> eine Ähnlichkeitsrelation auf der Menge (oder Klasse) <math>A</math>. Eine Menge (oder Klasse) <math>B \subseteq A</math> heißt Ähnlichkeits-Präklasse (Toleranz-Präklasse), wenn alle <math>x,y\in B</math> verträglich sind, d. h. es gilt <math>a\ R\ b</math>. Eine maximale Präklasse ist eine Toleranzklasse. Die Menge der Toleranzklassen einer Toleranzrelation <math>R</math> auf einer Menge <math>A</math> ist eine Überdeckung von <math>A</math>. Jede Äquivalenzrelation ist eine Verträglichkeitsrelation, und analog ist jede Zerlegung (Partitionierung) eine Überdeckung.<ref>V. Borschev and B. Partee: [http://people.umass.edu/partee/726_01/lectures/lecture3.pdf Mathematical Linguistics, Lecture 3] 6. September 2001, S. 3] |
|||
== Weitere Äquivalenzbegriffe == |
== Weitere Äquivalenzbegriffe == |
Version vom 27. April 2018, 15:27 Uhr
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 ist grundlegend für viele mathematische Begriffsbildungen.
Ä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 führt zum 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
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:
- Symmetrie
Wenn zu äquivalent ist, dann ist auch äquivalent zu .- Transitivität
Wenn zu äquivalent und zu äquivalent ist, dann ist äquivalent zu .- Reflexivität
Jedes Objekt ist zu sich selbst äquivalent.
Jede Beziehung (zwischen Objekten), die diese Eigenschaften hat, heißt Äquivalenzrelation.
Formale Definition
Eine Äquivalenzrelation auf einer Menge ist eine Teilmenge , die folgende Bedingungen erfüllt:
- Symmetrie
- Für alle , für die gilt, ist auch .
- Transitivität
- Für alle mit und gilt auch .
- Reflexivität
- Für alle gilt .
Üblicherweise schreibt man
- oder einfach statt
und dann nehmen diese Forderungen genau die in der Einleitung genannte Form an.
Das geordnete Paar nennt man in diesem Fall auch Setoid oder E-set (englische Bezeichnung: extensional set, auch Bishop set).[1]
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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/78/Exemplare_von_B%C3%BCchern_mit_eingezeichneter_%C3%84quivalenzrelation.svg/440px-Exemplare_von_B%C3%BCchern_mit_eingezeichneter_%C3%84quivalenzrelation.svg.png)
Ein Beispiel aus der Landwirtschaft soll die eingeführten Begriffe verdeutlichen. Betrachtet sei 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 Für das Huhn gilt aber nicht Die Relation erfüllt die drei Forderungen für Äquivalenzrelationen:
- 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). - Reflexivität
Jedes Tier ist von derselben Art wie es selbst (im Sinne von: Jedes Tier gehört einer Art an).
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 ein Bruder von“ auf der Menge aller Menschen. Sie ist sogar weder reflexiv (weil ich kein Bruder von mir selbst bin) noch symmetrisch (weil meine Schwester kein Bruder von mir ist, obwohl ich ein Bruder von ihr bin) noch transitiv (weil ich kein Bruder von mir selbst bin, obwohl ich ein Bruder meines Bruders bin und dieser ein Bruder von mir ist).
Äquivalenzklassen
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/3d/Exemplare_von_B%C3%BCcher_mit_eingezeichneter_%C3%84quivalenzrelation_und_%C3%84quivalenzklassen.svg/440px-Exemplare_von_B%C3%BCcher_mit_eingezeichneter_%C3%84quivalenzrelation_und_%C3%84quivalenzklassen.svg.png)
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
von 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.
Die kanonische surjektive Abbildung
die jedem Element seine Äquivalenzklasse zuordnet, heißt Quotientenabbildung. Diese Abbildung ist nur dann injektiv, wenn es sich bei der Äquivalenzrelation auf um die sogenannte Diagonale
handelt. ist dann der Graph einer Funktion, nämlich der identischen Abbildung auf .
Partielle Äquivalenzrelation
Eine Relation auf einer Menge heißt partielle (oder beschränkte) Äquivalenzrelation, wenn sie symmetrisch und transitiv ist. Mit anderen Worten: Für alle muss gelten:
- Symmetrie
- Transitivität
Ist die Relation zusätzlich reflexiv, dann handelt es sich um eine (totale) Äquivalenzrelation.
Jede partielle Äquivalenzrelation auf einer Menge ist auf der Untermenge
eine totale Äquivalenzrelation. Die durch die Äquivalenzklassen definierte Zerlegung von in Äquivalenzklassen heißt auch partielle Zerlegung von .
Eine partielle Äquivalenzrelation kann auf verschiedene Weise zu einer (totalen) Äquivalenzrelation fortgesetzt werden:
- (alle aus bilden eine eigene Äquivalenzklasse) oder
- (die Äquivalenzklassen von sind die von , ergänzt um die Restmenge wie oben).
Das Ergebnis ist jeweils eine totale Zerlegung von .
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 (Identität)
- Auf einer beliebigen Menge seien zwei Elemente äquivalent, wenn sie gleich sind:
- Als Bezeichner finden sich die Notationen , und , mengentheoretisch handelt es sich um die Diagonale:[2]
- Es gilt:
- Die Äquivalenzklasse eines Elementes ist die einelementige Menge .
- Die Menge der Äquivalenzklassen ist die Menge der einelementigen Teilmengen von ; die Abbildung ist eine Bijektion.
- Für die Verkettung mit beliebigen Relationen auf gilt:
- (Einselement)
- Allrelation
- Auf einer beliebigen Menge seien je zwei Elemente äquivalent:
- für alle
- Als Bezeichner für die Allrelation findet man die Notationen oder , mengentheoretisch handelt es sich um das kartesische Produkt von mit sich selbst:[2]
- Es gilt:
- Die Äquivalenzklasse jedes Elementes ist die ganze Menge .
- Die Menge der Äquivalenzklassen ist die einelementige Menge ; die Abbildung ist konstant.
- Für die Verkettung mit beliebigen reflexiven Relationen auf gilt:
- (Nullelement)
- Beliebige Partition einer Menge
- 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 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[3] 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 Menge der Äquivalenzklassen ist die sechselementige Menge .
- 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:
- Äquivalenzklasse einer reellen Zahl ist die abzählbar unendliche Menge der mit kommensurablen Zahlen; Äquivalenzklasse der Zahl ist die einelementige Menge
- Die Menge der Äquivalenzklassen ist überabzählbar. Anders als bei anderen ähnlich einfachen Äquivalenzrelationen bietet sich hier kein Repräsentantensystem an.
- 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 sogenannte Restklasse
- Die Menge der Äquivalenzklassen ist der Restklassenring
- 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 Abbildung in eine beliebige andere Menge eine Äquivalenzrelation , die manchmal auch als Kern von mit bezeichnet wird:
- , d. h.:
Umgekehrt ist jede Äquivalenzrelation Kern einer geeigneten Abbildung , etwa der kanonischen Abbildung , in dieser Schreibweise also .
Für partielle Abbildungen in eine beliebige andere Menge liefert die obige Definition in Analogie als Kern eine partielle Äquivalenzrelation
und jede partielle Äquivalenzrelation ist Kern einer geeigneten partiellen Abbildung.
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 [ ] “ (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ßlich verwendete 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 das 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
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.
Reflexiv-transitive Hülle
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, bspw. mit vorgegebenen Verknüpfungen verträglich ist (d. h. eine Kongruenzrelation ist).
Sei eine Menge gegeben und eine beliebige Relation . Dann kann die durch erzeugte Äquivalenzrelation auch dadurch beschrieben werden, dass genau dann gilt, wenn
- oder
- Es gibt endlich viele Elemente mit , und für jeweils oder .
Die neue Relation wird reflexiv-transitive Hülle von genannt.
Kongruenzrelationen
In der Mathematik beschäftigt man sich hauptsächlich mit Mengen, auf denen eine Struktur definiert ist, beispielsweise durch Verknüpfungen eine algebraische, durch eine Ordnungsrelation eine Ordnungsstruktur, durch eine Metrik oder eine Topologie ein metrischer oder topologischer Raum, oder durch Definition von Kanten und anderen Eigenschaften ein Graph. Im Folgenden wird nur der einfachste Fall betrachtet, dass eine Struktur allein durch die Trägermenge mit Funktionen und Relationen darauf definiert ist (Struktur erster Stufe).
Im Allgemeinen hat eine Äquivalenzrelation auf einer Menge nichts mit den Strukturen zu tun, die auf der Menge definiert sein können. Oft interessiert man sich jedoch für den Fall, dass eine Äquivalenzrelation mit der Struktur verträglich ist, d. h., dass für alle zur Struktur gehörigen Funktionen und Relationen gilt:
- Ist , so gilt:
Eine solche mit der Struktur verträgliche Äquivalenzrelation heißt dann eine Kongruenzrelation auf der Struktur – nicht auf der Menge, denn die Funktionen und Relationen sind für die Menge allein nicht definiert.
Der Kern eines Homomorphismus zwischen algebraischen Strukturen ist eine Kongruenzrelation.
Hat man eine Kongruenzrelation auf einer Struktur mit der Trägermenge , so lassen sich auf der Menge der Äquivalenzklassen dieselben Funktionen und Relationen definieren, indem man von jeder beteiligten Klasse jeweils einen Repräsentanten nimmt, diese Repräsentanten wie in der Ausgangsstruktur verknüpft und dann wieder zur Äquivalenzklasse übergeht. Aufgrund der Verträglichkeit ist das Resultat von der Wahl des Repräsentanten unabhängig. Ist dann mit diesen Funktionen und Relationen eine Struktur gleicher Art wie die Ausgangsstruktur, spricht man von einer Faktor- oder Quotientenstruktur, z. B. einem Quotientenkörper oder -raum. Ein bekanntes Beispiel sind die Restklassenringe ganzer Zahlen, die Quotientenringe des Rings der ganzen Zahlen sind.
Eine solche Konstruktion wird in vielen Gebieten der Mathematik benutzt und ist eine der wichtigsten Anwendungen von Äquivalenzklassen.
Verallgemeinerungen
Eine reflexive und symmetrische Relation wird auch als Verträglichkeitsrelation oder Toleranzrelationbezeichnet. Eine verträgliche Relation ist nicht notwendig transitiv, Verträglichkeit ist eine schwächere forderung als Äquivalenz.[4][5][6] (englisch: im finiten Fall dependency relation, im transfiniten Fall tolerance relation). Der Begriff wurde von Zeeman und Kalmer eingeführt und spielt eine Rolle in der Biomathematik, Fuzzy-Theorie und Modelltheorie.[7]
Anstelle von Äquivalenzklassen und Zerlegungen (Partitionierungen) spricht man hier von Verträglichkeits- oder Toleranzklassen und Überdeckungen (engl.: covering). Sei eine Ähnlichkeitsrelation auf der Menge (oder Klasse) . Eine Menge (oder Klasse) heißt Ähnlichkeits-Präklasse (Toleranz-Präklasse), wenn alle verträglich sind, d. h. es gilt . Eine maximale Präklasse ist eine Toleranzklasse. Die Menge der Toleranzklassen einer Toleranzrelation auf einer Menge ist eine Überdeckung von . Jede Äquivalenzrelation ist eine Verträglichkeitsrelation, und analog ist jede Zerlegung (Partitionierung) eine Überdeckung.<ref>V. Borschev and B. Partee: Mathematical Linguistics, Lecture 3 6. September 2001, S. 3]
Weitere Äquivalenzbegriffe
Beispiele für Faktormengen:
- Faktorraum (für Vektorräume)
- Faktorgruppe (für Gruppen)
- Faktorring (für Ringe)
- Kongruenzrelation (für allgemeine algebraische Strukturen)
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:
- Vervollständigung durch Äquivalenzklassen von Cauchy-Folgen
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. Kohlhammer, Stuttgart 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
Einzelnachweise
- ↑ 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. 218 (2008) 21–32.
- ↑ a b Siehe auch Homogene Relationen.
- ↑ Folge A000110 in OEIS
- ↑ Man unterscheide den Begriff verträglich von Abbildungen zwischen relationalen oder algebraischen Strukturen: Homomrphismen als strukturverträgliche Abbildungen.
- ↑ Wendt 2013, Siegfried Wendt: Nichtphysikalische Grundlagen der Informationstechnik - Interpretierte Formalismen, Springer-Verlag Berlin Heidelberg, Zeite Auflge 2013, 487 Seiten,doi:10.1007/978-3-642-87627-1, ISBN=978-3-540-54452-4. Hier Seite 31
- ↑ Zheng Zheng, Hong Hu, Zhongzhi Shi: Tolerance Relation Based Granular Space, Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China, 2009, Seiten 682-691, hier: Seite 683, Definition 2.3
- ↑ M. Das, M.K. Chakraborty, T.K. Ghoshal: Fuzzy tolerance relation, fuzzy tolerance space and basis, in: Fuzzy Sets ans Systems, Vol. 97, Issue 3, 1. August 1998, Seiten 361-369, doi:10.1016/S0165-0114(97)002 PDF