Relationenabschlüsse

Ein Relationenabschluss bedeutet, die Relation um den kleinsten Betrag zu erweitern, der notwendig ist, um eine gegebene Eigenschaft zu erfüllen. Wir sprechen am häufigsten von reflexivem, symmetrischem oder transitivem Abschluss.

Reflexiver Abschluss

Im reflexiven Abschluss fügen wir (a,a)-Paare zu jedem Element hinzu, um die Relation reflexiv zu machen.

Zum Beispiel, wenn R = { (1,2) } und A = {1,2}, dann R_ref = { (1,2), (1,1), (2,2) }.

Symmetrischer Abschluss

Im symmetrischen Abschluss fügen wir das inverse Paar zu jedem Paar hinzu, um die Relation symmetrisch zu machen.

Zum Beispiel, wenn R = { (1,2) }, dann R_sym = { (1,2), (2,1) }.

Transitiver Abschluss

Im transitiven Abschluss fügen wir jedes Paar hinzu, das aus Transitivität folgt. Dies ist die kleinste transitive Relation, die die ursprüngliche Relation enthält.

Mit anderen Worten: Wenn (a,b) ∈ R und (b,c) ∈ R, dann wird (a,c) auch im transitiven Abschluss sein. Zum Beispiel, wenn R = { (1,2), (2,3) }, dann R_trans = { (1,2), (2,3), (1,3) }.

Beispiel zum Vergleich der Drei Abschlüsse

Sei A = {1,2,3} und R = { (1,2), (2,3) }.

• Reflexiver Abschluss: { (1,2), (2,3), (1,1), (2,2), (3,3) }
• Symmetrischer Abschluss: { (1,2), (2,1), (2,3), (3,2) }
• Transitiver Abschluss: { (1,2), (2,3), (1,3) }

Eigenschaften

• Der Abschluss ist immer die kleinste Relation, die die gegebene Eigenschaft erfüllt.
• Der reflexive Abschluss enthält immer alle (a,a)-Paare.
• Der symmetrische Abschluss enthält immer alle inversen Paare.
• Der transitive Abschluss enthält jede Verbindung, die aus Ketten intermediärer Elemente folgt.

Zusammenfassung

Relationenabschlüsse ermöglichen es, eine Relation mit den notwendigen Paaren zu ergänzen, um sie reflexiv, symmetrisch oder transitiv zu machen. Dies ist entscheidend in der Mathematik, da viele Beweise und Algorithmen darauf aufbauen.

Übungsaufgabe