Gerichtete Menge

Bedeutung und Grundidee

Eine gerichtete Menge ist in der Mathematik eine Verallgemeinerung einer nichtleeren, linear geordneten Menge. Ihre Elemente müssen nicht alle miteinander vergleichbar sein. Entscheidend ist stattdessen, dass zu je zwei Elementen ein gemeinsames späteres beziehungsweise größeres Element existiert.

Gerichtete Mengen werden in der Topologie zur Definition von Netzen verwendet. Netze verallgemeinern Folgen und ermöglichen es, Konvergenz auch in allgemeineren Räumen zu beschreiben. In der Kategorientheorie dienen gerichtete Mengen unter anderem zur Definition von Limites und Kolimites.

Definition einer nach oben gerichteten Menge

Eine nichtleere Menge X heißt bezüglich einer Relation ◁ gerichtet, wenn die folgenden drei Bedingungen gelten:

• Reflexivität (R1): Für jedes x ∈ X gilt x ◁ x.
• Transitivität (R2): Für alle x, y, z ∈ X gilt: Aus x ◁ y und y ◁ z folgt x ◁ z.
• Gemeinsame obere Schranke (R3): Für alle x, y ∈ X gibt es ein z ∈ X mit x ◁ z und y ◁ z.

Die Relation ◁ heißt Richtung. Wegen Reflexivität und Transitivität ist sie eine Quasiordnung. Anders als bei einer Halbordnung wird nicht verlangt, dass aus x ◁ y und y ◁ x die Gleichheit x = y folgt. Bedingung (R3) lässt sich auch so ausdrücken: Jede endliche Teilmenge besitzt eine obere Schranke. Daher ist jede halbgeordnete Menge, in der Suprema vorhanden sind, nach oben gerichtet.

Die Schreibweise x ◁ y wird als „x vor y“ oder „y nach x“ gelesen. Für die zweite Lesart findet man auch y ▷ x. Um deutlich zu machen, welche Richtung verwendet wird, bezeichnet man häufig das geordnete Paar (X, ◁) als gerichtete Menge.

Richtungen und unterschiedliche Begriffsverwendungen

Eine nach unten gerichtete Menge erhält man, wenn die Forderung nach einer gemeinsamen oberen Schranke durch die Forderung nach einer gemeinsamen unteren Schranke ersetzt wird:

• (R3′): Für alle x, y ∈ X gibt es ein z ∈ X mit z ◁ x und z ◁ y.

Einige Autoren, darunter der Artikel, verwenden „gerichtete Menge“ als Kurzform für „nach oben gerichtete Menge“. Andere nennen eine Menge nur dann gerichtet, wenn sie bezüglich derselben Relation sowohl nach oben als auch nach unten gerichtet ist.

Auf derselben Menge können verschiedene Richtungen definiert werden. Außerdem ist eine bezüglich ◁ nach oben gerichtete Menge hinsichtlich der gespiegelten Relation ▷ nach unten gerichtet. Diese wird durch x ▷ y genau dann definiert, wenn y ◁ x gilt.

Typische Beispiele

Die Menge X = {(0,0), (0,1), (1,0)} werde komponentenweise geordnet: (x₁,y₁) ◁ (x₂,y₂) genau dann, wenn x₁ ≤ x₂ und y₁ ≤ y₂ gilt. Sie ist nach unten gerichtet, denn (0,0) ist beispielsweise eine gemeinsame untere Schranke von (0,1) und (1,0). Sie ist jedoch nicht nach oben gerichtet, weil dieses Paar innerhalb von X keine gemeinsame obere Schranke besitzt.

Auf ℕ kann n ◁ m durch „n teilt m“, also n ∣ m, definiert werden. Zu zwei natürlichen Zahlen liefert ihr kleinstes gemeinsames Vielfaches eine gemeinsame obere Schranke und erfüllt damit (R3). Die gerichtete Menge (ℕ, ∣) wird bei kategoriellen Limites verwendet, etwa bei den proendlichen Zahlen.

Die üblichen Ordnungen (ℕ, ≤) und (ℝ, ≤) sind ebenfalls gerichtet. Mit ihnen können Grenzwerte von Folgen für n → ∞ beziehungsweise von Funktionen für x → ∞ als Konvergenz zugehöriger Netze aufgefasst werden.

Auf ℕ² kann man komponentenweise ordnen: (n,m) ◁ (p,q) genau dann, wenn n ≤ p und m ≤ q. Diese Richtung erlaubt es, die Konvergenz von Doppelfolgen als Netzkonvergenz zu definieren.

Für eine beliebige Menge M ist auch ihre Potenzmenge 𝒫(M) mit der Inklusion gerichtet: A ◁ B bedeutet A ⊆ B. Eine gemeinsame obere Schranke zweier Teilmengen ist ihre Vereinigung.

Richtung auf ein Zentrum

Für X ⊆ ℝⁿ und einen festen Punkt ρ ∈ ℝⁿ kann eine Richtung durch x ◁ y genau dann definiert werden, wenn ‖x − ρ‖ ≥ ‖y − ρ‖ gilt. Ein Element y liegt in diesem Sinn nach x, wenn es mindestens ebenso nah am Punkt ρ liegt. Man sagt, X sei „auf ρ gerichtet“, oder nennt ρ das Richtungszentrum von X.

Mit dieser Richtung lässt sich der Grenzwert einer Funktion f: X → ℝⁿ für x → ρ als Netzkonvergenz des zugehörigen Netzes auffassen. Das Beispiel zeigt zugleich, warum unterschiedliche Richtungen auf derselben Grundmenge sinnvoll sein können: Die Richtung legt fest, was beim Durchlaufen der Menge als „später“ gilt.