Ganzzahl-Division: Kongruenzen und Restklassen als Beispiele für Äquivalenzrelationen und Äquivalenzklassen

Die Ganzzahl-Division (oder Division mit Rest) führt zu wichtigen Begriffsbildungen: Kongruenz, Restklassen und ihre Verallgemeinerungen Äquivalenzrelation und Äquivalenzklassen. Insbesondere kann mit einer Äquivalenzrelation eine Zerlegung der zugrundeliegenden Menge definiert werden.

walter
Äquivalenzrelation Äquivalenzklasse Restklasse Zerlegung Ganzzahl-Division Kongruenz Multiplikationstabelle modulo Additionstabelle
Inhaltsverzeichnis

Einordnung des Artikels

Einführung

Wird die Division n ÷ k mit ganzen Zahlen durchgeführt und das Ergebnis nicht als Dezimalzahl sondern mit Rest geschrieben, also

n ÷ k = q + r, wobei r = 0, 1, 2, ..., k - 1,

fällt sofort auf, dass ein gegebener Teiler k die Zahlen n in k Klassen einteilt: Zahlen n und m, die sich um ein Vielfaches von k unterscheiden, besitzen identischen Rest r.

Diese Klassen-Einteilung der Zahlen führt zu den wichtigen mathematischen Begriffen der Kongruenz und der Restklassen. Sie werden von den speziellen Eigenschaften der Division befreit und zu den Begriffen Äquivalenzrelation und Äquivalenzklassen verallgemeinert.

Als Anwendung werden im nächsten Kapitel Rechnen mit Restklassen: Teilbarkeitsregeln die bekannten Teilbarkeitsregeln hergeleitet: woran erkennt man, ob eine Zahl durch 2, 3, 4, 5, ... teilbar ist?

Additions- und Multiplikationstabellen

Eigentlicher Gegenstand dieses Kapitels ist die Division und wie sie eine Zerlegung der ganzen Zahlen herbeiführt. Da die Division die Umkehrung der Multiplikation ist, kann man viele Eigenschaften der Division aus den Eigenschaften der Multiplikation herleiten. Hilfreich werden dabei sogenannte Multiplikationstabellen sein, die jeder aus der Grundschule kennt. Was nicht so einleuchtend ist, auch die entsprechenden Additionstabellen werden hilfreich sein.

Abbildung 1 zeigt die vertraute Additions- und Multiplikationstabelle für Zahlen bis 10.

Abbildung 1: Additions- und Multiplikationstabelle im Zehnersystem für Zahlen bis 10.Abbildung 1: Additions- und Multiplikationstabelle im Zehnersystem für Zahlen bis 10.

Abbildung 2 und 3 zeigen die entsprechenden Tabellen für das Hexadezimalsystem – obwohl sie einfache Sachverhalte darstellen, wirken sie eher befremdlich.

Abbildung 2: Additionstabelle im Hexadezimalsystem für Zahlen von 1 bis 16.Abbildung 2: Additionstabelle im Hexadezimalsystem für Zahlen von 1 bis 16.

Abbildung 3: Multiplikationstabelle im Hexadezimalsystem für Zahlen von 1 bis 16.Abbildung 3: Multiplikationstabelle im Hexadezimalsystem für Zahlen von 1 bis 16.

Die Ganzzahl-Division

Die Division ist die Umkehrung der Multiplikation, ein einfaches Beispiel soll dies demonstrieren.

Die Gleichung 6 · 3 = 18 kann man auch umgekehrt lesen: Versucht man 18 Gegenstände auf drei Körbe aufzuteilen, müssen in jedem Korb 6 Gegenstände liegen, wenn jeder Korb gleich viele Gegenstände enthalten soll.

Sollen dagegen 20 Gegenstände auf drei Körbe aufgeteilt werden, müssen wieder 6 Gegenstände in jedem Korb liegen, aber jetzt bleiben zwei Gegenstände übrig.

Die Umkehrung zu 6 · 3 = 18 schreibt man daher als:

18 : 3 = 6

und die Umkehrung zu 6 · 3 = 20 als:

20 : 3 = 6 Rest 2.

Die Division, die als Teiler nur ganze Zahlen zulässt und das Ergebnis nicht als Bruch oder Dezimalzahl angibt, sondern mit Rest, wird oft als Ganzzahl-Division bezeichnet.

Dreht man jetzt die Ganzzahl-Division nochmals um und verwandelt sie wieder in eine Multiplikation, so erscheint es sinnvoll zu schreiben:

20 = 6 · 3 + 2.

Man kann dies als eine Zerlegung der Zahl 20 lesen: Die Zahl 20 ist sechsmal aus der 3 aufgebaut und es müssen 2 addiert werden.

Etwas abstrakter kann man diese Zerlegung auch so lesen: Die Zahl 20 wird durch den Teiler k = 3 in den Faktor q = 6 und den Rest r = 2 zerlegt (die Bezeichnung q soll an Quotient erinnern, r an Rest).

Im Allgemeinen lautet eine derartige Zerlegung für eine natürliche Zahl n mit einem Teiler k:

n = q · k + r, wobei r = 0, 1, ..., k - 1.

Teilt man n Gegenstände auf k Körbe auf, so liegen in jedem Korb q Gegenstände und es bleiben r Gegenstände übrig, wobei r nur die Zahlen von 0 bis k - 1 annehmen kann; wäre r gleich k, so könnte man einen Gegenstand mehr in jeden Korb legen.

Gilt r = 0 in der Zerlegung n = q · k + r (es bleibt also kein Rest), so nennt man k einen Teiler von n. Man schreibt dann k|n und sagt: "k ist Teiler von n".

So hat zum Beispiel die Zahl 5 außer 1 und 5 keine weiteren Teiler; dagegen besitzt die Zahl 6 die Teiler: 1, 2, 3 und 6.

Eine Zahl wie die 5, die nur die 1 und sich selbst als Teiler besitzt, wird als Primzahl bezeichnet.

Es ist klar, dass außer der 2 keine weitere gerade Primzahl existiert, da jede gerade Zahl durch 2 teilbar ist. Die ersten Primzahlen lauten (die 1 wird üblicherweise nicht zu den Primzahlen gerechnet):

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...

Primzahlen werden später näher untersucht. Jetzt soll gezeigt werden, wie die Division mit Rest eine Art von Gleichheit zwischen Zahlen einführt.

Die Kongruenz als Äquivalenzrelation

Die soeben eingeführte Division mit Rest erlaubt es jetzt, Zahlen danach zu klassifizieren, welchen Rest sie bei der Division durch einen bestimmten Teiler k erzeugen. Dies führt zu den Begriffen Äquivalenzrelation und Äquivalenzklassen, die im Folgenden erklärt werden.

Ein Beispiel zur Einführung: Die Kongruenz modulo 4

Betrachtet man in der Multiplikationstabelle in Abbildung 1 eine beliebige Spalte (ausgenommen die Spalte, in der die Vielfachen der 1 stehen), etwa die zum Faktor 4, so enthält sie Zahlen, die durch 4 teilbar sind – was sonst? Mit Hilfe der Begriffe, die mit der Ganzzahl-Division eingeführt wurden, kann man auch sagen, es sind Zahlen, die bei der Division durch 4 den Rest 0 besitzen.

Weiter erkennt man:

Man kann dies Beobachtung auch so formulieren: Die Division mit Rest durch 4 erzeugt zwischen den ganzen Zahlen eine Art von Gleichheit, die man vielleicht besser als Äquivalenz oder Kongruenz bezeichnet. Nämlich: Zwei Zahlen sind äquivalent (oder kongruent), wenn sie bei Division durch 4 den selben Rest besitzen, andernfalls sind sie nicht äquivalent (oder nicht kongruent). Die Äquivalenz wird dann oft mit einem eigenen Symbol ausgedrückt, etwa:

4 ≡ 8 oder 5 ≡ 9.

Um ausdrücklich darauf hinzuweisen, dass sich diese Äquivalenz auf den Rest bei Division durch 4 bezieht, schreibt man besser:

4 ≡ 8 (mod 4) oder 5 ≡ 9 (mod 4).

Dabei ist der Zusatz "(mod 4)" folgendermaßen zu verstehen:

Den Zusatz (mod 4) oder allgemein (mod k) sollte man nur weglassen, wenn aus dem Zusammenhang klar erkennbar ist, bezüglich welchem Teiler die Kongruenz gebildet wird.

In Abbildung 4 ist oben der Zahlenstrahl angedeutet, wobei diejenigen Zahlen mit gleicher Farbe gekennzeichnet sind, die bei Division durch 4 den gleichen Rest besitzen. Unten sind die vier möglichen Reste 0, 1, 2 und 3 dargestellt.

Abbildung 4: Kongruenz zwischen Zahlen, die bei Division durch 4 den gleichen Rest besitzen.Abbildung 4: Kongruenz zwischen Zahlen, die bei Division durch 4 den gleichen Rest besitzen.

Man erkennt in Abbildung 4: Ganze Zahlen, die auf dem Zahlenstrahl gleichfarbig gekennzeichnet sind (also nach bisheriger Sprechweise gleichen Rest bei Division durch 4 besitzen), haben eine Differenz, die durch 4 teilbar ist. Diese Eigenschaft wird üblicherweise zur Definition der Kongruenz verwendet.

Bei den Bezeichnungen, die die Beziehungen zwischen Zahlen beschreiben, haben sich folgende Konventionen eingespielt:

Der letzte Punkt lässt offen, was genau eine Äquivalenz ist; dies soll im nächsten Abschnitt formuliert werden und wird zu den Begriffen Äquivalenzrelation und Äquivalenzklassen führen.

Versuch einer abstrakten Formulierung von Kongruenz und Äquivalenz

Es wurde jetzt schon mehrfach angedeutet, dass die Kongruenz und die Gleichheit Gemeinsamkeiten besitzen – sicherlich aber auch Unterschiede. Um zu einem besseren Verständnis der Kongruenz zu gelangen, sollen schärfer formuliert werden:

Man definiert dazu erst, was unter Kongruenz modulo k zu verstehen ist.

Definition:

Sind x und y ganze Zahlen und k eine natürliche Zahl, dann heißen x und y kongruent modulo k, wenn ihre Differenz x - y durch k teilbar ist.

Sind die ganzen Zahlen x und y kongruent modulo k, so schreibt man x ≡ y (mod k).

Bemerkung: Man könnte die Definition auch so formulieren:

Sind x und y ganze Zahlen und k eine natürliche Zahl, dann heißen x und y kongruent modulo k, wenn bei Division von x beziehungsweise y durch k ein identischer Rest r bleibt. Dabei kann r nur eine der Zahlen 0, 1, ..., k - 1 annehmen.

Diese Definition ist zwar gleichbedeutend zur obigen Definition, hat aber den Nachteil, dass bei negativen Zahlen eventuell nicht klar ist, "in welche Richtung" der Rest gerechnet wird.

Es soll nun versucht werden, diejenigen Eigenschaften zu isolieren, die sowohl für die Gleichheit als auch für die Kongruenz zutreffend sind; sie werden dann verwendet, um den allgemeinen Begriff der Äquivalenz festzulegen.

Die Gleichheit hat folgende Eigenschaften:

  1. Für alle ganzen Zahlen x gilt: x = x.
  2. Wenn für zwei ganze Zahlen gilt x = y, dann gilt auch y = x.
  3. Gilt für drei ganze Zahlen x, y, z: x = y und y = z, dann gilt auch x = z.

Diese drei Eigenschaften werden der Reihe nach Reflexivität, Symmetrie und Transitivität bezeichnet.

Man kann sich jetzt leicht überlegen, dass diese drei Eigenschaften auch für die Kongruenz modulo k gelten. Und da man die gemeinsamen Eigenschaften von Gleichheit und Kongruenz identifiziert hat, verwendet man sie zur allgemeinen Definition einer Äquivalenzrelation.

Die Äquivalenzrelation

Eine Relation ≡ mit den drei Eigenschaften Reflexivität, Symmetrie und Transitivität nennt man Äquivalenzrelation; ihre allgemeine Definition könnte lauten:

Definition

Eine Relation ≡ auf einer Menge M heißt Äquivalenzrelation, wenn sie reflexiv, transitiv und symmetrisch ist. Dabei ist:

  1. Reflexivität: Für alle x ∈ M gilt: x ≡ x.
  2. Symmetrie: Für alle x, y ∈ M gilt: Falls x ≡ y, dann gilt auch y ≡ x.
  3. Transitivität: Für alle x, y, z ∈ M gilt: Falls x ≡ y und y ≡ z, dann gilt auch x ≡ z.

Gegenbeispiel:

Die Relation "x ist verschieden von y" auf einer beliebigen Menge M ist natürlich keine Äquivalenzrelation.

Die Symmetrie ist zwar erfüllt, aber nicht die Transitivität; sie würde jetzt lauten:

"Ist x verschieden von y und y verschieden von z, dann ist auch x verschieden von z."

Die letzte Schlussfolgerung hört sich plausibel an, man kann aber leicht ein Gegenbeispiel finden: x = 0, y = 1, z = 0.

Die Reflexivität ist natürlich auch nicht erfüllt.

Was ist eine Relation?

Der Begriff der Äquivalenzrelation enthält den Bestandteil Relation, den man umgangssprachlich so verstehen kann, dass die Äquivalenz x ≡ y eine Beziehung zwischen x und y herstellt. Dies ist nicht falsch, Relation wird hier aber als scharf definierter mathematischer Begriff gebraucht – und dieser Begriff soll hier wegen seiner Wichtigkeit kurz erklärt werden.

Eine Relation ist eng mit dem Begriff der Menge verbunden und in der Definition der Äquivalenzrelation war von einer (beliebigen) Menge M die Rede. Im Allgemeinen stellt eine Relation eine Beziehung zwischen 2 Mengen A und B her, indem sie aus dem kartesischen Produkt (oder Kreuzprodukt) A × B eine Menge R von geordneten Paaren (a, b) auswählt, wobei a ∈ A und b ∈ B. Dabei wird der Auswahl keine weitere Einschränkung auferlegt:

Beispiel:

Für die beiden Mengen

A = {1, 2, 3, 4}, B = {1, 2},

definiert

R = {(1, 1), (1, 2), (2, 2)}

eine Relation. Das kartesische Produkt A × B besteht aus 4 · 2 = 8 Elementen, von denen durch die Relation R drei ausgewählt werden.

Für eine Relation gibt es mehrere graphische Darstellungsmöglichkeiten, von denen in Abbildung 5 zwei gezeigt sind.

Abbildung 5: Graphische Darstellungen der Relation R. Links: In einem Diagramm, das an die graphische Darstellung einer Funktion erinnert; die Mengen A und B sind auf der x- beziehungsweise y-Achse aufgetragen. Die Elemente der Relation R sind Punkte in der Ebene. Rechts: Die Relation wird als Zuordnung gezeichnet; Elementen von A werden Elemente von B zugeordnet.Abbildung 5: Graphische Darstellungen der Relation R. Links: In einem Diagramm, das an die graphische Darstellung einer Funktion erinnert; die Mengen A und B sind auf der x- beziehungsweise y-Achse aufgetragen. Die Elemente der Relation R sind Punkte in der Ebene. Rechts: Die Relation wird als Zuordnung gezeichnet; Elementen von A werden Elemente von B zugeordnet.

Definition:

Sind A und B zwei Mengen, dann heißt eine Teilmenge R von geordneten Paaren (a, b), mit a ∈ A und B ∈ B, eine Relation zwischen A und B.

♦ ♦ ♦ ♦ ♦

Eine Relation ist nach obiger Definition eine Menge von geordneten Paaren, im Fall des Beispiels R von oben kann man die Relation auch durch

a ≤ b, mit a ∈ A, b ∈ B

beschreiben. Denn sucht man alle Elemente a und b aus den Mengen A und B auf, die a ≤ b erfüllen, erhält man gerade die drei oben genannten Paare.

Im Fall der Kongruenz sind die beiden Mengen A und B identisch und hier immer gleich der Menge der ganzen Zahlen Z; man spricht dann von einer Relation auf Z. Kombiniert man dies mit der Darstellung einer Relation mit Hilfe eines Vergleichsoperators wie ≡ (mod 4) oder ≤, erhält man eine völlig neue Sichtweise auf die Gleichheit und die Kongruenzen als Äquivalenzrelation.

Denn die Gleichheit

a = b mit a, b ∈ Z

kann man jetzt lesen als die Abkürzung für alle Zahlenpaare der Form

{(a, a): a ∈ Z}.

In Abbildung 6 links werden diese Zahlenpaare graphisch dargestellt (für |a| ≤ 10).

Abbildung 6: Die Relationen Gleichheit und Äquivalenz (mod 4) graphisch dargestellt (jeweils auf den ganzen Zahlen definiert).Abbildung 6: Die Relationen Gleichheit und Äquivalenz (mod 4) graphisch dargestellt (jeweils auf den ganzen Zahlen definiert).

Und entsprechend steht

a ≡ b (mod k) mit a, b ∈ Z, k ∈ N

für alle Zahlenpaare (a, b), die bei Division durch k den selben Rest besitzen – als Menge von Zahlenpaaren lässt sich diese Relation nur sehr umständlich angeben, einfacher ist die graphische Darstellung in Abbildung 6 rechts (für |a|, |b| ≤ 10 und k = 4).

Zum Schluss soll noch auf den Unterschied zwischen einer Relation und einer Funktion hingewiesen werden – denn die beiden Darstellungen in Abbildung 5 erinnern sehr an eine Funktion.

Eine Funktion ist ein Spezialfall einer Relation R (dabei sei R eine Teilmenge eines kartesischen Produktes A × B). Damit eine Relation zu einer Funktion f wird, müssen zwei zusätzliche Bedingungen erfüllt sein:

  1. Die Funktion f muss auf ganz A definiert sein, das heißt für jedes Element a ∈ A muss es ein (a, b) ∈ f geben.
  2. Die Funktion f muss eine eindeutige Zuordnung definieren, das heißt zu jedem a ∈ A darf es nur ein b ∈ B geben mit (a, b) ∈ f.

Betrachtet man die bisher besprochenen Beispiele, so sieht man:

Die Restklassen als Äquivalenzklassen

Einführendes Beispiel

Oben wurden mehrmals die ganzen Zahlen modulo 4 betrachtet, wobei zwei Zahlen als "kongruent modulo 4" gelten, wenn sie bei Division durch 4 einen identischen Rest besitzen. Man kann dies auch so sehen, dass damit von den ganzen Zahlen ein spezielles Merkmal betrachtet wird. Und jetzt ist es naheliegend, alle Zahlen, die in diesem Merkmal übereinstimmen zu einer Klasse zusammenzufassen.

Die Menge der ganzen Zahlen zerfällt dann in vier Teilmengen:

R[0] = {0, 4, -4, 8, -8, 12, -12, 16, ...}

R[1] = {1, 5, -3, 9, -7, 13, -11, 17, ...}

R[2] = {2, 6, -2, 10, -6, 14, -10, 18, ...}

R[3] = {3, 7, -1, 11, -5, 15, -9, 19, ...}

Diese Teilmengen werden als Restklassen bezeichnet, was die obige Schreibweise erklärt:

Die Restklassen haben offensichtlich folgende Eigenschaften:

Man beachte das Wort Jede in der ersten Aussage: Damit ist gesagt, dass es keine ganze Zahl gibt, die man nicht einer Restklasse zuordnen könnte. Und daher kann bei der Vereinigung aller Restklassen keine ganze Zahl übrig bleiben.

Das Beispiel bezieht sich auf die Restklasse modulo 4. Naheliegend ist es jetzt zu fragen:

Die folgenden Unterabschnitte werden zeigen, dass das gewählte Beispiel schon alle Eigenschaften beliebiger Restklassen zeigt und dass man derartige Mengen mit jeder Äquivalenzrelation definieren kann, was zum Begriff der Äquivalenzklasse führen wird.

Definition von Restklassen

Die Kongruenz bezüglich einer beliebigen natürlichen Zahl k kann jetzt verwendet werden, um die Restklassen bezüglich eines Teilers k zu definieren.

Definition: Ist k eine natürliche Zahl mit k > 1, so lassen sich k Mengen definieren:

R[i] = {n ∈ Z: n ≡ i (mod k)}, mit i = 0, 1, ..., k - 1.

Die Mengen R[i], i = 0, 1, ..., k - 1 werden als Restklassen modulo k bezeichnet.

Beispiele:

Für k = 2 gibt es zwei Restklassen. Die Restklassen modulo 2 sind die geraden Zahlen und die ungeraden Zahlen.

Die Restklassen modulo 4 wurden oben bereits angegeben.

Zumindest die positiven ganzen Zahlen kann man sofort einer Restklasse modulo 10 zuordnen: Die Endziffer ist zugleich der Rest bei der Division durch 10. Bei negativen Elementen muss man einmal umdenken: -9 liegt in der selben Restklasse wie 1.

Die Restklassen modulo 7 lassen sich leicht mit den Wochentagen identifizieren: Die Frage "Welcher Wochentag ist in 50 Tagen?" ist sehr einfach zu beantworten, da 50 und 1 in der Restklasse R[1] modulo 7 liegen. "In 50 Tagen ist der selbe Wochentag wie morgen."

Äquivalenzklassen

Die Restklassen wurden mit Hilfe der Kongruenz definiert; es spricht jetzt nichts dagegen, anstelle der Kongruenz eine beliebige Äquivalenzrelation auf einer Menge M zuzulassen. Als Äquivalenzklasse zu einem Element x ∈ M werden dann alle Elemente y ∈ M bezeichnet, die zu x äquivalent sind. Die von x gebildete Restklasse wird mit R[x] abgekürzt.

Definition:

Ist ≡ eine Äquivalenzrelation auf einer Menge M und x ∈ M. Dann heißt

R[x] = {y ∈ M : x ≡ y}

die Äquivalenzklasse zu x.

Beispiel: Wie unten bewiesen wird, ist die Kongruenz (zu einem beliebigen Teiler k > 1) eine Äquivalenzrelation. Daher sind Restklassen zugleich Äquivalenzklassen und haben sämtliche in den folgenden vier Sätzen formulierten Eigenschaften.

Satz 1: Ist ≡ eine Äquivalenzrelation auf einer Menge M, so ist für jedes x ∈ M die Äquivalenzklasse R[x] eine nicht-leere Menge.

Satz 2: Ist ≡ eine Äquivalenzrelation auf einer Menge M, x, y ∈ M und y ∈ R[x]. Dann ist R[x] = R[y].

Satz 3: Ist ≡ eine Äquivalenzrelation auf einer Menge M, so gilt für zwei Elemente x, y ∈ M:

Satz 4: Ist ≡ eine Äquivalenzrelation auf einer Menge M, so bilden die Äquivalenzklassen eine Zerlegung der Menge M, das heißt je zwei Äquivalenzklassen sind disjunkt und die Vereinigung aller Äquivalenzklassen stimmt mit M überein.

Bemerkungen:

  1. Die Sätze setzen voraus, dass "≡ eine Äquivalenzrelation auf einer Menge M" ist, das heißt die zugrundeliegende Relation ist eine Menge von geordneten Paaren im kartesischen Produkt M × M (siehe Erklärungen zu Relation weiter oben). Betrachtet man eine Relation als Abbildung von M nach M, so müssen nicht alle Elemente von M ein Abbild besitzen (siehe Beispiel oben mit R = {(1, 1), (1, 2), (2, 2)}, das nicht alle Elemente der Menge M = {1, 2, 3, 4) abbildet). Bei einer Äquivalenzrelation ist aber die Reflexivität vorausgesetzt, nämlich dass für alle x ∈ M gilt: x ≡ x. Somit sind insbesondere alle (x, x) ∈ M × M in der Äquivalenzrelation enthalten.
  2. Ein Element einer Äquivalenzklasse wird auch als Repräsentant der Äquivalenzklasse bezeichnet. Satz 2 kann man dann kurz so formulieren: "Die Bildung einer Äquivalenzklasse ist unabhängig von der Auswahl des Repräsentanten".
  3. Sind auf einer Menge M mehrere Äquivalenzrelationen definiert, so sollte klar sein, dass sie im Allgemeinen unterschiedliche Äquivalenzklassen und unterschiedliche Zerlegungen von M definieren. Man bestimme etwa zur Menge {-10, -9, ..., 9, 10} und zu den beiden Äquivalenzrelationen "Gleichheit =" und "Kongruenz modulo 4" die Äquivalenzklassen (siehe Abbildung 6).
  4. Satz 4 kann man auch so lesen: Jedes x ∈ M gehört genau einer Äquivalenzklasse an.

Beweis der Sätze:

Beweis von Satz 1: Aus der Reflexivität folgt, dass x ∈ R[x] (siehe auch Bemerkung 1).

Beweis von Satz 2: Satz 2 ist eine einfache Anwendung der Transitivität.

Ist z ∈ R[x], dann ist z zu x äquivalent; nach Voraussetzung ist y zu x äquivalent. Wegen der Transitivität ist dann y zu z äquivalent und somit z ∈ R[y] und damit ist R[x] eine Teilmenge von R[y].

Um die umgekehrte Teilmengen-Relation zu zeigen, geht man von einem Element z ∈ R[y] aus. Jetzt folgt aus der Transitivität, dass x äquivalent zu z ist, also ist R[y] eine Teilmenge von R[x].

Insgesamt gilt: R[x] = R[y]

Beweis von Satz 3: Sind x und y äquivalent, so sind nach Satz 2 die beiden Äquivalenzklassen R[x] und R[y] identisch.

Sind x und y nicht äquivalent, dann ist zu zeigen, dass die Äquivalenzklassen R[x] und R[y] disjunkt sind.

Man zeigt dies leicht durch Widerspruch. Angenommen es gibt ein z ∈ R[x] ∩ R[y]. Dann ist aber x ≡ z und zugleich y ≡ z. Wegen der Transitivität sind dann aber x und y äquivalent, was der Voraussetzung widerspricht.

Beweis von Satz 4: Nach Bemerkung 1 oben liegt jedes x ∈ M in irgendeiner Äquivalenzklasse. Daher muss die Vereinigung aller Äquivalenzklassen auch mit M übereinstimmen.

Dass die Äquivalenzklassen eine Zerlegung bilden, folgt dann aus Satz 3.

Anwendung auf Restklassen

Bisher wurde immer nur behauptet, dass die Kongruenzen tatsächlich eine Äquivalenzrelation sind – die formalen Ähnlichkeiten zwischen den Kongruenzen und einer Äquivalenzrelation sowie zwischen den Restklassen und den Äquivalenzklassen sind so groß, dass man kaum daran zweifeln wird. Der Beweis soll jetzt nachgeholt werden.

Satz 5: Die Kongruenz modulo k, k > 1, auf den ganzen Zahlen ist eine Äquivalenzrelation.

Beweis von Satz 5:

Reflexivität: Zu zeigen ist, dass für jede ganze Zahl x gilt x ≡ x (mod k). Dies gilt, da x = x + 0 · k und somit x - x = 0 · k, was gerade die Äquivalenz von x zu x bedeutet.

Symmetrie:

Wenn x - y durch 4 teilbar ist, dann ist auch y - x durch 4 teilbar; somit gilt die Symmetrie für alle x, y ∈ Z.

Transitivität:

Seien x, y, z ∈ Z mit x ≡ y (mod k) und y ≡ z (mod k). Dann gibt es ganze Zahlen m und n mit:

x - y = m · k, y - z = n · k.

Addiert man beide Gleichungen, so erhält man

x - z = (m + n) · k.

Diese besagt aber, dass x und z kongruent modulo k sind.

Damit ist bewiesen, dass die Kongruenz modulo k eine Äquivalenzrelation ist und somit gelten alle Aussagen, die allgemein für Äquivalenzrelationen formuliert wurden.

Zudem erlaubt letzte Satz 4 über Äquivalenzklassen eine neue Interpretation von Abbildung 4 unten: Bisher waren dort die vier möglichen Reste bei Division einer ganzen Zahl durch 4 dargestellt. Man kann die Abbildung aber auch so interpretieren, dass unten die Menge der ganzen Zahlen dargestellt ist, die durch die Kongruenz modulo 4 in vier Äquivalenzklassen zerlegt wird. Das heißt jeder Viertelkreis steht für eine unendliche Menge von ganzen Zahlen: 0 für die Zahlen mit Rest 0, 1 für die Zahlen mit Rest 1 und so weiter.

R-Skripte

Erzeugen der Additions- und Multiplikationstabellen

In Abbildung 1 wurden die Additions- und Multiplikationstabelle für das Zehnersystem gezeigt, wobei die Eingabewerte x und y die Werte 0, 1, 2, ..., 10 bei der Additionstabelle beziehungsweise 1, 2, ..., 10 bei der Multiplikationstabelle annehmen. Diese Tabellen können mit wenigen Zeilen Quelltext erzeugt werden.

Additionstabelle:

v <- (0:10)

m.plus <- outer(X = v, Y = v, FUN = "+")

m.plus
# [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11]
# [1,]    0    1    2    3    4    5    6    7    8     9    10
# [2,]    1    2    3    4    5    6    7    8    9    10    11
# [3,]    2    3    4    5    6    7    8    9   10    11    12
# [4,]    3    4    5    6    7    8    9   10   11    12    13
# [5,]    4    5    6    7    8    9   10   11   12    13    14
# [6,]    5    6    7    8    9   10   11   12   13    14    15
# [7,]    6    7    8    9   10   11   12   13   14    15    16
# [8,]    7    8    9   10   11   12   13   14   15    16    17
# [9,]    8    9   10   11   12   13   14   15   16    17    18
# [10,]    9   10   11   12   13   14   15   16   17    18    19
# [11,]   10   11   12   13   14   15   16   17   18    19    20

Der Vektor v definiert die Eingabewerte. Mit Hilfe der Funktion outer() wird das kartesiche Produkt der Eingabewerte gebildet, wobei sie durch die Addition verknüpft werden. Das Ergebnis ist eine 11 × 11 Matrix.

Multiplikationstabelle:

v <- (1:10)

m.mult <- outer(X = v, Y = v, FUN = "*")

m.mult
# [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
# [1,]    1    2    3    4    5    6    7    8    9    10
# [2,]    2    4    6    8   10   12   14   16   18    20
# [3,]    3    6    9   12   15   18   21   24   27    30
# [4,]    4    8   12   16   20   24   28   32   36    40
# [5,]    5   10   15   20   25   30   35   40   45    50
# [6,]    6   12   18   24   30   36   42   48   54    60
# [7,]    7   14   21   28   35   42   49   56   63    70
# [8,]    8   16   24   32   40   48   56   64   72    80
# [9,]    9   18   27   36   45   54   63   72   81    90
# [10,]   10   20   30   40   50   60   70   80   90   100

Ausgabe der geordneten Paare einer Relation

Im Theorieteil wurde eine Relation als Menge von geordneten Paaren (x, y) definiert, wobei

Die Berechnung aller geordneten Paare ist oft sehr umfangreich, kann in Spezialfällen aber mit wenigen Zeilen Quelltext erledigt werden. Dazu definiert man eine Funktion getPairs() mit folgenden Eingabewerten:

  1. Die Mengen X und Y werden als Vektoren x und y eingegeben. Als default-Wert für y empfiehlt sich y = x (für den Fall X = Y). Lassen sich X und Y nicht durch Vektoren beschreiben, wird die Iteration über die Elemente der Menge deutlich komplizierter.
  2. Eine Funktion relation, die als Rückgabewert einen logischen Wert besitzt und die angibt, ob x und y in der gewünschten Beziehung stehen; diese Funktion muss natürlich separat implementiert werden.
  3. Der Rückgabewert der Funktion getPairs() ist eine Matrix, wobei ein optionales Argument asCols angibt, ob die geordneten Paare als Spalten oder als Zeilen in die Matrix geschrieben werden. Im Skript unten ist asCols = TRUE der default-Wert (die Paare werden als Spalten ausgegeben).
getPairs <- function(x = 1, y = x, relation, asCols = TRUE){
  m <- NULL
  for(i in x){
    for(j in y){
      if(relation(i, j)){
        m <- cbind(m, c(i, j))
      }
    }
  }
  if(asCols) return(m)
  else return(t(m))
}

Zeile 3 und 4:

Die Schleifen sorgen dafür, dass die geordneten Paare in lexikographischer Anordnung der Matrix hinzugefügt werden.

Zeile 5 und 6:

Falls die mit relation() definierte Beziehung zwischen i und j erfüllt ist, wird die Spalte (i, j) zur Matrix hinzugefügt.

Zeile 10 und 11:

Zurückgegeben wird entweder die Matrix oder bei asCols = FALSE die transponierte Matrix.

Das folgende Skript definiert als Relation den logischen Vergleich <= und gibt die geordneten Paare einmal als Spalten und einmal als Zeilen aus; als Mengen werden X = Y = {1, 2, 3, 4} gewählt:

less.equal <- function(x, y){
  return(x <= y)
}
getPairs(x = (1:4), relation = less.equal)
# [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
# [1,]    1    1    1    1    2    2    2    3    3     4
# [2,]    1    2    3    4    2    3    4    3    4     4

getPairs(x = (1:4), relation =  less.equal, asCols = FALSE)
#     [,1] [,2]
# [1,]    1    1
# [2,]    1    2
# [3,]    1    3
# [4,]    1    4
# [5,]    2    2
# [6,]    2    3
# [7,]    2    4
# [8,]    3    3
# [9,]    3    4
# [10,]    4    4

Das folgende Skript definiert als Relation die Beziehung "x ist Teiler von y" (man beachte, dass die Argumente nicht vertauscht werden dürfen):

isDivisor <- function(x, y){
  return((y %% x) == 0)
}

getPairs(x = (1:10), relation = isDivisor, asCols = FALSE)
# [,1] [,2]
# [1,]    1    1
# [2,]    1    2
# [3,]    1    3
# [4,]    1    4
# [5,]    1    5
# [6,]    1    6
# [7,]    1    7
# [8,]    1    8
# [9,]    1    9
# [10,]    1   10
# [11,]    2    2
# [12,]    2    4
# [13,]    2    6
# [14,]    2    8
# [15,]    2   10
# [16,]    3    3
# [17,]    3    6
# [18,]    3    9
# [19,]    4    4
# [20,]    4    8
# [21,]    5    5
# [22,]    5   10
# [23,]    6    6
# [24,]    7    7
# [25,]    8    8
# [26,]    9    9
# [27,]   10   10

Sinnvoll wäre es hier natürlich die trivialen Teiler zu unterdrücken (also x = 1 und x = y).

Im folgenden Skript werden die Punkte aus Abbildung 6 rechts berechnet (zumindest auf einer Teilmenge):

equal.modulo4 <- function(x, y){
  return( (x %% 4) == (y %% 4) )
}

getPairs(x = (0:6), relation = equal.modulo4, asCols = FALSE)
# [,1] [,2]
# [1,]    0    0
# [2,]    0    4
# [3,]    1    1
# [4,]    1    5
# [5,]    2    2
# [6,]    2    6
# [7,]    3    3
# [8,]    4    0
# [9,]    4    4
# [10,]    5    1
# [11,]    5    5
# [12,]    6    2
# [13,]    6    6

Berechnung von Äquivalenzklassen

Unten wird eine Funktion getRelatedElements() definiert, mit der in einer Menge m die zu einem Element x die äquivalenten Elemente berechnet werden; dazu muss wieder eine Relation als Funktion übergeben werden. Die Eingabewerte sind somit:

  1. Die Menge m, die als Vektor eingegeben wird.
  2. Das Element x der Menge m.
  3. Die Funktion relation, die wieder für die Relation steht, bezüglich der die äquivalenten Elemente gesucht werden Rückgabewert der Funktion ist ein logischer Wert).

Der Rückgabewert von getRelatedElements() ist die Äquivalenzklasse als Vektor.

Aber man beachte: Es wird nicht überprüft, ob relaton tatsächlich eine Äquivalenzrelation ist.

getRelatedElements <- function(m = 1, x = 1, relation){
  stopifnot(is.element(el = x, set = m))
  v <- NULL
  for(i in m){
    if(relation(i, x)){
      v <- append(x = v, values = i)
    }
  }
  return(v)
}

Das folgende Skript zeigt zwei Aufrufe der Funktion getRelatedElements() mit der Funktion equal.modulo4(), die oben schon verwendet wurde:

getRelatedElements(m = (1:20), x = 1, relation = equal.modulo4)
# [1]  1  5  9 13 17

getRelatedElements(m = (1:20), x = 0, relation = equal.modulo4)
#  Error: is.element(el = x, set = m) is not TRUE

Das folgende Beispiel zeigt, dass getRelatedElements() nicht nur verwendet werden kann, um die Elemente der zugehörigen Äquivalenzklasse zu bestimmen. Aber es gilt: Ist relation eine Äquivalenzrelation, so liefert getRelatedElements() eine Äquivalenzklasse.

Im folgenden Skript wird die Relation isDivisor aufgerufen – sie ist keine Äquivalenzrelation:

getEquivalencetElements(m = (1:20), x = 15, relation = isDivisor)
# [1]  1  3  5 15