Äquivalenzrelation
Auf der Grundlage der Menge der natürlichen Zahlen ℕ = { 0, 1, 2, 3, 4, ... } lassen sich weitere Zahlenmengen, nämlich ℤ (die Menge der ganzen Zahlen), ℚ (die Menge der rationalen Zahlen), u.s.w. auf eine ganz eigentümliche Art konstruieren. Der zentrale Begriff, mit dessen Hilfe diese Konstruktionen möglich sind, ist der Begriff Äquivalenzrelation. Auch in anderen Zusammenhängen ist dieser Begriff wichtig.
Eine Relation ~ ⊂ M x M auf einer Menge M heißt Äquivalenzrelation auf M, falls ~ transitiv, symmetrisch und reflexiv ist, das heißt, falls für alle x, y, z ∈∈ M das Folgende gilt:
x ~ y und y ~ z ⇒ x ~ z (Transitivität)
x ~ y ⇒ y ~ x (Symmetrie)
x ~ x (Reflexivität)
Eine Menge M, auf der eine Äqivalenzrelation definiert ist, zerfällt sozusagen von selbst in Teilmengen Mi, und zwar so, dass für je zwei Elemente x und y einer Teilmenge Mi stets x ~ y gilt. Das Umgekehrte ist ebenfalls richtig: Jede Zerlegung einer Menge M induziert in natürlicher Weise eine Äquivalenzrelation auf M.
Die Zerlegung einer nichtleeren Menge M ist eine Menge ℳ = { M1, M2, M3, ... } von Teilmengen von M mit den zwei Eigenschaften:
(I) M1 ∪ M2
∪ M3 ∪ ... = M
(II) Mi ∩ Mk
= { } ⇔ Mi
≠ Mk
Die so definierten Teilmengen von M sind also paarweise disjunkt und jedes Element von M ist in genau einer dieser Teilmengen von M enthalten. Jedes Element Mi ∈∈ ℳ ist eindeutig bestimmt und wird repräsentiert durch irgendein m ∈∈ Mi.
Jede Zerlegung induziert eine Äquivalenzrelation.
Sei ℳ eine Zerlegung einer nichtleeren Menge M. Dann ist die Relation ~ ⊂ M x M, definiert durch
x ~ y ⇔ x, y ∈∈ Mi für ein Mi ∈∈ ℳ
eine Äquivalenzrelation auf M.
Beweis:
Unter der Annahme, dass ℳ
eine Zerlegung von M ist, ist zu zeigen, dass die so definierte Relation ~
transitiv, symmetrisch und reflexiv ist.
(i) Seien x, y und z Elemente aus M.
Dann folgt aus x ~ y und y ~ z, dass x, y ∈∈ Mp
und y, z ∈∈ Mq mit Mp, Mq ∈∈ ℳ.
Damit haben die Mengen Mp
und Mq wenigstens ein Element gemeinsam, nämlich y.
Also können Mp und Mq nicht disjunkt sein.
Da
ℳ eine Zerlegung von M ist, folgt Mp = Mq und damit x ~ z.
(ii) x ~ y ist nach Definition von ~ gleichbedeutend mit x, y ∈∈ Mi mit Mi ∈∈ ℳ, das heißt, es gilt auch y ~ x.
(iii) Da nach Definition zu jedem x ∈∈ M ein Mi ∈∈ ℳ existiert mit x ∈∈ Mi, folgt x ~ x sofort.
Jede Äquivalenzrelation induziert eine Zerlegung.
Sei ~ eine Äquivalenzrelation auf einer nichtleeren Menge M. Dann ist
ℳ = { M(x) ⊂ M: x ∈∈ M }, definiert durch M(x) = { y ∈∈ M: x ~ y }
eine Zerlegung von M.
Beweis:
Unter der Annahme, dass ~ eine Äquivalenzrelation auf M ist, ist zu
zeigen, dass erstens
die Vereinigungsmenge aller Mengen M(x) mit x ∈∈ M gleich M ist und zweitens,
dass alle Mengen M(x) ∈∈ ℳ paarweise disjunkt sind.
(i) Weil ~ eine Äquivalenzrelation auf M ist, folgt für jedes x ∈∈ M sofort, dass x ~ x.
Also gilt nach
Definition der Mengen M(x), dass x
∈∈ M(x) und man hat
M = ∪x∈∈M{ x } ⊆ ∪x∈∈M M(x) ⊆ M.
(ii) Angenommen, es gibt unter den Elementen der oben definierten Menge
ℳ zwei nicht identische
Mengen M(x) und M(y), die nicht disjunkt sind. Dann existiert mindestens ein z* ∈∈ M mit z* ∈∈ M(x)
und z* ∈∈ M(y), mit anderen Worten: x ~ z* und z* ~ y.
Wegen der Transitivität von ~ folgt x ~ y.
Sei nun z irgendein Element aus M(x), dann gilt x ~ z und mit x ~ y auch
z ~ y, also ist z auch Element aus M(y).
Ebenso gilt: wenn z irgendein Element aus M(y) ist, dann ist z auch
Element von M(x).
Also sind die Mengen M(x) und M(y) identisch und dies steht im Widerspruch
zur getroffenen Annahme.
Zwei beliebig heraus gegriffene Mengen M(x), M(y)
∈∈
ℳ sind also entweder
identisch oder disjunkt.
Sei ~ eine Äquivalenzrelation auf einer nichtleeren Menge M. Dann heißen die zu ~ gehörenden Teilmengen
M(x) = { y ∈∈ M: x ~ y }
Äquivalenzklassen und die Menge
ℳ aller dieser Teilmengen − das ist die zu ~ gehörende Zerlegung
− wird Quotientenmenge von ~
genannt und mit M/~ bezeichnet.
Die zu einer Äquivalenzrelation ~ auf M gehörenden Äquivalenzklassen
M(x) werden oft auch mit dem Symbol [x] gekennzeichnet. x heißt
Repräsentant der Äquivalenzklasse [x].
Beispiel 1:
Sei m irgendeine positive natürliche Zahl. Dann hat man mit
x ~ y ⇔def (x − y) wird von m geteilt
eine Äquivalenzrelation auf ℤ, der Menge der ganzen Zahlen,
definiert.
Beweis:
Sei m ∈∈
ℤ+ beliebig, aber fest vorgegeben.
(1) zu zeigen: Die Relation ~ ist transitiv.
Seien x, y und z ganze Zahlen mit x ~ y und y ~ z.
Dann gibt es k, j ∈∈ ℤ
mit x − y = k·m und y − z = j·m.
Also hat man z − y = z − (x − k·m) = −j·m.
⇒ x − z = j·m + k·m = (j + k)·m.
Mit (j + k) ∈∈ ℤ
folgt, dass m ein Teiler ist von (x − z);
mit anderen Worten: x ~ z.
(2) zu zeigen: Die Relation ~ ist symmetrisch.
Seien x und y ganze Zahlen mit x ~ y.
Dann gibt es ein k ∈∈ ℤ
mit x − y = k·m.
−k ist ebenfalls eine ganze Zahl, also gilt auch y ~ x.
(3) zu zeigen: Die Relation ~ ist reflexiv.
Es gilt x − x = 0·m und das bedeutet, dass
x zu sich selbst äquivalent ist.
Die zugehörigen Äquivalenzklassen heißen Restklassen modulo m. Wenn [x] eine solche Restklasse darstellt, dann sind folgende Aussagen gleichwertig:
y
∈∈ [x]
x ~ y
m | (x − y)
x ≡ y mod m
In Worten:
y ist Element der
Äquivalenzklasse [x]
x ist äquivalent zu y
m ist ein Teiler von (x−y)
x ist kongruent zu y modulo m
Beispielsweise sind [0] = { ..., −6, −3, 0, 3, 6, ... }, [1] = { ..., −2, 1, 4, 7, ... } und [2] = { ..., −1, 2, 5, ... } die Restklassen modulo 3 und es gilt 0 ≡ 6 mod 3 oder −4 ≡ 5 mod 3.
Die Quotientenmenge ℤ/~ ist endlich und umfasst m Elemente: [0], [1], [2], ... [m − 1]. Dies hat Carl Friedrich Gauß im ersten Abschnitt seiner Disquisitiones Arithmeticae wie folgt formuliert (Art. 3):
Satz. Sind m aufeinander folgende ganze Zahlen a,
a + 1, a + 2, ..., a + m − 1 und eine andere A gegeben, so wird
eine und nur eine von jenen dieser letzteren nach dem Modul m
congruent sein.
Beweis:
Sei m
∈∈
ℕ* beliebig, aber fest gewählt.
Seien ferner a und A ganze Zahlen.
Dann sind zwei Fälle zu unterscheiden:
Fall 1.
m | (a − A). Dies ist gleichbedeutend damit, dass a ≡ A
mod m.
In diesem Fall setzen wir k = (a − A)/m und wissen, dass k ∈∈ ℤ.
Fall 2.
m ∤ (a − A). Sei k die kleinste ganze
Zahl mit k > (a − A)/m. Dann folgt, dass a < k·m + A.
Angenommen, a + m ≤ k·m + A. Dann hat
man a − A ≤ k·m − m
bzw. (a − A)/m ≤ k − 1.
Nach Voraussetzung ist aber bereits k die kleinste ganze Zahl mit (a − A)/m < k,
und da (a − A)/m = k − 1
wegen m ∤ (a − A)
nicht gelten kann, ergibt sich ein
Widerspruch zur Annahme. Es folgt also a + m > k·m + A bzw.
k·m + A < a + m.
Insgesamt hat man also a ≤ k·m + A < a + m,
mit anderen Worten: k·m + A ≡ A mod m
und (k·m + A) muss eine der Zahlen a, a+1, a+2, ... a+m−1 sein.
Damit ist bewiesen, dass A zu einer der Zahlen
a, a+1, a+2, ..., a+m−1 kongruent ist
und es gilt k·m + A = a + i mit i = 0, 1, ... m−1.
Es bleibt noch zu zeigen, dass A zu genau einer dieser Zahlen kongruent ist:
Aus dem Obenstehenden folgt
k − 1
<
(a − A)/m
< (a − A + m)/m
< k + 1.
⇒
k − 1
< (a − A)/m
< (a − A + 1)/m
< ...
< (a − A + m−1)/m
< (a − A + m)/m
< k + 1.
Es gibt aber zwischen k−1 und k+1 nur genau eine ganze
Zahl,
demzufolge gibt es auch genau ein i mit ((a + i) − A)/m ∈∈ ℤ,
was zu beweisen war.
Beispiel 2:
Sei MPf die Menge aller Pfeile in einem
dreidimensionalen euklidischen Raum, wobei ein Pfeil definiert sein soll
durch seinen Anfangspunkt, seine Richtung und seine Länge. Seien p, q ∈ MPf,
dann hat man mit
p ~ q ⇔def p und q sind richtungs- und längengleich
eine Äquivalenzrelation auf MPf definiert. Die zugehörigen Äquivalenzklassen heißen Pfeilklassen. Die nachfolgende Zeichnung zeigt fünf verschiedene Repräsentanten einer bestimmten Pfeilklasse.
Die Quotientenmenge MPf/~, das heißt die Menge aller Pfeilklassen im sogenannten Anschauungsraum, bildet mit geeignet definierter Addition „+“ bzw. skalarer Multiplikation „·“ ein ℝ-Vektorraum. (→ Vektor, Abschnitt Pfeile und Pfeilklassen).
