Äquivalenzrelation
Äquivalenzrelation — klingt ziemlich kompliziert! Wir zeigen dir hier im Artikel und im Video anhand von anschaulichen Beispielen, was das ist und wie du Äquivalenzrelationen beweisen kannst.
Inhaltsübersicht
Äquivalenzrelation einfach erklärt
Mit einer Äquivalenzrelation kannst du Beziehungen zwischen Dingen in einer Menge darstellen. Dabei werden zwei Dinge „äquivalent“ genannt, wenn sie gleiche oder ähnliche Eigenschaften haben.
Beispiel: Schau dir eine Menge M von Menschen an. Zwei Menschen sind sich ähnlich, wenn sie dieselbe Haarfarbe haben. Damit kannst du dann eine Äquivalenzrelation definieren.
Alex und Berta haben beide blonde Haare. Du sagst daher: Alex ist äquivalent zu Berta (a ∼ b). Auch Clara ist blond und steht damit in Relation zu den beiden: c ∼ a, c ∼ b
Dominik hat schwarze Haare, er ist nicht äquivalent zu Alex, aber zu Erika, denn sie hat auch schwarze Haare (d ∼ e).
Du bekommst so also eine Menge von Paaren, die zu dieser Äquivalenzrelation R gehören, weil sie in Beziehung zueinander stehen: (a, b), (c, a), (c, b), (d, e) ∈ R
Um auszudrücken, dass a und b äquivalent sind, gibt es verschiedene Schreibweisen:
- a ∼ b
- a ∼R b
- (a, b) ∈ R
- a R b
Äquivalenzrelation — Eigenschaften
Eine Äquivalenzrelation R auf einer Grundmenge M kannst du an drei Eigenschaften erkennen:
-
Reflexivität: Jedes Element der Menge M ist äquivalent zu sich selbst. Beispiel: Alex ist blond, genau wie er selbst, also a ∼ a.
(∀ a ∈ M : a ∼ a)
-
Symmetrie: Wenn ein Element a aus M äquivalent zu b ist, dann ist auch b äquivalent zu a. Eine solche Beziehung beruht also auf Gegenseitigkeit. Beispiel: Wenn Alex dieselbe Haarfarbe hat wie Berta (a ∼ b), dann hat Berta auch dieselbe Haarfarbe wie Alex (b ∼ a).
(∀ a, b ∈ M : a ∼ b ⇒ b ∼ a)
-
Transitivität: Ist a äquivalent zu b und b wiederum äquivalent zu c, dann ist auch a äquivalent zu c, das heißt, die Beziehung überträgt sich. Beispiel: Wenn Clara dieselbe Haarfarbe hat wie Berta (c ∼ b) und Berta wiederum dieselbe wie Alex (b ∼ a), dann kannst du daraus schließen, dass auch Clara und Alex dieselbe Haarfarbe haben: a∼ c.
(∀ a, b, c ∈ M : a ∼ b ∧ b ∼ c ⇒ a ∼ c)
Eine Äquivalenzrelation R beschreibt eine reflexive, symmetrische und transitive Beziehung zwischen je zwei Elementen. Indem du Elemente zusammenfasst, die paarweise äquivalent zueinander sind, kannst du damit die Grundmenge M in disjunkte Teilmengen gliedern. Mathematisch ausgedrückt ist eine Äquivalenzrelation damit eine Teilmenge des kartesischen Produktes M x M (R ⊂ M x M).
Äquivalenzrelation — Beispiele
Bei konkreten Beispielen für Äquivalenzrelationen hast du eine Grundmenge M und eine spezielle Eigenschaft vorgegeben. Diese Eigenschaft setzt zwei gleiche oder ähnliche Dinge in Beziehung zueinander und sagt dir damit, wann zwei Elemente äquivalent sind.
Das kann etwas ganz Alltägliches sein, wie „verwandt sein mit“ bei einer Menge M von Menschen. Oft ist es aber eine mathematische Eigenschaft. Zum Beispiel die Parallelität auf einer Menge von Geraden.
Um zu beweisen, dass du es tatsächlich mit einer Äquivalenzrelation zu tun hast, musst du überprüfen, ob sie die drei Eigenschaften Reflexivität, Symmetrie und Transitivität erfüllt.
Mach dir das an ein paar Beispielen klar!
Verwandtschaft als Äquivalenzrelation
Schau dir als Erstes ein Beispiel aus dem Alltag an. M ist hier eine Menge von Menschen und die Beziehung, durch die du die Äquivalenzrelation definierst, ist die Verwandtschaft. Das heißt: a ∼ b, falls a mit b verwandt ist.
Um zu beweisen, dass das tatsächlich eine Äquivalenzrelation ist, musst du nun also die drei Eigenschaften überprüfen:
- Reflexivität: Jeder Mensch ist verwandt mit sich selbst, passt also!
- Symmetrie: Wenn du mit einer Person verwandt bist, dann ist diese Person auch verwandt mit dir. Die Verwandtschaftsrelation ist folglich auch symmetrisch.
- Transitivität: Stell dir vor, du bist mit einer Person verwandt (etwa mit deiner Mutter) und diese Person ist dann mit einer dritten Person verwandt (zum Beispiel ist deine Mutter verwandt mit ihrem Bruder). Dann bist du auch mit der dritten Person verwandt (der Bruder deiner Mutter ist dein Onkel). Damit ist auch die Transitivität erfüllt.
Du hast durch einfache Logik also gezeigt: Die Verwandtschaftsbeziehung ist ein Beispiel für eine Äquivalenzrelation!
Parallelität von Geraden als Äquivalenzrelation
Dieses Beispiel hat etwas mehr mit Mathe zu tun. Du betrachtest eine Menge M von Geraden und nennst zwei davon äquivalent, wenn sie parallel zueinander sind. Bekommst du so eine Äquivalenzrelation?
- Reflexivität: Jede Gerade ist parallel zu sich selbst.
- Symmetrie: Wenn eine Gerade g parallel zu einer anderen Geraden h liegt, dann liegt auch h parallel zu g.
- Transitivität: Ist eine Gerade g parallel zu h und h parallel zu j, dann ist auch g parallel zu j.
Also definiert die Parallelität von Geraden eine Äquivalenzrelation.
Äquivalenzrelationen und Äquivalenzklassen
Du kannst Äquivalenzrelationen auch aus einem anderen Blickwinkel betrachten: Sie verbinden nicht nur Objekte mit ähnlichen Eigenschaften innerhalb einer Menge M, sondern teilen diese Menge auch in einzelne Teilmengen — sogenannte Äquivalenzklassen.
Alle Elemente einer Äquivalenzklasse sind äquivalent zueinander und jedes Element ist nur in genau einer Äquivalenzklasse. Erinnere dich dazu nochmal an das Beispiel mit den Haarfarben.
Da gibt es einmal die Teilmenge von Alex. Du bezeichnest sie mit [a]. Dazu gehören Berta, Clara und natürlich Alex selbst, denn sie alle haben dieselbe Haarfarbe wie Alex (a,b,c ∈ [a]) . Alex nennst du dann den Repräsentanten der Äquivalenzklasse. Genauso gut könntest du dafür aber auch Berta oder Clara nehmen. „Die Äquivalenzklasse von Alex ([a])“, „Die Äquivalenzklasse von Berta ([b])“ und „Die Äquivalenzklasse von Clara ([c])“ bezeichnen alle dieselbe Teilemenge ([a] = [b] = [c]).
Auch für die weiteren Teilmengen der Schwarz- und Braunhaarigen kannst du einen Repräsentanten bestimmen. Zum Beispiel repräsentiert Erika die Gruppe aus Dominik und Erika ([e] = {d,e}).
Felix steht als einziger Braunhaariger dann für die Teilmenge, die nur aus ihm selbst besteht ([f] = {f}).
Die Menge M kannst du also in die drei Teilmengen [a], [e] und [f] zerlegen. Mathematiker sagen dazu auch „Partition“. a, e und f repräsentieren damit also die gesamte Menge M. Deshalb nennst du {a, e, f} auch ein vollständiges Repräsentanten-System.
Formal: für ein Element x ∈ M gilt: [x]: = {y∈ M | y ∼ x}. x ist dann der Repräsentant der Äquivalenzklasse [x].
Super, jetzt kennst du einige Beispiele für Äquivalenzrelationen und weißt, was sich hinter den Begriffen „Äquivalenzrelation“ und Äquivalenzklasse“ verbirgt. Schau dir zum Abschluss noch einen Beweis dazu an, wenn du noch tiefer in das Thema einsteigen willst!
Äquivalenzrelation beweisen
Für eine Äquivalenzrelation R auf einer Menge M und zwei beliebige Elemente x, y ∈ M gilt:
- Die Äquivalenzenklassen von x und y stimmen genau dann überein, wenn x und y äquivalent zueinander sind: [x] = [y] ⇔ x ∼ y
- Sind zwei Elemente x und y nicht äquivalent zueinander, dann haben ihre Äquivalenzklassen keine gemeinsamen Elemente, sind also disjunkt:
x
y ⇒ [x] ∩ [y] = Ø
Beweis Teil a: [x] = [y] ⇔ x ∼ y
Am besten zeigst du die beiden Richtungen in zwei Schritten:
-
[x] = [y] ⇒ x ∼ y
Du startest also mit der Annahme [x] = [y]. Jedes Element aus [x] liegt also auch in [y]. Insbesondere gilt x ∈ [x] und damit auch x ∈ [y]. In [y] liegen aber genau die Elemente, die äquivalent zu y sind. Also x ∼ y.
-
[x] = [y] ⇐ x ∼ y
Hier nimmst du umgekehrt an, dass x ∼ y gilt. Du willst zeigen, dass jedes Element w aus [x] auch in [y] liegt und jedes Element v aus [y] auch in [x]. Zusammen ergibt das dann die Aussage [x] = [y].
Schau dir als Erstes also w ∈ [x] an:
Wegen der Definition der Äquivalenzklasse [x], weißt du w ∼ x. Zusammen mit der Annahme x ∼ y kannst du die Eigenschaft der Transitivität benutzen. Du bekommst w ∼ y und damit w ∈ [y].
Für v ∈ [y] machst du genau dasselbe:
Es gilt w ∼ y. Weil die Äquivalenzrelation symmetrisch ist, gilt nicht nur x ∼ y, sondern auch y ∼ x. Nun wendest du wieder die Transitivitätseigenschaft an: v ∼ y und y ∼ x ergebene zusammen genommen v ∼ x. Das bedeutet v liegt in [x].
Spitze, du hast also bewiesen, dass die Tatsache, dass zwei Elemente äquivalent zueinander sind, genau dasselbe ist wie die Aussage, dass ihre Äquivalenzklassen übereinstimmen.
Beweis Teil b: x y ⇒ [x] ∩ [y] = Ø
Eine gute Strategie ist hier der Beweis durch Widerspruch.
Dafür nimmst du an, dass die rechte Seite nicht stimmt ([x] ∩ [y] ≠ Ø). Es gibt also ein Element z im Schnitt von [x] und [y].
Wegen z ∈ [x] weißt du, dass z äquivalent zu x sein muss (z ∼ x). Mithilfe der Symmetrie erhältst du damit auch die Aussage: x ∼ z.
Genauso kannst du aus z ∈ [y] schließen, dass z ∼ y.
Weil die Äquivalenzrelation transitiv ist, ergeben x ∼ z und z ∼ y zusammen x ∼ y.
Das kann aber nicht sein, denn die linke Seite deiner Aussage war ja gerade x y. Aus diesem Widerspruch schließt du, dass deine Annahme, die linke Seite sei falsch, nicht stimmen kann.
Also folgt aus x y tatsächlich, dass die beiden Äquivalenzklassen von [x] und [y] disjunkt sind.
Eine wichtige Äquivalenzrelation in der Mathematik ist die sogenannte „Kongruenz modulo n“ auf der Menge der natürlichen Zahlen . Auch n ist eine natürliche Zahl, zum Beispiel n = 2.
Zwei natürliche Zahlen a und b heißen kongruent modulo n, wenn sie beim Teilen durch n denselben Rest haben. Du schreibst dann: a ≡ b mod n.
Überleg dir das mal am Beispiel n = 2. Diese Äquivalenzrelation teilt die Menge der natürlichen Zahlen dann in zwei Äquivalenzklassen: Solche, die beim Teilen durch 2 Rest 0 haben, also durch 2 teilbar sind (0, 2, 4, 6 …) und solche, bei denen als Rest 1 übrig bleibt, wenn du sie durch 2 teilst (1, 3, 5, 7, …). Als Äquivalenzklassen bekommst du also genau die geraden und die ungeraden Zahlen heraus!
Vektorraum
Du hast nun an vielen Beispielen von Äquivalenzrelationen gesehen, was eine Äquivalenzrelation ist und wie du sie beweisen kannst. Wie eine Äquivalenzrelation ist auch ein Vektorraum durch eine Reihe von Eigenschaften charakterisiert. Welche das sind und was du sonst noch über Vektorräume wissen musst, erfährst du in unserem Video dazu.
