Principia mathematica, vol. 1 (of 3)

The subjects to be treated in this section are certain general ideas of which a particular instance is afforded by mathematical induction. Mathematical induction is, in fact, the application to the number-series of a conception which is applicable to all relations, and is often very important. The conception in question is that which we shall call the ancestral relation with respect to a given relation. If is the given relation, we denote the corresponding ancestral relation by ""; the name is chosen because, if is the relation of parent and child, will be the relation of ancestor and descendant—where, for convenience of language, we include among his own ancestors if is a parent or a child of anything.

It would commonly be said that has to the relation of ancestor to descendant if there are a certain number of intermediate people , , , ... such that in the series , , , , ... each term has to the next the relation of parent and child. But this is not an adequate definition, because the dots in represent an unanalysed idea. We may then try to amend this definition by saying that there is a finite class of intermediate terms such that one member () of is a child of , one () is a parent of , every member of except is a child of one (and only one) member of , and every member of except is a parent of one (and only one) member of . This definition is open to several objections. In the first place, it is very complicated; in the second place, there will, in regard to a general relation, be difficulty in securing the uniqueness of the member of which is to be a parent (or a child) of a given member of ; in the third place (and this is the really fatal objection) the proposed definition states that is to be a finite class, and we shall find that finitude, in the relevant sense, is only defined by means of the very conception of the ancestral relation which we are here engaged in defining. In fact, if denotes the relation of to , where is a cardinal number, then a finite cardinal (in the sense we require) is one to which 0 has the relation , i.e. one of which 0 is an ancestor with respect to the relation Hence we must not use the notion of finitude in defining the ancestral relation. In fact, the ancestral relation is defined as follows.

Let us call a hereditary class with respect to if , i.e. if successors of 's (with respect to ) are 's. Thus, for example, if is the class of persons named Smith, is hereditary with respect to the relation of father to son. If is the Peerage, is hereditary with respect to the relation of father to surviving eldest son. If is numbers greater than 100, is hereditary with respect to the relation of to ; and so on. If now is an ancestor of , and is a hereditary class to which belongs, then also belongs to this class. Conversely, if belongs to every hereditary class to which belongs, then (in the sense in which a is one of his own ancestors if is anybody's parent or child) must be an ancestor of . For to have for one's ancestor is a hereditary property which belongs to , and therefore, by hypothesis, to . Hence is an ancestor of when, and only when, belongs to the field of the relation in question and belongs to every hereditary class to which belongs. This property may be used to define the ancestral relation; i.e. since we have we put We then have Here may be called "the descendants of ." It is the class of terms of which is an ancestor.

To make plain the relation of the above to mathematical induction, put 0 for , and for . Then, since 1=0+1, we have . Again Thus we find Thus if is a descendant of 0, belongs to every class to which 0 belongs and to which belongs whenever belongs. Hence mathematical induction, starting from 0, will prove properties of . In elementary mathematics it is customary to speak as if this held of all integers, i.e. as if (as above defined) included all integers; but in fact only finite integers (in one of the two senses which the word finite may have) belong to the class , and they belong to it by definition, being defined as the class i.e. as in the above sense. To infinite numbers, inductive proofs of this kind starting from 0 cannot be applied.

The study of will occupy *90. The relation holds between and if or or or etc. The study of this "etc." occupies *91, "on the powers of a relation." We may, for many technical purposes, regard as the 0th power of ; the other powers are , , etc. If is a power of , so is . Now is , according to the definition in *38. Thus if we have must be a power of , because the class of powers of is a value of which satisfies the hypothesis Conversely, if is a power of , then is reached by repetitions of the process of turning into , starting this process with . Hence if is a power of , we shall have

Consequently, if we denote the class of powers of by , we have We might use this as the definition of ; but we can get a somewhat simpler form. For the above is shown, without much difficulty, to be equivalent to that is, belongs to the ancestry of with respect to , in other words, is reached from by proceeding along the series which is the same as the series The relation is important on its own account. We put and then we put

We often want to include among the powers of ; the class consisting of together with we call . The definition is whence we easily prove The relation of being related by some power of (other than ) is a very important one. We denote it by , and put Thus when , we have one of , , , etc. It is easy to prove that In a series in which every term (except the first, if there is a first) has an immediate predecessor, and every term (except the last, if there is a last) has an immediate successor, if is the relation of a term to its immediate successor, is the relation of any earlier term to any later one.

The next number (*93) analyses the field of a relation into successive generations; e.g. if the relation is that of parent and child, the first generation will consist of Adam and Eve, the second of their children, the third of their grandchildren, and so on, taking always the longest route from Adam and Eve when there have been intermarriages between generations. That is, taking any relation , the first generation is , the second is , the third is , and so on. Generally, if is a power of (including ), the corresponding generation is

In order to express this more conveniently, we introduce a new symbol , which is required also on other grounds, especially in series. "" may be read "minimum with respect to ." We regard "" as " precedes "; then in a class , the "minima of " will be those members of which belong to and are not preceded by any other members of , i.e. . We put therefore Hence we have i.e. consists of those members of which are not preceded by any other members of . (If has a single first term, this term is .) Thus we have, when is a power of , Thus , where is any power of (including ) is the generation of corresponding to ; thus the whole class of generations is . Hence we put where "" stands for "generation."

The notation "" will not be much used until we come to series, but then it will be constantly used. At present, we shall only give such properties of as are necessary for our immediate purposes, but in Part V (on series) we shall devote a number (*205) to its properties.

In this number we also introduce the notation "" for "." "" may be read " begins ." If there is a single beginning of , this is ; otherwise the class of beginnings is , which =. Thus if is the relation of father and son, = Adam; if is the relation of parent and child, = Adam and Eve. will be the end of , if there is one; generally, will be the class of ends, i.e. . The first generation of is . If , any generation of is , where is the corresponding power of .

The field of a relation consists, in general, not only of the generations of , but also of another part, the part in which, however far we go backwards, we never reach a beginning. This part is . The two parts and are mutually exclusive, and together exhaust .

The two next numbers, *94 and *95, are hardly ever relevant in subsequent propositions, and may therefore be omitted by any reader who is not interested in their subject-matter. *94 deals with powers of relative products. It is only used in the following number (*95), on "equi-factor relations." The matter to be dealt with in this number may be explained as follows. In dealing with correlations and similar topics, we often wish to consider the series of relations Now we have not yet at our command a definition of , where is any finite number; thus we cannot define a general term of this series as . We need therefore a different method of definition. We have and so on. Thus if is any power of (, a general term of our series is . For convenience of notation, we put Then our series consists of (. The sum of all relations of this class is considered in this number.

*96, on the posterity of a term, is concerned with the properties of , chiefly when . In this case, in general, consists of two parts, first an open series and then a cyclic series. Either of these may vanish, or may reduce to a single term. If we call the two parts and , the whole of precedes the whole of , and , . Thus if either or vanishes, . If vanishes, the series never returns into itself, that is, . If exists, there is a definite power of , say , such that . If and both exist, there is one term, namely the successor of the last term of , which has just two immediate predecessors, one in and one in ; every other term of has only one immediate predecessor in . Thus is shaped like a , with at the tip of the tail.

*97 deals with the analysis of the field of a relation into families. Taking any member of , the family of with respect to is , which we write . Thus the class of families is . Those families which contain a member of are . If we regard as arranged in a rectangle, in which the generations are the successive rows, then will be the columns. Thus the relation of to may be regarded as a generalized form of the relation of rows and columns. Under a suitable hypothesis, each row is a selection from the columns, and each column a selection from the rows. This is expressed in the following proposition: whence we derive existence-theorems for selections in the cases concerned.

The importance of the ideas dealt with in the present section is very great. These ideas dominate the treatment of finite and infinite, the theory of progressions and , and the transition from series generated by one-one or many-one relations of consecutive terms to series generated by transitive relations of before and after. Wherever, in short, mathematical induction is used the ideas treated in this section are required. The portions of our subsequent work in which this section is most referred to are the two sections on finite and infinite cardinals and ordinals (Part III, Section C and Part V, Section E). In the general theory of cardinals, i.e. in Part III, Sections A and B, before the distinction of finite and infinite has been introduced, the present section will be seldom if ever referred to[65].