Äquivalenzrelationen

By | 9. April 2017

Unter einer Äquivalenzrelation versteht man in der Mathematik eine Relation, die reflexiv, symmetrisch und transitiv ist. Äquivalenzrelationen sind für die Logik und die Mathematik von großer Bedeutung. Eine Äquivalenzrelation teilt eine Menge restlos in disjunkte (elementfremde) Untermengen auf, die als Äquivalenzklassen bezeichnet werden.

Definition: Äquivalenzrelation

Eine Äquivalenzrelation ist eine homogene, binäre Relation auf einer Grundmenge, die folgende Eigenschaften besitzt:

  • reflexiv (x ~ x)
  • symmetrisch (x ~ y  y ~ x)
  • transitiv (x ~ y  und  y ~ z   x ~ z )

Definition: Äquivalenzklasse (=Restklasse)

Eine Äquivalenzklasse [x] ist die Menge aller Elemente der Grundmenge M, die zum Element x äquivalent sind: [x]:={y∈M|y∼x}

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.

Beispiel 1: Ostereier

M=Menge aller Schoko-Ostereier aus Nugat-, Vollmich- und Bitter-Schokolade
Wir betrachten auf der Menge M nun die Äquivalenzrelation “»” die wie folgt definiert sei:
x » y genau dann, wenn x und y aus der selben Schokolade sind.

Erstmal prüfen wir nach, dass » wirklich eine Äquivalenzrelation ist:

-reflexiv: ist x aus Vollmilch, dann ist x » x auch aus Vollmilch. Damit ist die Relation reflexiv

-symetrisch: Sei x » y. Dann sind x und y beides Vollmilch-Eeier, damit sind dann auch y und x aus Vollmilch, damit gilt:  y»x. Damit ist die Relation symmetrisch

-transitiv: wenn x»y und y»z dann gilt auch x»z. Damit ist die Relation auch transitiv
Die Äquivalenzrelation » bezüglich Vollmilch-Eier sortiert die Menge M der Eier in 2 Haufen:
Ein Haufen mit Nugat. und Bitter-Schoko-Eier und ein Haufen mit Vollmilch-Eier.

Der Vollmilch Haufen bildet dann eine Äquivalenzklasse, da alle Elemente der
Teilmenge untereinander äquivalent (d.h. hier aus Vollmilch) sind.

Beispiel 2: Modulo-Rechnung

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.

Die zugehörigen Äquivalenzklassen heißen Restklassen modulo m. Wenn [x] eine solche Restklasse darstellt, dann sind folgende Aussagen gleichwertig:

  • y ist Element der Äquivalenzklasse [x]: y [x]
  • x ist äquivalent zu y: x ~ y
  • m ist ein Teiler von (x−y): m | (x − y)
  • x ist kongruent zu y modulo m: x y mod 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.

Oder auch alle Zahlen die  z.B. mod 5 gerechnet 0 ergeben, würden somit in einer eigen Klasse liegen: {0,5,10,15,-5,…}