Successor (mathematics)
In mathematics , the concepts of descent or succession and counting are formalized and generalized through the terms successor and predecessor .
Successors and predecessors in counting and in order
When counting, the successor of an integer is intuitively the next larger number: For example, 2 is the successor to 1, 3 is the successor to 2, etc. When counting down, you get from 9 to its predecessor 8, etc. This basically naive discovery, the children always To understand again in the game, one can formalize to a mathematical characterization of the natural numbers , which was developed by Giuseppe Peano and in his honor is called the Peano axiom system .
When counting up and down, you find that the meaning of the numerals is not important, only their order. This finding allows a generalization of the counter neighbors predecessors and successors to graphs and ordered sets:
Definitions
Be a strictly ordered set , . Then is called
- Predecessor or lower neighbor of , if and not a major element than exists with this property
- Successor or upper neighbor of , if is and no smaller element than with this property exists
- formal: if ,
For a strict total order , this definition also ensures that predecessors and successors (if any) are clearly identified. The function that assigns each element to its uniquely determined successor is called the successor function. In general, however, an element can have several, not comparable, predecessors and successors. Graph theory pursues this more general concept . It comes close to the pre-mathematical concept of descent.
In order theory, one defines :
- is ancestor of if is and every other element with this property is smaller
- formal: if .
- is the successor of if is and every other element with this property is greater
- formal: if ,
This means that the predecessor and successor, if any, are unambiguous even in not totally ordered sets. This rather depicts the counting process.
example
The graph shown illustrates the divisor relation in the set of divisors of the number 12. The abstract relation 3 <6 is represented here by arrows and has the meaning 3 divides 6, 1 divides 4 etc. The order is not total, because there are elements which cannot be compared with each other, for example 2 is neither a divisor of 3 nor vice versa. In the sense of the second, order-theoretical definition, the 2 has no successors but a predecessor, in the sense of the first, more general definition, the 2 has a predecessor and two successors.
Applications
- In a well-ordered set ( ordinal number ) each element has a unique successor, unless it is the maximum of the well-ordered set. Elements without a predecessor are called Limes elements or limit ordinal numbers.
- The existence of predecessors and successors in ordered sets can also be examined using topological means. See also order topology .
- The concept of predecessors and successors in directed graphs is explained in the article neighborhood (graph theory) .
generalization
The above definition can easily be extended to strict partial orders. In the general case, especially in the case of a (weak) total or partial order , one still has to demand that the predecessor or successor is a different element (which is always fulfilled in the case of a strict order).
For with
- and
- ,
is called a (immediate) predecessor of ; a (immediate) successor is defined analogously.
Many authors use the terms predecessor and successor in a more general way, namely without the second condition. In this alternative way of speaking, the terms defined here are called immediate ( direct ) predecessors or successors.
Individual evidence
- ↑ Johannes Köbler: Introduction to Theoretical Computer Science , Humboldt University Berlin, Institute for Computer Science, WS2013 / 14, p. 79
- ^ Wiebke Petersen: Mathematical Foundations of Computational Linguistics - Ordnungsrelationen , 4th set of slides, Heinrich Heine University Düsseldorf, Institute of Language and Information, PDF: WS 2011/12 p. 93 WS 2013/14 p. 90 , accessed on April 21 2018.
Footnotes
- ↑ This procedure determines a new relation ( immediate , synonymous direct ) predecessor for a given relation .
- ↑ Such a predecessor or successor in the broader sense does not necessarily have to go through one path , i.e. H. a finite sequence of direct (i.e. immediate) predecessors (quasi indirectly or indirectly) can be reached, e.g. B. 0 to 10 , or - as opposed to , where there is such a finite way. For the concept of path in relations, see Hans-Rudolf Metz: Relationen ,wege, Hüllen , FH Gießen-Friedberg, Diskrete Mathematik (Informatik), SS 2010 - Script 16, June 2, 2010 (accessed on May 1, 2018). In the finite case, the relation can be understood as a directed graph: in the graph-theoretical sense, it is a directed path (without edge weights).