Wikipedia · einfach zusammengefasst · Stand
Nachfolger (Mathematik)
In einer wohlgeordneten Menge (Ordinalzahl) besitzt jedes Element einen eindeutigen Nachfolger, es sei denn, es ist das Maximum der wohlgeordneten Menge. · Die …
Inhalt6 Abschnitte
Grundidee
In der Mathematik formalisieren die Begriffe Nachfolger und Vorgänger die Vorstellungen des Zählens, der Reihenfolge und allgemein auch von Abhängigkeiten wie Abstammung oder Amtsnachfolge.
Beim Zählen ist der Nachfolger einer ganzen Zahl die nächstgrößere Zahl: 2 ist der Nachfolger von 1, 3 der Nachfolger von 2 usw. Beim Abwärtszählen gelangt man von einer Zahl zu ihrem Vorgänger, zum Beispiel von 9 zu 8. In der Mathematik zählt man bei den natürlichen Zahlen ab 0. Diese Idee wurde in der Charakterisierung der natürlichen Zahlen durch Giuseppe Peano formalisiert; das zugehörige Axiomensystem heißt Peano-Axiomensystem.
Wichtig ist dabei nicht die Bedeutung einzelner Zahlwörter, sondern ihre Reihenfolge. Deshalb lassen sich Vorgänger und Nachfolger über das gewöhnliche Zählen hinaus auf geordnete Mengen und Graphen verallgemeinern.
Definition in strikt geordneten Mengen
Sei (M, <) eine strikt geordnete Menge und b ein Element aus M.
Ein Element a heißt Vorgänger oder unterer Nachbar von b, wenn a < b gilt und es kein Element a' in M gibt, das echt zwischen a und b liegt. Formal: a ≺ b, wenn a < b und es kein a' ∈ M gibt mit a < a' < b.
Ein Element c heißt Nachfolger oder oberer Nachbar von b, wenn b < c gilt und es kein Element c' in M gibt, das echt zwischen b und c liegt. Formal: c ≻ b, wenn b < c und es kein c' ∈ M gibt mit b < c' < c.
Bei einer strikten Totalordnung sind Vorgänger und Nachfolger, falls sie existieren, eindeutig bestimmt. Die Funktion, die jedem Element seinen eindeutig bestimmten Nachfolger zuordnet, heißt Nachfolgerfunktion. In allgemeineren Ordnungen kann ein Element jedoch mehrere nicht miteinander vergleichbare Vorgänger oder Nachfolger haben; dieses Konzept wird besonders in der Graphentheorie weiterverfolgt.
Ordnungstheoretische Definition
In der Ordnungstheorie wird für b ∈ M eine engere Definition verwendet, die auch in nicht total geordneten Mengen Eindeutigkeit sichern soll.
Ein Element a ist Vorgänger von b, wenn a < b gilt und jedes andere Element, das ebenfalls kleiner als b ist, kleiner oder gleich a ist. Formal: a ≺ b, wenn a < b und für alle a' ∈ M gilt: Aus a' < b folgt a' ≤ a.
Ein Element c ist Nachfolger von b, wenn b < c gilt und jedes andere Element, das größer als b ist, größer oder gleich c ist. Formal: c ≻ b, wenn b < c und für alle c' ∈ M gilt: Aus b < c' folgt c ≤ c'.
Nach dieser Definition sind Vorgänger und Nachfolger, sofern vorhanden, auch in nicht total geordneten Mengen eindeutig. Sie bildet daher stärker den Zählprozess ab.
Beispiel mit Teilern von 12
Ein Beispiel ist die Teilerrelation auf der Menge der Teiler von 12. Eine Relation wie 3 < 6 bedeutet hier: 3 teilt 6. Ebenso bedeutet 1 < 4: 1 teilt 4.
Diese Ordnung ist nicht total, weil nicht alle Elemente miteinander vergleichbar sind. Zum Beispiel ist 2 weder ein Teiler von 3 noch ist 3 ein Teiler von 2.
Je nach Definition ergeben sich unterschiedliche Aussagen: Im Sinne der ordnungstheoretischen Definition hat die 2 keinen Nachfolger, aber einen Vorgänger. Im Sinne der allgemeineren Definition hat die 2 einen Vorgänger und zwei Nachfolger. In der Darstellung der Teilerrelation haben außerdem 1 und 2 jeweils zwei Nachfolger, während 6 und 12 jeweils zwei Vorgänger haben.
Anwendungen
In einer wohlgeordneten Menge, also bei einer Ordinalzahl, besitzt jedes Element einen eindeutigen Nachfolger, außer wenn es das Maximum der wohlgeordneten Menge ist. Elemente ohne Vorgänger heißen Limeselemente oder Grenz-Ordinalzahlen.
Die Existenz von Vorgängern und Nachfolgern in geordneten Mengen kann auch mit topologischen Mitteln untersucht werden; dazu gehört die Ordnungstopologie.
Für gerichtete Graphen werden entsprechende Nachbarschaftsbegriffe in der Graphentheorie behandelt.
Verallgemeinerung
Die Definition lässt sich auf strikte partielle Ordnungen übertragen. Bei schwachen totalen oder partiellen Ordnungen (M, ≤) muss zusätzlich gefordert werden, dass Vorgänger und Nachfolger andere Elemente sind; bei strikten Ordnungen ist das automatisch erfüllt.
Für a, b ∈ M heißt a ein unmittelbarer Vorgänger von b, wenn a ≤ b und a ≠ b gilt und es kein b' ∈ M gibt, das echt zwischen a und b liegt. Formal muss ausgeschlossen sein, dass ein b' existiert mit a ≤ b', a ≠ b', b' ≤ b und b' ≠ b. Ein unmittelbarer Nachfolger wird analog definiert.
Viele Autoren verwenden Vorgänger und Nachfolger allgemeiner, nämlich ohne die Bedingung, dass kein Element dazwischenliegt. In dieser Sprechweise heißen die hier beschriebenen Begriffe unmittelbarer oder direkter Vorgänger beziehungsweise unmittelbarer oder direkter Nachfolger.
