Bernhard Kabelka - Lineare Algebra und analytische Geometrie I: "Mengen und Relationen

Relationen

Eine Relation zwischen zwei Mengen und ist eine Teilmenge des kartesischen Produkts . Ist , so spricht man von einer binären Relation.

Eine binäre Relation heißt Äquivalenzrelation, wenn folgende drei Gesetze gelten:

(Reflexivität)
(Symmetrie)
(Transitivität)

Eine Äquivalenzrelation heißt Gleichheitsrelation, wenn jedes Element nur mit sich selbst in Relation steht, und Allrelation, wenn jedes Element mit allen anderen in Relation steht.

Eine Äquivalenzklasse ist definiert durch

Die Gesamtheit der Äquivalenzklassen bilden eine Partition von , d.h. es gilt

$forall i in I: A_i \neq Ø, A_i \subseteq A$
$\bigcup_{i in I} A_i = A$
$forall i,j in I: i \neq j ==> }A_i \cap A_j = Ø$

Eine binäre Relation heißt Halbordnung oder partielle Ordnung, wenn folgende Gesetze erfüllt sind:

(Reflexivität)
(Antisymmetrie)
(Transitivität)

Eine Halbordnung heißt Totalordnung (oder Kette oder lineare Ordnung), wenn je zwei Elemente vergleichbar sind, d.h. wenn gilt:

Eine Totalordnung heißt Wohlordnung, wenn jede nichtleere Teilmenge $T \subseteq H$ ein minimales Element besitzt:

$T \subseteq H ==> }exists x_{0} in T: forall x in T: x_{0} <= x$

Für Wohlordnungen gilt das Prinzip der transfiniten Induktion: Ist eine Wohlordnung, eine Teilmenge von , und gilt für alle

${ y in H | y < x } \subseteq T ==> }x in T$

dann gilt: .

Das Lemma von Zorn besagt, dass, wenn jede Teilkette einer Halbordnung eine obere Schranke besitzt, ein maximales Element in existiert.