dh-Materialien
Mathematische Begriffe
 

Äquivalenzrelation

 
Zerlegungen von Mengen nach oben

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:

~ y  und  y ~ z   x ~ z   (Transitivität)
~ y    y ~ x   (Symmetrie)
~ 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 Mi.


Jede Zerlegung induziert eine Äquivalenzrelation. nach oben

Sei eine Zerlegung einer nichtleeren Menge M. Dann ist die Relation ~  M x M, definiert durch

~ y x, y M 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. nach oben

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 M sofort, dass x ~ x.
Also gilt nach Definition der Mengen M(x), dass x M(x) und man hat 
M = xM{ x }  xM 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.

 
Quotientenmengen nach oben

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

~ 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]
~ 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.

Repräsentanten einer Pfeilklasse a

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