Binäre Relationen (2)


Eine Relation, die reflexiv,  symmetrisch  und transitiv  ist, heißt eine Äquivalenzrelation. Solche Relationen sind wichtig, weil sie die Tatsache ausdrücken, daß zwei Elemente ein geeignetes Merkmal  gemeinsam  haben.

Zu jeder Äquivalenzrelation R gehört eine Klassenzerlegung der Grundmenge M, und umgekehrt: die Äquivalenzklasse [a] eines Elements a besteht aus allen zu a äquivalenten Elementen von M. Zwei verschiedene Klassen sind disjunkt, haben also kein Element gemeinsam, und insgesamt schöpfen sie die Grundmenge aus.

Umgekehrt können wir einer beliebigen disjunkten Klassenzerlegung der Grundmenge eine Äquivalenzrelation zuordnen: zwei Elemente sind genau dann äquivalent, wenn sie in derselben Klasse liegen.

Eine Relation R, die irreflexiv,  asymmetrisch  und transitiv  ist, heißt eine (schwache) Halbordnung; sie kann ausdrücken, daß ein Element bezüglich geeigneter Merkmale kleiner  als ein anderes ist. Dabei ist es nicht nötig, daß für ein beliebiges Paar <a,b> von Elementen genau eine der drei Beziehungen aRb, bRa oder a=b gilt; manche Paare können unvergleichbar sein.

Beispiele für Halbordnungen:

Eine Halbordnung, bei der alle Paare von Elementen vergleichbar sind, heißt eine (schwache) Totalordnung. Sie bestimmt für die Elemente der Grundmenge eine eindeutige Reihenfolge.

Ist eine Relation R asymmetrisch, transitiv und reflexiv  anstatt irreflexiv , so nennt man sie eine starke  Halbordnung (ebenso kann man starke Totalordnungen einführen). Für sie gilt: aRb bRa a=b

Eine Halbordnung läßt sich stets in eine Totalordnung einbetten, oft auf mannigfache Weise. Dazu legt man für Paare von vorher unvergleichbaren Elementen willkürlich eine Reihenfolge fest und nimmt jeweils gleich die Beziehungen dazu, die sich aus der Forderung der Transitivität ergeben. Ein systematisches Verfahren, aus einer Halbordnung eine Totalordnung zu machen, heißt topologisches Sortieren.  Wir gehen hier darauf nicht ein.


zurück | Inhalt | Index | vor | Vorlesung

Klaus Lagally, 22. Februar 2000, 19:36