Strenge Ordnung

Eine strenge Ordnung (auf Englisch: strict order) ist eine Relation, die irreflexiv, transitiv und asymmetrisch ist. Asymmetrie bedeutet, dass wenn a < b, es nie vorkommen kann, dass b < a. Diese Ordnung drückt 'streng kleinere' Typ-Verbindungen aus, bei denen ein Element nie mit sich selbst in Relation steht, aber wenn ein Element kleiner als ein anderes ist und dieses andere kleiner als ein Drittes, dann ist das Erste auch kleiner als das Dritte.

Formale Definition

Irreflexiv: Ein Element steht nie in Relation zu sich selbst.

Transitiv: Wenn a mit b und b mit c in Relation steht, dann steht a mit c in Relation.

Asymmetrisch: Wenn a mit b in Relation steht, steht b nicht mit a in Relation.

Beispiele für strenge Ordnungen

• Die "<"-Relation auf natürlichen Zahlen: irreflexiv, transitiv, asymmetrisch.
• Die strenge Teilmengenrelation ⊂ auf Mengen: irreflexiv, transitiv, asymmetrisch.
• Die "vorhergehende in Wörterbuchordnung"-Relation auf Wörtern: irreflexiv, transitiv, asymmetrisch.

Gegenbeispiele (Nicht-strenge Ordnungen)

• Die "≤"-Relation: Nicht irreflexiv (jedes Element steht in Relation zu sich selbst).
• Die "Freund von"-Relation unter Menschen: Nicht asymmetrisch (wenn A Freund von B ist, kann B Freund von A sein).
• Die "teilt"-Relation auf natürlichen Zahlen: Nicht asymmetrisch (wenn 2 4 teilt und 4 2? Nein, aber für Gleiches wäre es, aber da reflexiv nein).

Zusammenhang mit nicht-strengen Ordnungen

Jede strenge Ordnung hat eine 'nicht-strenge' Variante (z.B. < statt ≤), und umgekehrt. Wenn es eine strenge Ordnung R gibt, können wir daraus die nicht-strenge Ordnung R′ erzeugen, indem (a,b) ∈ R′ genau dann, wenn a = b oder (a,b) ∈ R. Das stellt die enge Verbindung zwischen den beiden Konzepten sicher.

Zusammenfassung

Eine strenge Ordnung ist eine Relation, die irreflexiv, transitiv und asymmetrisch ist. Dieser Typ Relation modelliert 'streng kleinere' Vergleiche. Sie spielt eine wichtige Rolle in Mathematik und Informatik, weil viele Strukturen auf strengen Ordnungen aufbauen.

Übungsaufgabe