Kurs:Topologische Invertierbarkeitskriterien/B-Regularität/Von Äquivalenzklassen zum Ideal

Einleitung

Bearbeiten

Diese Seite kann als Wiki2Reveal Folien angezeigt werden. Einzelne Abschnitte werden als Folien betrachtet und Änderungen an den Folien wirken sich sofort auf den Inhalt der Folien aus.

Zielsetzung

Bearbeiten

Diese Lernressource hat das Ziel, den Zusammenhang von Äquivalenzklassen bis hin zum Ideal zu behandeln. Die Gemeinsamkeiten und Unterschiede zwischen den damit zusammenhängenden Aspekten führen dann zu eine Quotientenraum bzgl. eines Ideals  , der dann die Algebraerweiterung   bildet, in der ein   invertierbar ist.

Einführung

Bearbeiten

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 zerlegt den Polynomraum   in Mengen, die dann die Elemente der Algebraerweiterung   bilden.

Äquivalenz

Bearbeiten

In der Mathematik werden Objekte, die sich in einem bestimmten Zusammenhang gleichen, als gleichwertig bzw. äquivalent angesehen. Auf Polynomraum   werden dabei zwei Polynome   als äquivalent angesehen, wenn die Differenz   also ein Element eines Ideals  ist.

Äquivalenz als spezielle Relation

Bearbeiten

Ein solcher Zusammenhang lässt sich für alle Elemente einer nichtleeren Menge   stets durch eine Relation   darstellen, indem man genau dann zwei Elemente   als zueinander „äquivalent“ bezeichnet und diese Beziehung durch   symbolisiert, wenn das Paar   also ein Element der Relation ist. Diese Relation wird zu einer Äquivalenzrelation, wenn 3 Eigenschaften erfüllt sind.

Definition - Äquivalenzrelation

Bearbeiten

Eine Relation   auf einer nichtleeren Menge   heißt Äquivalenzrelation, wenn diese die folgenden drei Eigenschaften erfüllt:

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

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

Schreibweise

Bearbeiten

Wie bei zweistelligen Relationen üblich, schreibt man statt   auch einfacher  , dann nehmen diese Eigenschaften die oben genannte Form an.

Polynomalgebra - Relation

Bearbeiten

Die Polynome   stehen in Relation  , wenn gilt  . Dabei ist   ein Ideal bzw. das abgeschlossene Hauptideal bzgl.   und   mit   die gesuchte Algebraerweiterung.

Beispiel

Bearbeiten
  • Gleichheit von Brüchen ist eine Äquivalenzrelation  , Dabei gibt es unterschiedliche Zahldarstellungen, die die gleiche Zahl darstellen.
  • Den gleichen Anfangsbuchstaben beim Nachnamen zu haben, fasst Namen zu einer Äquivalenzklasse zusammen, die den gleichen Anfangsbuchstaben besitzen (hilfreich bei alphabetischen Ordnungsprinzipien in Telefonbüchern und Nachschlagewerken).
  • Bei Restklassen werden ganze Zahlen zu einer Äquivalenzklasse zusammengefasst, wenn diese bei Division den gleichen Rest lassen.

Terminologie

Bearbeiten

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  .

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.

Mächtigkeit

Bearbeiten

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.

Bemerkung - Quotientenabbildung

Bearbeiten

Diese Abbildung ist nur dann injektiv, wenn es sich bei der Äquivalenzrelation auf   um die Identitätsrelation   handelt.

Homomorphismen

Bearbeiten

Homomorphismen als strukturerhaltende Abbildungen findet man z.B. bei

  • Gruppenhomomorphismen,
  • Vektorraumhomomorphismen (Lineare Abbildungen)
  • Algebrahomomorphismen (Vektorräume mit eine Multiplikation als innere Verknüpfung)

liefern als Eigenschaften die Verträglichkeit mit den Verknüpfungen auf dem Grundraum.

Gruppenhomomorphismus

Bearbeiten

Gegeben seien zwei Gruppen   und   Eine Funktion   heißt Gruppenhomomorphismus, wenn für alle Elemente   gilt:

 

Vektorraumhomomorphismus - Lineare Abbildung

Bearbeiten

Gegeben seien zwei Vektorräume   und  . Eine Funktion   heißt Vektorraumhomomorphismus oder linear, wenn für alle Elemente   und   gilt:

  •   und
  •  

Dabei wurden hier die innere additive Verknüpfung und äußere Verknüpfung einmal indiziert, um deutlich zu machen, dass es sich um unterschiedliche Verknüpfungen handelt. Diese Unterscheidung wird in der Regel vernachlässigt.

Algebrahomomorphismus

Bearbeiten

Gegeben seien zwei Algebren   und  . Eine Funktion   heißt Algebrahomomorphismus, wenn für alle Elemente   und   gilt:

  •   und
  •  
  •  

Dabei wurden die multiplikative innere Verknüpfungen   bzw.   zur Unterscheidung mit der Multiplikation mit Skalaren   bzw.   unterschiedlich bezeichnet. Diese Unterscheidung wird in der Regel vernachlässigt und wurde nur hier zur Darstellung der Strukturerhaltung verwendet.

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.

Ä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[2] 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  

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

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

 .

Dabei bezeichnet   die symmetrische Hülle,[4]   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-[5] oder Toleranzrelation[6] 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.[7]

Bezeichne   eine Toleranzrelation auf der Menge (oder Klasse)  . Eine Teilmenge (oder -klasse)   heißt Verträglichkeits- oder Toleranzpräklasse, falls alle   miteinander tolerant sind:[6]

 .

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

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

Weitere Äquivalenzbegriffe

Bearbeiten

Literatur

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

Vorlage:Wikiversity    Wikibooks: Mathe für Nicht-Freaks: Äquivalenzrelation – Lern- und Lehrmaterialien



Aufgaben für Studierende

Bearbeiten

Quellennachweise

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. Vorlage:OEIS
  3. 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).
  4. Notation wie in Symmetric Closure, auf: ProofWiki vom 12. September 2016
  5. Man unterscheide den Begriff der mit Relationen verträglichen Abbildung: Homomorphismus als strukturverträgliche Abbildung.
  6. 6,0 6,1 6,2 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).
  7. 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.
  8. Diese lassen sich bei jeder symmetrischen Relation (= partielle Toleranzrelation) bilden.


Siehe auch

Bearbeiten


Seiteninformation

Bearbeiten

Diese Lernresource können Sie als Wiki2Reveal-Foliensatz darstellen.

Wiki2Reveal

Bearbeiten

Dieser Wiki2Reveal Foliensatz wurde für den Lerneinheit Kurs:Topologische Invertierbarkeitskriterien' erstellt der Link für die Wiki2Reveal-Folien wurde mit dem Wiki2Reveal-Linkgenerator erstellt.


Wikipedia2Wikiversity

Bearbeiten

Diese Seite wurde auf Basis der folgenden Wikipedia-Quelle erstellt: