Nachfolger (Mathematik)

Begriffe aus der Mathematik
(Weitergeleitet von Nachfolgerfunktion)

In der Mathematik werden durch die Begriffe Nachfolger und Vorgänger die gedanklichen Konzepte der Abstammung oder Amtsnachfolge und des Zählens formalisiert und verallgemeinert.

Nachfolger und Vorgänger beim Zählen und in Ordnungen

Bearbeiten
 
Die Nachfolgerrelation in der Ordnung der natürlichen Zahlen. Beim Zählen schreitet man von Zahl zu Zahl in der Richtung der Pfeile vor. In der Mathematik zählt man ab 0, man fängt also direkt vor dem ersten Objekt zu zählen an.

Beim Zählen ist der Nachfolger einer ganzen Zahl intuitiv die nächstgrößere Zahl: So ist etwa 2 der Nachfolger von 1, 3 der Nachfolger von 2 usw. Beim Abwärtszählen kommt man von 9 zu ihrem Vorgänger 8 usw. Diese an sich naive Entdeckung, die Kinder immer wieder im Spiel nachvollziehen, kann man zu einer mathematischen Charakterisierung der natürlichen Zahlen formalisieren, die von Giuseppe Peano entwickelt wurde und ihm zu Ehren Peano-Axiomensystem heißt.

Beim Aufwärts- und Abwärtszählen stellt man fest, dass es auf die Bedeutung der Zahlwörter gar nicht ankommt, sondern nur auf ihre Reihenfolge. Diese Feststellung lässt eine Verallgemeinerung der Zählnachbarn Vorgänger und Nachfolger auf Graphen und geordnete Mengen zu:

Definitionen

Bearbeiten

Sei   eine strikt geordnete Menge,  . Dann heißt

  •   Vorgänger oder unterer Nachbar von  , wenn   ist und kein größeres Element als   mit dieser Eigenschaft existiert
formal:  , wenn      .
  •   Nachfolger oder oberer Nachbar von  , wenn   ist und kein kleineres Element als   mit dieser Eigenschaft existiert
formal:  , wenn  , [1]
 
Die Teilerrelation auf der Menge der Teiler von 12. 1 und 2 haben je zwei Nachfolger, 6 und 12 je zwei Vorgänger.

Für eine strikte Totalordnung sichert diese Definition zugleich, dass Vorgänger und Nachfolger (falls vorhanden) eindeutig bestimmt sind. Die Funktion, die jedem Element seinen eindeutig bestimmten Nachfolger zuordnet, heißt Nachfolgerfunktion. Im Allgemeinen kann aber ein Element mehrere, untereinander nicht vergleichbare Vorgänger und Nachfolger haben. Dieses allgemeinere Konzept verfolgt die Graphentheorie weiter. Es kommt damit dem vormathematischen Abstammungskonzept nahe.

In der Ordnungstheorie definiert man zu  :

  •   ist Vorgänger von  , wenn   ist und jedes andere Element mit dieser Eigenschaft kleiner ist
formal:  , wenn  .
  •   ist Nachfolger von  , wenn   ist und jedes andere Element mit dieser Eigenschaft größer ist
formal:  , wenn  ,

Somit sind Vorgänger und Nachfolger, sofern vorhanden, auch in nicht total geordneten Mengen eindeutig. Damit wird eher der Zählprozess abgebildet.

Beispiel

Bearbeiten

Der abgebildete Graph veranschaulicht die Teilerrelation in der Menge der Teiler der Zahl 12. Die abstrakte Relation 3 < 6 wird hier durch Pfeile dargestellt und hat die Bedeutung 3 teilt 6, 1 teilt 4 usw. Die Ordnung ist nicht total, denn es gibt Elemente, die man nicht miteinander vergleichen kann, zum Beispiel ist 2 weder ein Teiler von 3 noch umgekehrt. Im Sinne der zweiten, ordnungstheoretischen Definition hat die 2 keine Nachfolger aber einen Vorgänger, im Sinne der ersten, allgemeineren Definition hat die 2 einen Vorgänger und zwei Nachfolger.

Anwendungen

Bearbeiten
  • In einer wohlgeordneten Menge (Ordinalzahl) besitzt jedes Element einen eindeutigen Nachfolger, es sei denn, es ist das Maximum der wohlgeordneten Menge. Elemente ohne Vorgänger heißen hier Limeselemente oder auch Grenz-Ordinalzahlen.
  • Die Existenz von Vorgängern und Nachfolgern in geordneten Mengen kann auch mit topologischen Mitteln untersucht werden. Siehe dazu Ordnungstopologie.
  • Den Begriff von Vorgängern und Nachfolgern in gerichteten Graphen wird im Artikel Nachbarschaft (Graphentheorie) erklärt.

Verallgemeinerung

Bearbeiten

Die obige Definition kann ohne Weiteres auf strikte partielle Ordnungen ausgedehnt werden. Im allgemeinen Fall, insbesondere im Fall einer (schwachen) totalen oder partiellen Ordnung   muss man immer noch fordern, dass es sich beim Vorgänger bzw. Nachfolger um ein anderes Element handelt (was im Fall einer strikten Ordnung immer erfüllt ist).

Für   mit

  und
 ,

heißt   ein (unmittelbarer) Vorgänger von  ;[A 1] ein (unmittelbarer) Nachfolger wird analog definiert.

Viele Autoren fassen die Begriffe Vorgänger und Nachfolger allgemeiner, nämlich jeweils ohne die zweite Bedingung.[A 2] Die hier definierten Begriffe heißen in dieser alternativen Sprechweise dann unmittelbarer (direkter) Vorgänger bzw. Nachfolger.[2]

Einzelnachweise

Bearbeiten
  1. Johannes Köbler: Einführung in die Theoretische Informatik, Humboldt-Universität Berlin, Institut für Informatik, WS2013/14, S. 79
  2. Wiebke Petersen: Mathematische Grundlagen der Computerlinguistik - Ordnungsrelationen, 4. Foliensatz, Heinrich-Heine-Universität Düsseldorf, Institute of Language and Information, PDF: WS 2011/12 S. 93 WS 2013/14 S. 90, aufgerufen am 21. April 2018.

Fußnoten

Bearbeiten
  1. Durch diese Vorgehensweise wird zu einer gegebenen Relation   eine neue Relation (unmittelbarer, synonym direkter) Vorgänger bzgl.   bestimmt.
  2. Ein solcher Vorgänger bzw. Nachfolger im weiteren Sinn muss aber nicht zwangsläufig über einen Weg, d. h. eine endliche Sequenz direkter (d. h. unmittelbarer) Vorgänger (quasi indirekt oder mittelbar) erreichbar sein, wie z. B. 0 und 10 auf   oder   – im Gegensatz zu  , wo es einen solchen endlichen Weg gibt. Zum Begriff des Wegs bei Relationen siehe Hans-Rudolf Metz: Relationen, Wege, Hüllen, FH Gießen-Friedberg, Diskrete Mathematik (Informatik), SS 2010 - Skript 16, 2. Juni 2010 (abgerufen am 1. Mai 2018). Im finiten Fall kann man die Relation als einen gerichteten Graphen auffassen: im graphentheoretischen Sinn handelt es sich um einen gerichteten Weg (ohne Kantengewichte).