Totale (Vollständige) Relation

Eine Relation ist total (oder vollständig), wenn beliebige zwei verschiedene Elemente vergleichbar sind. Das bedeutet, dass für jedes a,b ∈ A entweder (a,b) ∈ R oder (b,a) ∈ R.

Mit anderen Worten: Zwischen beliebigen zwei Elementen können wir immer bestimmen, welches vor dem anderen kommt oder mit ihm in Relation steht; es gibt kein Paar, das nicht verglichen werden kann.

Beispiele für totale Relationen

• Die ≤-Relation auf natürlichen Zahlen: Für beliebige zwei Zahlen können wir entscheiden, welche kleiner oder gleich ist.
• Die ≥-Relation ist auch total, weil beliebige zwei Zahlen auch damit verglichen werden können.
• Alphabetische Ordnung (lexikografische Ordnung) unter Wörtern: Zwischen beliebigen zwei Wörtern können wir bestimmen, welches dem anderen folgt.

Gegenbeispiele (Nicht-totale Relationen)

• Die Teilbarkeitsrelation auf natürlichen Zahlen ist nicht total, weil z.B. 2 3 nicht teilt und 3 2 nicht teilt.
• Die Geschwister-Relation ist auch nicht total, weil nicht jedes Paar von Personen eine solche Verbindung hat.

Zusammenfassung

In totalen Relationen sind beliebige zwei Elemente vergleichbar, was grundlegend für Ordnungen ist, z.B. das Anordnen von Zahlen oder Wörtern. Wenn eine Relation nicht total ist, gibt es bestimmte Paare, die nicht verglichen werden können.

Übungsaufgabe