Kurs:Grundkurs Mathematik (Osnabrück 2022-2023)/Teil II/Vorlesung B/Referenzsuche

In dieser Vorlesung möchten wir verstehen, wie man an der beschreibenden Matrix zu einer linearen Abbildung erkennen kann, ob diese bijektiv ist, und wann ein lineares Gleichungssystem

die Eigenschaft besitzt, dass es für jedes eine eindeutige Lösung gibt, und wie man diese findet.

Definition

Es sei ein Körper und sei eine Matrix über Dann heißt invertierbar wenn es eine weitere Matrix

mit

gibt.

Definition

Es sei ein Körper. Zu einer invertierbaren Matrix

heißt die Matrix

mit

die inverse Matrix von Man schreibt dafür

Beispiel

Eine Diagonalmatrix

ist genau dann invertierbar, wenn sämtliche Diagonaleinträge von verschieden sind. Die inverse Matrix dazu ist

Das Produkt von invertierbaren Matrizen ist wieder invertierbar, die invertierbaren Matrizen bilden eine Gruppe. Aus der einzigen Gleichung

folgt sogar die umgekehrte Gleichung

also die Invertierbarkeit von Dies ist aber rein matrizentheoretisch schwierig zu beweisen, für den Fall von Matrizen siehe Aufgabe 36.9. Mit Hilfe der Korrespondenz zwischen Matrizen und linearen Abbildungen kann man es beweisen, indem man verwendet, dass für eine lineare Abbildung

die Begriffe injektiv, surjektiv und bijektiv äquivalent sind (das haben wir nicht bewiesen). Invertierbare Matrizen und bijektive lineare Abbildungen hängen unmittelbar zusammen.

Satz

Es sei ein Körper und sei

eine lineare Abbildung mit zugehöriger Matrix

Dann ist genau dann bijektiv, wenn invertierbar ist.

Beweis

Wenn bijektiv ist, so gibt es eine lineare Abbildung

mit

Es sei die Matrix zu und die Matrix zu Nach Satz 35.15 ist dann

und dies bedeutet die Invertierbarkeit von Die Rückrichtung geht genauso.

$\Box$

Wir möchten zu einer Matrix bestimmen, ob sie invertierbar ist oder nicht und wie gegebenenfalls die inverse Matrix aussieht. Dazu sind Elementarmatrizen hilfreich, da man mit ihnen die Manipulationen, die im Eliminationsverfahren auftreten, als Matrizenmultiplikationen beschreiben kann.

Definition

Es sei ein Körper und sei eine Matrix über Dann nennt man die folgenden Manipulationen an elementare Zeilenumformungen

1. Vertauschung von zwei Zeilen.
2. Multiplikation einer Zeile mit
3. Addition des fachen einer Zeile zu einer anderen Zeile.

Elementare Zeilenumformungen ändern nicht den Lösungsraum von homogenen linearen Gleichungssystemen, wie in Lemma 32.3 gezeigt wurde.

Definition

Es sei ein Körper. Mit bezeichnen wir diejenige Matrix, die an der Stelle den Wert und sonst überall den Wert hat. Dann nennt man die folgenden Matrizen Elementarmatrizen

Ausgeschrieben sehen diese Elementarmatrizen folgendermaßen aus.

Elementarmatrizen sind invertierbar, siehe Aufgabe 36.1, und ihre Inversen sind ebenfalls Elementarmatrizen.

Lemma

Es sei ein Körper und eine Matrix mit Einträgen in Dann hat die Multiplikation mit den Elementarmatrizen von links mit folgende Wirkung.

1. Vertauschen der ten und der ten Zeile von
2. Multiplikation der ten Zeile von mit
3. Addition des fachen der ten Zeile von zur ten Zeile ($i\neq j$).

Beweis

Siehe Aufgabe 36.11.

$\Box$

Satz

Es sei ein Körper und sei eine Matrix über

Dann gibt es elementare Zeilenumformungen und eine (Neu-)Nummerierung der Spalten

und ein

derart, dass in der entstandenen Matrix die Spalten die Gestalt

und

besitzen. Durch elementare Zeilenumformungen und zusätzliche Spaltenvertauschungen kann man also eine Matrix auf die Gestalt

mit

bringen.

Beweis

Dies beruht auf den entsprechenden Manipulationen für Gleichungen wie beim Eliminationsverfahren, siehe die zweite Vorlesung.

$\Box$

Beispiel

Wir betrachten die Matrix Wir wollen diese Matrix durch elementare Zeilenumformungen auf Diagonalgestalt bringen und diese Manipulatonen durch Multiplikationen mit Elementarmatrizen realisieren. Die erste Umformung ist, die zweite Zeile durch zu ersetzen. Die geschieht durch

Die dritte Zeile soll durch ersetzt werden, dies wird realisiert durch

Die neue dritte Zeile kann man zu einer Nullzeile machen, indem man sie durch ersetzt. Dies wird realisiert durch

Beispiel

Wir betrachten die Matrix Wir wollen diese Matrix durch elementare Zeilenumformungen auf Diagonalgestalt bringen und diese Manipulationen durch Multiplikationen mit Elementarmatrizen realisieren. Die einzige Umformung ist, die zweite Zeile durch zu ersetzen. Dies wird durch

realisiert.

Beispiel

Die Matrix ist nicht in der in Satz 36.8 zuletzt beschriebenen Form, und kann auch nicht durch Zeilenumformungen dahin gebracht werden. Durch Spaltenvertauschungen ist das möglich.

Korollar

Es sei ein Körper und sei eine invertierbare Matrix über

Dann gibt es elementare Zeilenumformungen derart, dass nach diesen Umformungen eine Matrix der Gestalt

mit

entsteht. Durch weitere elementare Zeilenumformungen kann die Einheitsmatrix erreicht werden.

Beweis

Dies beruht auf den Manipulationen des Eliminationsverfahrens und darauf, dass elementare Zeilenumformungen nach Lemma 36.7 durch Multiplikationen mit Elementarmatrizen von links ausgedrückt werden können. Dabei können in einer Spalte bzw. in einer Zeile nicht nur Nullen entstehen, da die Elementarmatrizen invertierbar sind und so in jedem Schritt die Invertierbarkeit erhalten bleibt. Eine Matrix mit einer Nullspalte oder einer Nullzeile ist aber nicht invertierbar. Wenn eine invertierbare obere Dreiecksmatrix vorliegt, so sind nach Aufgabe ***** die Diagonaleinträge nicht und man kann mit skalarer Multiplikation die Diagonaleinträge zu machen und damit die in jeder Spalte darüberliegenden Einträge zu

$\Box$

Insbesondere gibt es zu einer invertierbaren Matrix Elementarmatrizen derart, dass

die Einheitsmatrix ist.

Verfahren  

Es sei eine quadratische Matrix. Wie kann man entscheiden, ob die Matrix invertierbar ist, und wie kann man die inverse Matrix

finden?

Dazu legt man eine Tabelle an, wo in der linken Seite zunächst die Matrix steht und in der rechten Seite die Einheitsmatrix. Jetzt wendet man auf beide Matrizen schrittweise die gleichen elementaren Zeilenumformungen an. Dabei soll in der linken Seite die Ausgangsmatrix in die Einheitsmatrix umgewandelt werden. Dies ist genau dann möglich, wenn diese Matrix invertierbar ist. Wir behaupten, dass bei dieser Vorgehensweise in der rechten Seite die Matrix als Endmatrix entsteht. Dies beruht auf folgendem Jede elementare Zeilenumformung kann nach Lemma 36.7 als eine Matrizenmultiplikation mit einer Elementarmatrix

von links realisiert werden. Wenn in der Tabelle

steht, so steht im nächsten Schritt

Wenn man das Inverse (das man noch nicht kennt, das es aber unter der Voraussetzung, dass die Matrix invertierbar ist, gibt.) der linken Seite mit der rechten Seite multipliziert, so ergibt sich

D.h., dass sich dieser Ausdruck bei den Einzelschritten nicht ändert. Zu Beginn ist dieser Ausdruck gleich daher muss zum Schluss für gelten

Beispiel

Wir wollen zur Matrix gemäß dem in Verfahren 36.13 beschriebenen Verfahren die inverse Matrix

bestimmen.

Für eine invertierbare Matrix kann man die inverse Matrix einfacher direkt angeben, es ist nämlich

(und die ist genau dann ungleich wenn die Matrix invertierbar ist).

Beispiel

Wir wollen zur Matrix gemäß dem in Verfahren 36.13 beschriebenen Verfahren die inverse Matrix

bestimmen.

Sei eine Menge von Personen und eine Menge von Eigenschaften, die eine Person haben kann oder auch nicht, und zwar sollen hier nur solche Eigenschaften betrachtet werden, wo es nur die beiden Möglichkeiten des Zukommens oder des Nichtzukommens gibt. Die Gesamtinformation, welche der beteiligten Personen welche Eigenschaft besitzt, kann man dann auf verschiedene Arten ausdrücken. Man kann beispielsweise eine Liste von allen zutreffenden Person-Eigenschafts-Paaren erstellen, also

(Anna, klug), (Hans, schön), (Berta, schön), (Hans, lustig), (Anna, lustig)

oder man kann zu jeder Person die ihr zukommenden Eigenschaften auflisten, also

Anna: klug, lustig

Berta: schön

Hans: schön, lustig

oder umgekehrt zu einer Eigenschaft die Personen auflisten, die diese Eigenschaft erfüllen, also

Schön: Berta, Hans

Klug: Anna

Lustig: Anna, Hans

Man kann auch das ganze in eine Tabelle schreiben, wo die eine Leiste die Personen und die andere Leiste die Eigenschaften repräsentiert, und dann diejenigen Kreuzungspunkte, die eine zutreffende Beziehung repräsentieren, ankreuzen, also

	Anna	Berta	Hans
Schön		x	x
Klug	x
Lustig	x		x

Eine weitere Möglichkeit besteht darin, die Information durch ein Verbindungsdiagramm auszudrücken, bei dem Person und Eigenschaft genau dann durch eine Strecke oder eine Kurve verbunden werden, wenn die Eigenschaft zutrifft.

Der mathematische Begriff, um Beziehungen zwischen den Elementen von zwei Mengen zu beschreiben, heißt Relation.

Definition

Es seien Mengen. Eine Relation zwischen den Mengen

ist eine Teilmenge der Produktmenge

also  

Statt

schreibt man häufig auch oder und sagt, dass Typische mathematische Relationen sind: ist gleich, ist größer als, ist Element von, ist Teilmenge von, ist disjunkt zu, usw.

Wenn

eine Relation ist, so heißt für jedes

die Menge

die durch und für jedes

heißt die Menge

die Faser durch

Beispiel

Wir betrachten auf einer Auswahl von Speisen und Getränken die Relation, die angibt, ob ein Gericht zu einem Getränk passt. Sei

und

Wasser passt zu allen Gerichten, Kamillentee zu keinem der Gerichte. Rotwein passt zu Nudeln und Kartoffelgratin, aber nicht zu Hecht oder zu Zupfkuchen. Heiße Schokolade und Kaffee passt zu Zupfkuchen, nicht zu den anderen Gerichten.

Beispiel

Es sei die Menge der Städte und die Menge der Autobahnen. Dann ist die Beziehung eine Relation zwischen

Zwischen einer Stadt

und einer Autobahn

bedeutet

einfach, dass die konkrete Stadt an der Autobahn liegt. Zu ist dann die Menge

die Menge der Autobahnen, an denen liegt, und zu

ist

die Teilmenge der Städte, an denen die Autobahn vorbeifährt. Für ergibt sich also

und für die ergibt sich

Diese Relation wird vollständig beschrieben, wenn man zu jeder Stadt die daran vorbeiführenden Autobahnen oder aber wenn man zu jeder Autobahn die daran liegenden Städte aufführt. Genauso gut kann man die Relation durch eine Tabelle ausdrücken mit einer Leitzeile für die Autobahnen und einer Leitspalte für die Städte, und wo im Kreuzungspunkt ein Kreuz gemacht wird genau dann, wenn gilt. Die Aussage

bedeutet, dass jede Stadt an einer Autobahn liegt (wohl falsch) und die Aussage

bedeutet, dass jede Autobahn an mindestens einer Stadt vorbeiführt (wohl wahr).

Beispiel

Es sei

die reelle Ebene und die Menge aller Geraden in der Ebene. Die Produktmenge

besteht aus allen Paaren wobei ein Punkt der Ebene und eine Gerade ist. Es gibt mehrere Möglichkeiten, eine Gerade zu beschreiben, und damit auch mehrere Möglichkeiten, ein solches Paar zu beschreiben. Beispielsweise ist

ein Paar, wobei der Punkt vorne durch die beiden Koordinaten und die Gerade hinten durch eine Geradengleichung angegeben wird. Bei einem solchen Paar besteht keine Bedingung zwischen dem Punkt und der Geraden.

Die zwischen Punkten und Geraden wird ausgedrückt durch

Statt kann man auch einfach

schreiben.

Beispiel

Es sei eine Menge und die Potenzmenge von Dann wird auf die erklärt durch

Die Inzidenzrelation drückt also aus, ob ein Element zu einer bestimmten Teilmenge gehört oder nicht. Die Faser zu einem Element besteht aus sämtlichen Teilmengen, die dieses Element enthalten, und die Faser zu einer Teilmenge besteht aus allen Elementen dieser Teilmenge.

Abbildungen kann man als spezielle Relationen auffassen.

Definition

Es seien

Mengen und es sei

eine Abbildung. Dann nennt man

den Graphen der Abbildung

Abbildungen und ihre Graphen sind im wesentlichen äquivalente Objekte. Um Abbildungen innerhalb der Relationen herauszustellen, sind die folgenden Begriffsbildungen sinnvoll (die Begriffe sind sinnvoll, ob die gewählten Bezeichnungen sinnvoll sind, ist eine andere Frage).

Definition

Eine Relation

heißt linkseindeutig wenn es zu jedem

maximal ein

mit

gibt.

Definition

Eine Relation

heißt rechtseindeutig wenn es zu jedem

maximal ein

mit

gibt.

Definition

Eine Relation

heißt linksvollständig wenn es zu jedem

ein

mit

gibt.

Definition

Eine Relation

heißt rechtsvollständig wenn es zu jedem

ein

mit

gibt.

Wenn ein Paar

gegeben ist, so meint rechtseindeutig, dass (bei gegebenem)

die rechte Seite, also das  eindeutig bestimmt ist. Wenn man sich aber die Relation auf  dadurch gegeben denkt, dass zwischen den Elementen der linken Menge  und den Elementen der rechten Menge  genau dann eine verbindende Strecke

(kein Pfeil) vorliegt, wenn das entsprechende Paar zu gehört, so hat rechtseindeutig die Auswirkung, dass von jedem Punkt der linken Seite (!) aus maximal eine Verbindungsstrecke abgeht.

Lemma

Eine Relation

ist genau dann eine (der Graph einer) Abbildung, wenn sie linksvollständig und rechtseindeutig ist.

Beweis

Eine Abbildung

ordnet jedem

genau ein

zu, das ist nach Definition die Linksvollständigkeit und die Rechtseindeutigkeit.

$\Box$

Eine rechtseindeutige Relation, die nicht unbedingt linksvollständig ist, nennt man auch manchmal eine eine (insbesondere linksvollständige) Relation nennt man manchmal auch eine

Bemerkung  

Eine Abbildung

ist genau dann surjektiv, wenn der Graph der Abbildung (als Relation aufgefasst) rechtsvollständig ist, und genau dann injektiv, wenn der Graph linkseindeutig ist.

Im eingangs erwähnten Beispiel gab es einerseits Personen und andererseits Eigenschaften, die diese Personen haben konnten oder nicht. Die beiden beteiligten Mengen hatten also eine unterschiedliche Funktion. Wenn man aber z.B. zwischenmenschliche Beziehungen ausdrücken möchte, so stimmen die beiden Mengen häufig überein, und es ergeben sich neuartige strukturelle Möglichkeiten, da ein Element sowohl vorne als auch hinten stehen kann. Betrachten wir in der studentischen Dreier-WG die Relation „kann gut leiden“. Die zugehörige Relationstabelle sieht vielleicht so aus.

	Anna	Berta	Hans
Anna		x	x
Berta	x	x
Hans	x	x	x

Hier ist zunächst wichtig, die Bedeutung der Spalte und der Zeile festzulegen; sagen wir, dass die Tabelle so zu verstehen ist, dass in der Leitspalte das grammatische Subjekt und in der Leitzeile das grammatische Objekt steht. Damit besagt die Tabelle, dass Hans alle Personen der WG gut leiden kann, dass Berta sich und Anna gut leiden kann, aber nicht Hans, und dass Anna ihre beiden Mitbewohner gut leiden kann, aber nicht sich selbst. Die Relation ist also weder „reflexiv“, da sich Anna nicht gut leiden kann, noch „symmetrisch“, da Hans zwar Berta gut leiden kann, aber nicht umgekehrt.

Definition

Eine Relation auf einer Menge ist eine Teilmenge der Produktmenge also

Wenn ein Paar zu gehört, so sagt man auch, dass und in der Relation stehen. Statt

verwendet man häufig suggestivere Schreibweisen wie oder Dabei werden manche Symbole nur verwendet, wenn die Relation gewisse zusätzliche Eigenschaften erfüllt. Die wichtigsten Eigenschaften fasst die folgende Definition zusammen (die bei zwei verschiedenen Mengen keinen Sinn ergeben).

Definition

Es sei eine Menge und

eine Relation auf Man nennt

• reflexiv wenn

gilt für alle

• transitiv wenn für beliebige

aus

stets

folgt.

• symmetrisch wenn für beliebige

aus

auch

folgt.

• antisymmetrisch wenn für beliebige

aus

die Gleichheit

folgt.

Eine wichtige Darstellungsmöglichkeit für eine Relation auf einer Menge ist durch ein Pfeildiagramm gegeben, man spricht auch von einem Dabei werden die Elemente der Grundmenge als Punkte (Knoten) gezeichnet, und es wird genau dann ein Pfeil von Punkt zu Punkt gezeichnet, wenn gilt. Die Richtung des Pfeiles ist dabei wichtig. Wenn allerdings die Relation symmetrisch ist, so gibt es zu jedem Pfeil den entsprechenden Rückpfeil. Daher drückt man symmetrische Relationen direkt durch ungerichtete Pfeile (Kanten, Verbindungsstrecken) aus und spricht von

Beispiel

Eine (Fußball-)Spielgruppe bei einer Europa- oder Weltmeisterschaft besteht aus vier Mannschaften, und jede spielt gegen jede. Ein Spiel kann unentschieden oder mit einem Sieg für eine der beiden Mannschaften enden. Wir interessieren uns für die Gewinnrelation in einer Spielgruppe, die man durch einen gerichteten Graphen beschreiben kann, wobei man einen Sieg von über durch einen Pfeil von nach (und ein Unentschieden durch keine Verbindung) ausdrücken kann.

Wir besprechen nun verschiedene mathematische Relationen, die mit diesen Eigenschaften definiert werden können.

Eine reflexive, transitive und antisymmetrische Relation nennt man eine Ordnung, wofür man häufig ein Symbol wie verwendet. Diese haben wir schon im Kontext von angeordneten Ringen besprochen.

Definition

Eine Relation

auf einer Menge  heißt Ordnungsrelation oder Ordnung wenn folgende drei Bedingungen erfüllt sind.

1. Es ist für alle
2. Aus und folgt stets
3. Aus und folgt

Eine Menge mit einer fixierten Ordnung darauf heißt Wenn zusätzlich gilt, dass für je zwei Elemente

gilt, so spricht man von einer

Beispiel

Die reellen Zahlen (ebenso die rationalen Zahlen und die ganzen Zahlen) sind total geordnet durch die Dies gehört zum Begriff des angeordneten Körpers, der nicht nur verlangt, dass eine totale Ordnung erklärt ist, sondern auch, dass diese mit den algebraischen Operationen verträglich ist. Die strikte ist keine Ordnungsrelation, da sie nicht reflexiv ist. Der Körper der komplexen Zahlen ist nicht angeordnet (und lässt sich auch nicht anordnen).

Beispiel

Wir betrachten die positiven ganzen Zahlen zusammen mit der Teilbarkeitsbeziehung. Man sagt, dass eine Zahl die Zahl teilt, geschrieben

wenn es eine weitere natürliche Zahl  mit

gibt. Die Bezeichnung ist nicht sonderlich glücklich gewählt, da ein symmetrisches Symbol für eine nichtsymmetrische Relation verwendet wird. Die Teilbarkeitsrelation ist in der Tat reflexiv, da stets ist, wie

zeigt. Die Transitivität sieht man so: sei

mit

Dann ist

und daher Die Antisymmetrie folgt so: Aus

folgt

Da wir uns auf positive natürliche Zahlen beschränken, folgt

und daraus

Also ist

Einfache Beispiele wie $2$ und $3$ zeigen, dass hier keine totale Ordnung vorliegt, da weder von noch umgekehrt geteilt wird.

Beispiel

Es sei eine beliebige Menge und

die Potenzmenge davon. Dann sind die Elemente aus

- also die Teilmengen von - durch die Inklusionsbeziehung geordnet. Die Reflexivität bedeutet einfach, dass eine jede Menge in sich selbst enthalten ist und die Transitivität bedeutet, dass aus

und

die Inklusion

folgt. Die Antisymmetrie ist dabei ein wichtiges Beweisprinzip für die Gleichheit von Mengen: Zwei Mengen sind genau dann gleich, wenn

gilt.

Beispiel

Es sei eine Menge (beispielsweise ein reelles Intervall, oder ein topologischer Raum), so ist die Menge der (stetigen) Funktionen

geordnet, indem man

dadurch definiert, dass

für jeden Punkt

sein muss. Dies ist offensichtlich keine totale Ordnung.

In der Mathematik sind Formulierungen, dass mathematische Objekte 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 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.

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 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 äquivalent zu 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

oder

gleichwertige Terme. Ebenso sind die Bruchterme

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

Mengen und sei

eine Abbildung.

Dann wird durch die Festlegung

wenn

eine Äquivalenzrelation auf definiert.

Beweis

Siehe Aufgabe 38.9.

$\Box$

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

ü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 38.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 23.11 sind aber

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 falls die Zahl positiv ist). 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) 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.

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 38.10 erfassen.

Beispiel

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 (in der reellen Ebene). Zwei Dreiecke

heißen wenn es eine (eventuell uneigentliche)

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

(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 bei der nur eigentliche Bewegungen (also keine Achsenspiegelungen) erlaubt sind, eine Äquivalenzrelation.

Eine Äquivalenzrelation

auf einer Menge kann auch als Zerlegung der Menge aufgefasst werden. Hierzu ist der Begriff der nützlich.

Definition

Es sei

eine Äquivalenzrelation und

Dann ist

die Äquivalenzklasse von bezüglich

In Worten: ist die Teilmenge aller Elemente von die zu äquivalent sind, also einfach die Faser zu Jede Teilmenge

die die Gestalt

für ein

besitzt, heißt Äquivalenzklasse. Jedes Element

heißt ein für die Äquivalenzklasse Insbesondere ist selbst ein Repräsentant für die Klasse doch ist dies keineswegs der einzige oder der Repräsentant.

Definition

Es sei eine Äquivalenzrelation auf einer Menge Eine Teilmenge

heißt ein Repräsentantensystem für die Äquivalenzrelation, wenn es für jede Äquivalenzklasse genau ein Element in aus dieser Klasse gibt.

Beispiel

Wir knüpfen an Beispiel 38.5 an. Die gesamte Wäsche haben wir gemäß der Waschverträglichkeit sortiert und es haben sich dabei verschiedene Haufen ergeben, wobei zwei Kleidungsstücke genau dann auf dem gleichen Haufen gelandet sind, wenn sie zueinander waschverträglich sind. Die Haufen sind also die Äquivalenzklassen. Die Äquivalenzklasse zu einem bestimmten Kleidungsstück besteht aus allen zu waschverträglichen Kleidungsstücken, also aus allen Kleidungsstücken, die zusammen mit auf dem gleichen Haufen liegen. Wenn wir aus jedem Haufen ein bestimmtes Kleidungsstück auswählen, so haben wir ein Repräsentantensystem für die Waschverträglichkeit.

Bemerkung  

Wir betrachten in einigen Beispielen von Äquivalenzrelationen die Äquivalenzklassen. Wenn die Äquivalenzrelation die Gleichheit ist, so sind alle Äquivalenzklassen einelementig und die Äquivalenzklasse zu ist einfach die einelementige Menge

Im anderen Extremfall, wenn alle Elemente zueinander äquivalent sind, so gibt es nur eine einzige Äquivalenzklasse, nämlich die Gesamtmenge

Bei der Äquivalenzrelation auf der Menge der Bruchterme, die durch die Wertegleichheit in gegeben ist, besteht die Äquivalenzklasse zu aus allen anderen Bruchdarstellungen dieser Zahl, also beispielsweise aus Ein Repräsentantensystem liegt in der Menge aller gekürzten Brüche vor.

Wenn eine Äquivalenzrelation auf durch eine Abbildung

im Sinne von Lemma 38.10 festgelegt ist, so sind die Äquivalenzklassen die nichtleeren Fasern der Abbildung. Die Äquivalenzklasse zu

besteht aus dem Urbild von ist also gleich

Um ein Repräsentantensystem zu erhalten, muss man aus jeder Faser ein Element auswählen. Im Allgemeinen gibt es hier kein besonders einfaches Repräsentantensystem.

In Beispiel 38.11 besteht die Äquivalenzklasse zu

aus (wobei diese beiden Zahlen nicht unbedingt, wie etwa bei

verschieden sein müssen). Wenn angeordnet ist, so kann man die nichtnegativen Elemente als ein übersichtliches Repräsentantensystem heranziehen.

In Beispiel 38.12 bei der durch die Gaußklammer gegebenen Äquivalenzrelation besteht die Äquivalenzklasse zu aus dem halboffenen Intervall

Ein besonders einfaches Repräsentantensystem ist durch die Menge der ganzen Zahlen gegeben.

Bei der durch das Betrachten des Bruchanteils (der Nachkommazahl) gegebenen Äquivalenzrelation auf besteht die Äquivalenzklasse zu aus der Menge also aus allen Zahlen, die man von aus mit einem ganzzahligen Schritt erreichen kann. Die Menge der Zahlen zwischen

einschließlich der und ausschließlich der , also der Zahlen aus dem halboffenen Intervall

ist ein Repräsentantensystem.

In Beispiel 38.13, der Erreichbarkeitsrelation auf dem Landweg, besteht die Äquivalenzklasse zu aus der Insel bzw. dem Kontinent, auf der bzw. dem der Punkt liegt.

Beispiel

Es sei

fixiert. Wir bestimmen auf die Äquivalenzklassen zur Äquivalenzrelation

bei der zwei Zahlen

als äquivalent betrachtet werden, wenn ihre Differenz ein Vielfaches von ist. Zu jeder Zahl

kann man einfach die zugehörige Äquivalenzklasse finden, sie besteht aus allen Zahlen der Form

In jeder Äquivalenzklasse gibt es ein Element (einen Vertreter, einen Repräsentanten) zwischen

da ja insbesondere zu seinem Rest bei der Division durch äquivalent ist. Andererseits sind bei

die Äquivalenzklassen zu und zu verschieden. Es ist nämlich

da aus

sofort

folgt, was wegen

nicht sein kann.

Beispiel

In der Ebene sei ein bestimmter Punkt markiert. Wir betrachten die Äquivalenzrelation, bei der zwei Punkte

als äquivalent gelten, wenn sie zu den gleichen Abstand besitzen. Dies wird durch

ausgedrückt. Dies ist eine Äquivalenzrelation, wie man direkt überprüfen kann und was auch aus Lemma 38.10 folgt, da man ja die Situation mittels der Abbildung

interpretieren kann. Die Äquivalenzklasse zu einem Punkt besteht aus allen Punkten der Ebene, die in ihrem Abstand zu mit übereinstimmen. Dies ist genau der Kreis mit Mittelpunkt durch den Punkt Die Äquivalenzklassen sind also die konzentrischen Kreise um den Mittelpunkt wobei man hier den Punkt als Kreis mit Radius mitzählen muss (man kann sich darüber streiten, ob das ein Kreis ist, jedenfalls ist diese einpunktige Menge hier eine Äquivalenzklasse).

Beispiel

Auf der Menge aller Geraden in der Ebene kann man die Parallelität als Äquivalenzrelation auffassen. Eine Gerade ist zu sich selbst parallel, die Relation ist offenbar symmetrisch und wenn

parallel und

parallel ist, so ist auch

parallel. Die Äquivalenzklasse zu einer Geraden besteht aus allen zu parallelen Geraden, diese bilden eine parallele Geradenschar. Wir fixieren einen Punkt in der Ebene. Dann gibt es zu jeder Geraden eine dazu parallele Gerade die durch den Punkt verläuft. Man kann also jede Äquivalenzklasse durch eine Gerade durch den Punkt repräsentieren, und zwar eindeutig, da parallele Geraden, die durch einen Punkt verlaufen, übereinstimmen müssen. Die Menge der Geraden durch bildet also ein Repräsentantensystem für die Äquivalenzrelation der Parallelität.

Beispiel

Beim Schach darf ein Läufer diagonal in jede Richtung beliebig weit ziehen. Zwei Felder heißen läuferäquivalent, wenn man von dem einen Feld mit endlich vielen Läuferzügen zu dem anderen Feld gelangen kann. Das ist eine Äquivalenzrelation. Da sich bei einem Diagonalzug die Farbe des Feldes nicht ändert, bleibt ein Läufer, der auf einem weißen Feld steht, stets auf einem weißen Feld. Zugleich kann ein Läufer, der auf einem weißen Feld steht, jedes weiße Feld (grundsätzlich, ohne Beachtung von anderen Figuren in einer Stellung) erreichen. Deshalb gibt es zwei Äquivalenzklassen: die weißen Felder und die schwarzen Felder, und entsprechend spricht man von weißfeldrigen Läufern und schwarzfeldrigen Läufern (das ist nicht die Farbe der Figur).

Beispiel

Wir knüpfen an Beispiel 38.5 und Beispiel 39.3 an. Die Wäsche liegt in verschiedenen waschgangverträglichen Haufen vor. Für den weiteren Ablauf (beispielsweise in welcher Reihenfolge gewaschen wird) kommt es auf die Einzelsachen nicht mehr an, sondern nur noch auf die einzelnen Haufen. Es ist daher sinnvoll, die entstandene Situation dadurch zu erfassen, dass man die Menge der Haufen bildet. Jeder Haufen wird zu genau einem Element in dieser Haufenmenge. Das Sortieren kann man dann auffassen als eine Abbildung von der Wäschemenge in die Haufenmenge, wobei jedem Wäschestück der zugehörige Haufen zugeordnet wird. Bei diesem Übergang werden waschgangverträgliche Sachen miteinander identifiziert. Dies ist die Grundidee der Quotientenmenge und der kanonischen Abbildung.

Definition

Es sei

eine Äquivalenzrelation. Dann heißt

die Quotientenmenge von

Die Quotientenmenge ist also einfach die Menge der Äquivalenzklassen. Wenn man die Äquivalenzrelation mit bezeichnet, so schreibt man für die Quotientenmenge. Das Konzept Quotientenmenge ist nicht einfach, allein schon deshalb, da es nach Definition eine Menge von Mengen, nämlich der Äquivalenzklassen ist. Von der Handhabung und der Vorstellung her betrachtet man aber diese Äquivalenzklassen eher als neue in einer neuen Menge, die eben erst durch die Konstruktion entsteht. Auch die Beziehung zu einem Repräsentantensystem ist nicht ganz einfach. Wenn man ein Repräsentantensystem

für eine Äquivalenzrelation hat, so ergibt sich eine bijektive Abbildung

zwischen dem Repräsentantensystem und der Quotientenmenge. Diese kann zu Verwechslungen führen. Wichtig ist, dass ein Repräsentantensystem von einer Wahl abhängt und nur selten kanonisch ist, während die Quotientenmenge nicht von Wahlen abhängt. Wenn es allerdings ein besonders einfaches Repräsentantensystem gibt, so übernimmt man die Bezeichnungen für die Elemente wiederum auch als Bezeichnungen für die Elemente der Quotientenmenge.

Man muss aber auch sagen, dass die Abstraktion, die in der Quotientenmenge zum Ausdruck kommt, in vielen Kontexten anzutreffen ist. Beispielsweise gibt es die Menge der Tiere und die Menge der Tierarten. Hinter Tierart steckt doch eine andere Idee als die Menge der zu unter diese Tierart fallenden Einzeltiere oder die Idee, aus jeder Tierart einen Vertreter auszuwählen. Die Menge aller geraden und die Menge aller ungeraden Zahlen wird durch das Eigenschaftspaar gerade oder ungerade deutlicher gemacht. Entsprechend führt die Parallelität zur Idee der einer Geraden, u.s.w.

Im oben angeführten Beispiel 39.5 besteht die Quotientenmenge aus den Restklassen wobei die Bezeichnungen des einfachsten Repräsentantensystems übernommen werden. Die konzentrischen Kreise um den Punkt aus Beispiel 39.6 kann man mit ihrem Radius identifizieren, d.h. die Quotientenmenge steht in einer natürlichen Korrespondenz zu Auch dies ist eine wichtige Beobachtung, dass die Quotientenmenge häufig eine neue Struktur besitzt oder in einer natürlichen Beziehung zu einem anderen mathematischen Gebilde steht, was von der Ausgangsmenge her nicht unmittelbar ersichtlich ist. So kann man auch die Menge der Geraden durch einen Punkt die ein Repräsentantensystem für die Parallelität ist, in einem weiteren Schritt mit den Punkten auf einem halboffenen Halbkreis um identifizieren, um eine geometrische gehaltvolle Interpretation der Quotientenmenge zu erhalten. Die Quotientenmenge zur Äquivalenzrelation des Läufers besteht nur aus den Feldfarben weiß und schwarz.

Definition

Es sei

eine Äquivalenzrelation und die Quotientenmenge. Die Abbildung

heißt kanonische Projektion von

Man spricht auch von der da unter dieser Abbildung äquivalente Elemente auf das gleiche Element, ihre Klasse, abgebildet werden.

Lemma

Es sei eine Menge und eine Äquivalenzrelation auf mit den Äquivalenzklassen

und der

Quotientenmenge

Dann gelten folgende Aussagen.  

1. Es ist genau dann, wenn ist, und dies gilt genau dann, wenn
2. ist eine disjunkte Vereinigung.
3. Die kanonische Projektion ist surjektiv.
4. Es ist

Beweis

1. Seien äquivalent und Dann ist und nach der Transitivität auch also Damit stimmen die Äquivalenzklassen überein. Die Implikation von der Mitte nach rechts ist klar, da wegen Äquivalenzklassen nicht leer sind. Es sei nun und sei ein Element im Durchschnitt. Dann ist und wegen der Transitivität ist
2. Wegen der Reflexivität ist und daher ist Wegen Teil (1) ist die Vereinigung disjunkt.
3. Die Surjektivität ist klar aufgrund der Definition der Quotientenmenge, und da auf die Klasse geschickt wird.
4. Es ist

$\Box$

Bei der Eigenschaft (2) sagt man auch, dass die Äquivalenzrelation eine der Menge bewirkt. Die Eigenschaft (4) bedeutet insbesondere, dass man zu jeder Äquivalenzrelation eine Abbildung, nämlich die kanonische Abbildung in die Quotientenmenge, angeben kann, derart, dass Elemente genau dann äquivalent sind, wenn sie unter der Abbildung den gleichen Wert besitzen. Damit ist gezeigt, dass man jede Äquivalenzrelation als eine Äquivalenzrelation zu einer Abbildung im Sinne von Lemma 38.10 erhalten kann.

Die folgende Aussage beschreibt die der Quotientenmenge.

Lemma

Es sei eine Menge und eine Äquivalenzrelation auf mit der Quotientenmenge

Es sei

eine Abbildung mit

für alle

Dann gibt es eine eindeutig bestimmte Abbildung

mit

Beweis

Sei

gegeben. Die einzige Möglichkeit für ist

zu setzen. Es muss aber gezeigt werden, dass diese Abbildung überhaupt wohldefiniert ist, also unabhängig von der Wahl des Repräsentanten ist. Es sei hierzu

also

Dann ist nach der Voraussetzung an aber

$\Box$

Bemerkung  

Zu einer Abbildung

und der zugehörigen Äquivalenzrelation

im Sinne von

Lemma 38.10 gibt es nach Satz 39.13 eine eindeutig bestimmte Abbildung

mit

Diese ist sogar injektiv.

Beispiel

Es sei

und ein Körper. Wir setzen

Der ist ein Vektorraum, wobei die Skalarmultiplikation von

und

mit bezeichnet wird. Es sei weiter

Zwei Punkte werden also als äquivalent erklärt, wenn sie durch Skalarmultiplikation mit einem Skalar

ineinander überführt werden können. Ebenso könnte man sagen, dass zwei Punkte als äquivalent gelten, wenn sie dieselbe Gerade durch den Nullpunkt definieren.

Dass wirklich eine Äquivalenzrelation vorliegt, sieht man so. Die Reflexivität folgt aus

für jedes

Zum Nachweis der Symmetrie sei d.h. es gibt ein

mit

Dann gilt aber auch

da ja ein Inverses besitzt. Zum Nachweis der Transitivität sei

angenommen, d.h. es gibt

mit

Dann ist insgesamt

mit

Die Äquivalenzklassen zu dieser Äquivalenzrelation sind die einzelnen Geraden durch den Nullpunkt (aber ohne den Nullpunkt). Die Quotientenmenge heißt über (der Dimension) und wird mit bezeichnet.

Wir besprechen nun mit Hilfe von Äquivalenzrelationen, Äquivalenzklassen und Quotientenmengen erneut, wie man aus den natürlichen Zahlen die ganzen Zahlen und wie man aus den ganzen Zahlen die rationalen Zahlen konstruieren kann. Dieser Zugang ist zwar abstrakter, aber konzeptionell klarer, allgemeiner und systematischer. In einigen Wochen werden wir die reellen Zahlen aus den rationalen Zahlen ebenfalls mittels Äquivalenzrelationen definieren.

Die ganzen Zahlen haben wir in der 18. Vorlesung einfach als die disjunkte Vereinigung von natürlichen und negativen Zahlen eingeführt und dann nach und nach die Verknüpfungen und die Ordnungsrelation festgelegt und die wichtigsten Eigenschaften bewiesen. Dabei hatten wir es häufig, beispielsweise beim Nachweis der Assoziativität für die Multiplikation, mit einer Vielzahl von Fallunterscheidungen zu tun, die wir im Einzelnen gar nicht alle ausgeführt haben.

Es sei die Menge der natürlichen Zahlen und

die Produktmenge mit der komponentenweisen Addition. Wir erklären auf eine Relation durch

Es wird hier also über Kreuz addiert, um diese Relation zu erhalten. Diese Relation ist bei

genau dann erfüllt, wenn es ein (nämlich die natürliche Zahl) mit

gibt und bei

genau dann erfüllt, wenn es ein

(nämlich) mit

gibt. So oder so kann man sagen, dass die Paare

zueinander äquivalent sind, wenn sie sich um ein Diagonalelement, also um ein Paar, wo beide Komponenten übereinstimmen, unterscheiden. Diese Relation ist eine Äquivalenzrelation auf Das ist von der soeben etablierten Interpretation als her klar, kann aber auch direkt gezeigt werden:

1. Wegen ist die Relation ist also reflexiv.
2. Die Symmetrie folgt daraus, dass aus sofort folgt.
3. Zum Nachweis der Transitivität sei also und Dann ist Aufgrund der Abziehregel ist dann und dies bedeutet

Passende Interpretationen für die Paare mit dieser Äquivalenzrelation sind beispielsweise:

• Das Paar repräsentiert das Ergebnis eines Fußballspieles, wobei die Toranzahl der Heimmannschaft und die Toranzahl der Gastmannschaft repräsentiert. Zwei Spiele gelten dann als äquivalent, wenn die gleich ist. Ein wird als äquivalent zu einem betrachtet, wenn beide Mannschaften ein weiteres Tor schießen, ändert sich zwar das Paar, aber nicht die Äquivalenzklasse. Die Äquivalenzklassen kann man charakterisieren als Unentschieden, mit einem Tor Vorsprung gewonnen, mit zwei Toren Vorsprung gewonnen, mit drei Toren Vorsprung gewonnen, ... , mit einem Tor Unterschied verloren, mit zwei Toren Unterschied verloren, mit drei Toren Unterschied verloren, ....

• Das Paar repräsentiert das Alter eines menschlichen Paares, wobei für das Alter der Frau und für das Alter des Mannes steht. Die Äquivalenzklasse ist durch den gerichteten Altersunterschied (also den Altersunterschied mit der zusätzlichen Information, wer älter ist)

festgelegt. Diese Beziehung ändert sich im Laufe des Lebens nicht, da beide gleichermaßen älter werden.

• Das Paar kann die Einnahmen und Ausgaben eines Haushaltes in einem Monat beschreiben, wobei die erste Stelle die Einnahmen und die zweite Stelle die Ausgaben repräsentieren möge. Zwei Haushalte

(oder Monate) sind dann äquivalent, wenn sie den gleichen Überschuss oder das gleiche Defizit erwirtschaftet haben. Wenn Einnahmen und Ausgaben gleichermaßen steigen oder fallen, ändert sich an dieser Gesamtbewertung nichts.

• Man kann das Paar als eine Schrittfolge aus Schritten nach rechts und Schritten nach links ansehen. Im Paar selbst wird die Anzahl der Schritte in die beiden Richtungen notiert, für die Äquivalenzrelation schaut man nur das Endergebnis des Bewegungsvorganges an.

Wenn man als ein quadratisches Gitter anordnet (das ist ein), so sind die Äquivalenzklassen durch die Punkte auf einer zur Diagonalen parallelen gegeben. Die Punkte mit

sind äquivalent zu sie haben also einen Repräsentanten, bei dem die zweite Komponente ist. Die Punkte mit

sind äquivalent zu sie haben also einen Repräsentanten, bei dem die erste Komponente ist. Die Punkte sind zu äquivalent. Den Repräsentanten einer Äquivalenzklasse, bei dem mindestens eine Komponente ist, nennen wir den dieser Äquivalenzklasse. Die Standardvertreter sind die diskreten Punkte des begrenzenden Viertelkreuzes; zu einem Punkt ergibt sich der Standardvertreter, indem man parallel zur Diagonalen in Richtung der Halbachsen wandert, bis man auf einer der Halbachsen landet. Zwei Punkte sind genau dann äquivalent, wenn sie den gleichen Standardvertreter besitzen.

Wir bezeichnen nun die Quotientenmenge, also die Menge der Äquivalenzklassen unter dieser Äquivalenzrelation, als und bezeichnen sie mit Wir sprechen vom oder für die ganzen Zahlen. Diese Quotientenmenge ist die Menge der zur Diagonalen parallelen diskreten Geraden, bei der kanonischen Projektion wird jedes Paar auf die Gerade abgebildet, auf der es liegt. Jede ganze Zahl hat genau einen Standardvertreter der Form

mit der Form

oder der Form

mit Eine natürliche Zahl fassen wir in diesem Modell als die ganze Zahl auf, und negative Zahlen werden als spezielle Äquivalenzklassen eingeführt.

Wir wollen nun zwei ganze Zahlen, also zwei solche Äquivalenzklassen

miteinander also eine Verknüpfung auf einführen. Ein Ansatz, der sich durch den Zugang über Äquivalenzklassen eröffnet, ist es, auf der Menge der Paare die Addition zu nehmen und zu versuchen, diese Addition auf die Äquivalenzklassen zu übertragen. Die komponentenweise Addition auf also die Verknüpfung

ist recht einfach und insbesondere ist diese Verknüpfung kommutativ, assoziativ und ist das neutrale Element. Diese Addition hat in den oben angegebenen Beispielen eine sinnvolle Interpretation, wie wenn man die Ergebnisse von zwei Fußballspielen miteinander addiert (Hin- und Rückspiel, allerdings muss man die Reihenfolge beibehalten) oder das Haushaltsgeschehen von mehreren Monaten addiert.

Lemma

Durch die Festlegung

erhält man auf (dem Äquivalenzklassenmodell von)

eine Verknüpfung, die kommutativ und assoziativ ist und die  als neutrales Element besitzt. Darüber hinaus besitzt jedes Element ein inverses Element, und zwar sind

invers zueinander.

Beweis

Wir müssen zuerst die Wohldefiniertheit überprüfen, da die Verknüpfung unter Bezug auf Repräsentanten erklärt wird und daher nicht von vornherein klar ist, dass unterschiedliche Repräsentanten zum gleichen Ergebnis (zur gleichen Äquivalenzklasse) führen. Zu

und

muss man überprüfen, dass

und damit

gilt. Die beiden Voraussetzungen bedeuten ausgeschrieben

und

Damit ist durch Addition der beiden Gleichungen

was die Äquivalenz bedeutet. Die kanonische Abbildung

verträgt sich nach Konstruktion mit der Addition auf der Produktmenge und der soeben etablierten Addition auf es ist also

für alle In einer solchen Situation übertragen sich wegen der Surjektivität der kanonischen Abbildung Rechengesetze von direkt auf die Quotientenmenge. Für das Assoziativgesetz beispielsweise betrachten wir Elemente Es gibt mit

Somit ist

Der Nachweis der Kommutativität und dass das neutrale Element der Verknüpfung ist, verläuft ähnlich einfach. Wegen

ist in der Tat das inverse Element zu

$\Box$

Lemma

Durch die Festlegung

erhält man auf (dem Äquivalenzklassenmodell von)

eine 

Verknüpfung, die kommutativ und assoziativ ist und die als neutrales Element besitzt.

Beweis

Siehe Aufgabe 40.5.

$\Box$

Satz

Das Äquivalenzklassenmodell von ist mit der Addition

der Multiplikation

dem Nullelement und dem Einselement

ein kommutativer Ring.

Beweis

Aufgrund von Lemma 40.1 und Lemma 40.2 müssen wir nur noch das Distributivgesetz überprüfen. Dieses ist wegen

erfüllt.

$\Box$

Lemma

Durch die Festlegung

falls

erhält man auf (dem Äquivalenzklassenmodell von)

eine

totale Ordnung.

Beweis

Siehe Aufgabe 40.6.

$\Box$

Satz

Das Äquivalenzklassenmodell von ist mit der Addition

der Multiplikation

dem Nullelement dem Einselement und der durch

falls

definierten Ordnung

ein angeordneter Ring.

Beweis

Nach Satz 40.3 ist ein kommutativer Ring und nach Lemma 40.4 ist eine totale Ordnung. Wir müssen also lediglich noch die Verträglichkeit der Ordnung mit der Addition und der Multiplikation überprüfen. Sei

also

und beliebig. Dann ist auch

also

Wenn

und

ist, so ist

und

Mit Aufgabe 10.31 ergibt sich

was

bedeutet.

$\Box$

Die natürlichen Zahlen sind über die Zuordnung

in den ganzen Zahlen enthalten. Diese Zuordnung ist mit der Addition, der Multiplikation und der Ordnung verträglich, siehe Aufgabe 40.7. Statt schreibt man einfach Die ganzen Zahlen, die durch mit repräsentiert werden, heißen negative Zahlen. Statt schreibt man einfach

In den Aufgaben wird gezeigt, dass das Paarmodell für mit dem im ersten Semester eingeführten Modell übereinstimmt.

Wir wollen ausgehend von der Menge der ganzen Zahlen die einen kommutativen Ring bildet, die Menge der konstruieren. Wir gehen dabei ähnlich wie bei der Konstruktion der ganzen Zahlen aus den natürlichen Zahlen vor, indem wir auf einer Menge eine Äquivalenzrelation einführen, sodass die Quotientenmenge ein Modell für die rationalen Zahlen ist. Die Konstruktion und die Beweise sind nicht wesentlich verschieden von den in der 23. Vorlesung durchgeführten, als wir die Sprache der Äquivalenzrelationen noch nicht zur Verfügung hatten.

Wir starten mit der Produktmenge

Zur Orientierung sei schon jetzt gesagt, dass das Paar später den Bruch repräsentieren soll.

Man kann sich vorstellen, dass in die erste Zahl eine Anzahl an Kuchen und die zweite Zahl eine Anzahl an Personen bedeutet, oder die Anzahl der Frauen und die Anzahl der Männer auf einer Party, oder irgendein Paar, das einen proportionalen Zusammenhang repräsentiert.

Auf wollen wir eine Äquivalenzrelation definieren, wobei zwei Paare als äquivalent gelten sollen, wenn sie repräsentieren (den es noch nicht gibt). Wir definieren

Diese Relation wird also unter Bezug auf die Gleichheit in erklärt. Es handelt sich dabei um eine Äquivalenzrelation, wie man direkt nachrechnen kann, siehe Aufgabe 40.6. Insbesondere sind und für

zueinander äquivalent.

Es ist hilfreich, sich diese Situation zu veranschaulichen, indem man die diskrete obere Halbebene

betrachtet. Ein Paar ist dann ein Gitterpunkt, wobei wir uns die ganzen Zahlen als die Punkte vorstellen. Die zugehörige durchgezogene (wo also die zweite Komponente konstant ist.) bezeichnen wir mit Ein jeder Punkt

definiert eine eindeutige Gerade, die durch diesen Punkt und durch den Nullpunkt verläuft. In dieser geometrischen Interpretation sind zwei Punkte

genau dann äquivalent, wenn sie die gleiche Gerade definieren, und dies ist genau dann der Fall, wenn ihre übereinstimmen. Zwei Punkte liegen ja genau dann auf der gleichen Geraden, wenn sie, wenn man durch Streckung ihre zweite Koordinate zur Übereinstimmung bringt, dann auch die erste Koordinate übereinstimmt. Wenn man den ersten Punkt mit streckt (multipliziert) und den zweiten Punkt mit so erhält man die beiden Punkte

und die Gleichheit vorne war die Definition für die Relation. Die Äquivalenzklassen sind die durch den Nullpunkt und einen weiteren Gitterpunkt.

Auch die Identifizierungsabbildung zu dieser Äquivalenzrelation kann man sich gut vorstellen. Der Schnittpunkt der durch einen Punkt und dem Nullpunkt definierten Geraden mit der Zahlengeraden ist ein Punkt, der dem Bruch entspricht (die Steigung der Geraden ist aber ${\frac {a}{b}}$).

Die Quotientenmenge unter dieser Äquivalenzrelation nennen wir und sprechen vom für Für die Elemente in schreiben wir vorläufig noch Wir wollen nun auf eine Addition und eine Multiplikation definieren.

Lemma

Durch die Festlegung

erhält man auf (dem Äquivalenzklassenmodell von)

eine Verknüpfung, die kommutativ und assoziativ ist und die  als neutrales Element besitzt. Darüber hinaus besitzt jedes Element ein inverses Element, und zwar sind

invers zueinander.

Beweis

Zum Nachweis der Wohldefiniertheit seien

und

also

und

Dann ist

und somit

Die Kommutativität und die Eigenschaft, dass das neutrale Element der Verknüpfung ist, folgen unmittelbar aus der Definition. Zum Beweis der Assoziativität seien gegeben. Es ist dann

Ferner ist

$\Box$

Lemma

Durch die Festlegung

erhält man auf (dem Äquivalenzklassenmodell von)

eine Verknüpfung, die kommutativ und assoziativ ist und die  als neutrales Element besitzt. Darüber hinaus besitzt jedes Element  ein inverses Element, und zwar sind bei

die Klassen

und bei

die Klassen

invers zueinander.

Beweis

Siehe Aufgabe 40.10.

$\Box$

Satz

Das Äquivalenzklassenmodell von ist mit der Addition

der Multiplikation

dem Nullelement und dem Einselement

ein Körper.

Beweis

Dies folgt aus Lemma 40.6 und aus Lemma 40.7, es ist somit lediglich noch das Distributivgesetz zu begründen. Dies ergibt sich aus

$\Box$

Lemma

Durch die Festlegung

falls

erhält man auf (dem Äquivalenzklassenmodell von)

eine 

totale Ordnung.

Beweis

Siehe Aufgabe 40.13.

$\Box$

Satz

Das Äquivalenzklassenmodell von ist mit der Addition

der Multiplikation

dem Nullelement dem Einselement und der durch

falls

definierten Ordnung

ein angeordneter Körper.

Beweis

Dies folgt aus Satz 40.8 und Lemma 40.9, es bleibt nur noch die Verträglichkeit der Ordnung mit den Verknüpfungen zu zeigen. Sei

also

und beliebig. Wegen

ist dann auch

und somit

Wenn

und

ist, so sind positiv und dann ist auch positiv, also

$\Box$

Die ganzen Zahlen sind über die Zuordnung

in den rationalen Zahlen enthalten. Diese Zuordnung ist mit der Addition, der Multiplikation und der Ordnung verträglich, siehe Aufgabe 40.14. Für die Äquivalenzklasse schreibt man abkürzend