Logo

DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000

Äquivalenzrelationen

Definition: Eine reflexive, symmetrische und transitive binäre Relation auf einer Menge M wird Äquivalenzrelation genannt. Dann definieren wir für jedes x Î M die Menge Rx = {y Î M|(x,y) Î R}. Diese Teilmengen Rx, x Î M, von M werden Äquivalenzklassen der Äquivalenzrelation genannt.

Eine Partition einer Menge M ist eine Menge {Pi | i Î I} paarweise disjunkter nichtleerer Teilmengen von M, deren Vereinigung gerade M ergibt.

Partitionen einer Menge "sind" Äquivalenzrelationen.

Sei M eine Menge.
Die Menge (!) aller Äquivalenzklassen jeder Äquivalenzrelation R auf M bildet eine Partition P¢ von M.
Jede Partition P = {Pi: i Î I} von M erzeugt eine Äquivalenzrelation P¢ auf M durch (x,y) Î R Û $i Î I: x, y Î Pi.
Für jede Äquivalenzrelation R auf M ist R¢¢ = R.
Für jede Partition P von M ist P¢¢ = P.

Eine k-Partition ist eine Partition der Mächtigkeit k. Wieviele k-Partitionen einer n-elementigen Menge gibt es? Diese Zahlen werden Stirling-Zahlen zweiter Art S(n,k) genannt.

Beispiele von Äquivalenzrelationen sind "äquivalent modulo k" bei natürlichen Zahlen, oder auch Äquivalenz von aussagelogischen Formeln. In beiden Beispielen haben wir auch noch Verknüpfungen, "+" und "*" im ersten Beispiel, im zweiten Beispiel werden Formeln durch Junktoren zu grösseren Formeln verknüpft. Die Verknüpfungen sind nun verträglich mit der entsprechenden Äquivalenzrelation: Sind a und b kongruent modulo k, und c und d kongruent modulo k, so sind auch a+c und b+d kongruent modulo k, ebenso wie a*c und b*d. Bei den Formeln sind (nach der zweiten Substitutionsregel etwa A Ú C und B Ú D äquivalent, falls A und B äquivalent sind und C und D äquivalent sind (und ebenso mit anderen Junktoren). Es gibt für solche Sachverhalte natürlich wieder einen Namen:

Sei M eine Menge mit einer binären Verknüpfung "$". Eine Äquivalenzrelation R auf M heißt Kongruenzrelation (bzgl. "$") falls sie mit "§" in dem Sinne verträglich ist, daß aus (a,b) Î R und (c,d) Î R immer auch (a§c,b§d) Î R folgt.

Jede Relation R auf einer Menge M läßt sich zu einer Äquivalenzrelation erweitern indem wir die transitive Hülle "reflexivieren" und "symmetrisieren":
Sei R Í M ×M. Wir definieren x ~ y falls x = y oder ((x,y) Î R* & (y,x) Î R*). Dies definiert eine Äquivalenzrelation
Deren Äquivalenzklassen werden die starken (Zusammenhangs-) Komponenten von R genannt.

Im Beispiel rechts gibt es zwei starke Komponenten: {a,b,c} und {d,e}.

Übungsaufgabe: R sei eine Relation auf einer Menge M. M¢ sei die Menge der starken Komponenten. Wir definieren eine Relation R¢ Í M¢×M ¢ durch (A,B) Î R¢ Û $a Î A $b Î B: (a,b) Î R, die Kondensation von R.
Zeigen Sie, daß die starken Komponenten bzgl. R' alle einelementig sind. Zeigen Sie auch daß die Kondensation der transitiven Hülle (R*)¢ gleich der transitiven Hülle der Kondensation (R¢) * ist.


Bild Die Menge aller Partitionen einer festen Menge M läßt sich ordnen: Wir nennen eine Partition {A1, A2, ... , Ak} gröber als die Partition {B1, B2, ... , Bm}, falls es eine Abbildung f: {1,2,...,m} ® {1,2,...k} gibt, so daß für jedes i Bi Í Af(i) gilt. Insbesondere ist dann f surjektiv und deshalb k £ m. Diese Relation ist eine Ordnungsrelation. Rechts ist das Hasse-Diagramm für die Menge M={a,b,c,d} abgebildet, wobei die Schreibweise ad|b|c eine Abkürzung für die Partition {{a,d},{b},{c}} ist.

Preisaufgabe:

Zeigen Sie, daß die durch "... ist gröber als ..." geordnete Menge aller Partitionen einer festen Menge M sogar verbandsgeordnet ist. Ist es immer auch eine Boolesche Algebra? Falls nicht, welches der Axiome (Existenz von 0 und 1, Existenz eines Komplements, Distributivgesetze) ist verletzt? Es gab Preise!
Hier ist die Lösung
Erich Prisner
erstellt im Februar 2000, geändert im Mai 2000.