Äquivalenzrelationen

Eine Äquivalenzrelation auf einer Menge A ist eine binäre Relation R ⊆ A × A, die Reflexivität, Symmetrie und Transitivität erfüllt. Reflexivität bedeutet, dass jedes Element a in A zu sich selbst in Beziehung steht (a R a). Symmetrie bedeutet, dass aus a R b auch b R a folgt. Transitivität bedeutet, dass aus a R b und b R c folgt a R c.

Aus jeder Äquivalenzrelation ergibt sich eine Zerlegung der Grundmenge A in disjunkte Teilmengen, die Äquivalenzklassen. Für jedes a ∈ A ist die Klasse [a] = { x ∈ A | a R x }. Die Menge der Klassen A/R = { [a] | a ∈ A } wird Quotientenmenge genannt. Jedes Element von A gehört zu genau einer Äquivalenzklasse, und die Klassen bilden eine Partition von A.

Wichtige Beispiele: Die Gleichheit auf A ist die triviale Äquivalenzrelation. Die Kongruenzrelation modulo n auf den ganzen Zahlen ist eine Äquivalenzrelation, deren Klassen die Restklassen modulo n bilden. Weitere Beispiele entstehen, indem man Elemente nach einer Eigenschaft gruppiert, zum Beispiel zwei Zahlenwerte, die denselben Rest bei Division durch n haben.

Zusammenhang: Umgekehrt lässt sich aus jeder Partition von A eine Äquivalenzrelation definieren, indem x R y gilt, wenn x und y in derselben Teilmenge der Partition liegen. Damit gibt es eine enge, bijektive Verbindung zwischen Äquivalenzrelationen auf A und Partitionen von A.