Chr.Nelius: Mathematik für Informatiker I , WS 2000/01 13.11.2000

4.c Äquivalenzrelationen

Eine weitere wichtige Klasse von Relationen bilden die sog. Äquivalenzrelationen, die eng mit dem Abstraktionsprozeß in der Mathematik zusammenhängen.

\underline{(4.8) DEF:} Eine Relation R auf einer Menge M heißt Äquivalenzrelation auf M,wenn gilt:

R_{1}) ∀ x ∈ M : x R x (Reflexivität)
R_{6}) ∀ x, y ∈ M : x R y ⟹ y R x (Symmetrie)
R_{3}) ∀ x, y, z ∈ M : (x R y ∧ yRz) ⟹ xRz (Transitivität)

Der Unterschied zu einer Ordnungsrelation liegt nur in einer Bedingung. Während R_{1}) und R_{3}) in beiden Fällen gelten, ist eine Äquivalenzrelation symmetrisch (R_{6}), eine Ordnungsrelation dagegen antisymmetrisch (R_{2}) . Trotzdem werden wir wesentliche Unterschiede feststellen. Gilt x R y, so sagt man auch, daß \underline{x äquivalent ist zu y bzgl. R}.

Beispiele für Äquivalenzrelationen:

6) Parallelität von Geraden der Ebene

7) Gleichheitsbeziehung zwischen den Elementen einer Menge

11) x, y ∈ ZZ : xRy :⟺ x − y ist gerade

12) x, y ∈ ZZ : xSy :⟺ x − y ist ein ganzzahliges Vielfaches von 3.

\underline{(4.9) DEF:} R sei eine Äquivalenzrelation auf einer Menge M. Für ein Element x ∈ M heißt

die Menge [ x]_{R} := { y | y ∈ M ∧ y R x } ⊆ M

aller Elemente von M, die zu x bzgl. R äquivalent sind, die Äquivalenzklasse von x bzgl. R. Die Menge M/R := { [ x]_{R} | x ∈ M } aller Äquivalenzklassen von Elementen aus M bzgl. R heißt die Quotientenmenge von M nach R.

Wenn aus dem zzusammenhang klar ist, um welche Äquivalenzrelation es sich handelt, so schreibt man auch nur [ x] für die Äquivalenzklasse von x. Man mache sich klar:

[ x]_{R} ∈ P(M) und M/R ⊆ P(M)

Beispiele: 6) Für g ∈ G ist [ g] = { h | h ∈ G ∧ h ∥ g }. Damit ist [ g] die Menge aller zu g parallelen Geraden. Das Kennzeichnende für [ g] ist also die gemeinsame Richtung, die alle Geraden aus [ g] haben.

7) Für die Äquivalenzrelation R der Gleichheit auf einer Menge M gilt: [ x]_{R} := { y | y ∈ M ∧ yRx } = { y | y ∈ M ∧ y = x } = {x}. Also M/_{R} = { { x } | x ∈ M }

11) Für die Relation R auf ZZ gilt: [ 0 ] = { x | x ∈ ZZ ∧ x R 0 } = G (Menge der geraden ganzen Zahlen) [ 1 ] = { x | x ∈ ZZ ∧ x R 1 } = U (Menge der ungeraden ganzen Zahlen) Ferner gilt [ 2 ] = [ 8 ] = [ −6 ] , [ −1 ] = [ 3 ] = [ −17 ] , ZZ/R = { [ 0 ], [ 1 ]}