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:
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.