Volume 1 / Part 4 — SECTION C. THE PRINCIPLE OF FIRST DIFFERENCES, AND THE MULTIPLICATION AND EXPONENTIATION OF RELATIONS.
Reading edition
Summary of Section C.
In the present section, we have to consider various forms of a principle which is of the utmost utility in relation-arithmetic. This principle may be called "the principle of first differences." It has been explained and used by Hausdorff in brilliant articles[15]. The results there obtained by its use give some measure of its importance in relation-arithmetic. It has, however, other uses besides those that are concerned with the multiplication and exponentiation of relation-numbers, as, for example, in the ordering of segments and stretches in a series, or of any other set of classes which are contained in the field of a given relation. In the present section, after the first two numbers, we shall be concerned with its arithmetical uses, but other uses will occur later.
The principle of first differences has various forms which, though analogous, cannot, in the general case, be reduced to one common genus. The simplest of these is the relation , by which the sub-classes of are ordered. This is defined as follows. If and are both contained in , we say that if there are terms belonging to but not to such that no terms belonging to and not to precede them; i.e. if, after taking away the terms (if any) which are common to and , there are terms left in which do not come after any of the terms left in , i.e. if . Thus the definition is It will be seen that this relation holds if . Thus it holds between any existent member of and , and between and any member of other than itself. When is a serial relation (which is the important case for all the relations in this section), is transitive and asymmetrical , but not necessarily connected, i.e. there may be two members of its field of which neither has the relation to the other. This happens whenever is not well-ordered; but when is well-ordered, is connected, and therefore generates a series.
To illustrate the order generated by in a simple case, consider a series of three terms, , , . Let us for the moment write for the relation and similarly we will write for , and so on. Then assuming , In this series, a class containing is always earlier than one not containing ; and of two classes of which both or neither contain , one containing is earlier than one not containing ; and of two classes of which both or neither contain , and both or neither contain , one containing is earlier than one not containing . Thus our relation may be generated as follows: Begin with , which is . Add before these terms what results from adding to each; then we have , which is Now add at the beginning what results from adding to each of the above four classes, and we have . Thus generally, if , Thus by adding one term to , we double the number of terms in .
Again, if and are two relations which have no common terms in their fields, we shall have while conversely Hence so that .
These propositions illustrate the connection of with multiplication.
Besides , we often require (though not in this Part) the relation which is the converse of . This relation we call , so that This begins with , and ends with .
Thus we shall have, for example, Here, if we start from , which is , the series grows by adding terms at the end: we add to each member of and put the resulting terms after and ; we then add to each of the four terms we already have, and add the resulting terms at the end; and so we can proceed indefinitely.
The relation with its field limited arranges the segments of P in ascending order of magnitude; if the class of segments is , generates what may be called the natural order among the segments (cf. *212).
A variant of is afforded by the relation (*171), which is to hold between two members , of when the first term of either which does not belong to both belongs to , i.e. the "first difference" belongs to . This relation implies , and coincides with it if is well-ordered; but when is not well-ordered, may hold between two classes which have no first point of difference, e.g. (if is "less than" among rationals) if consists of rationals between 0 and 1 (both excluded) and of rationals between 1 and 2 (both excluded). The definition of is
The relation has the interesting property that its relation-number is found by raising to the power (cf. *177). As the field of is , this theorem is the ordinal analogue of (*116·72).
A somewhat more complicated form of the relation of first differences arises when we have a series of series. Let us suppose, to begin with, that is a serial relation whose field consists of mutually exclusive serial relations.
Thus in the accompanying figure, each row represents a series, the generating relations of these series being , ... ,... But the series themselves form a series, which may be regarded as generated by a relation whose field consists of the relations , ... ,... (It might be thought more natural to take , , ... as the field of ; but this would lead to confusion in the case when two or more of the series have the same field.) Suppose we now wish to find a relation which will order the multiplicative class of the fields of , , ..., i.e. the class . In the case illustrated in the figure, in which generates a well-ordered series, and all the members of are serial, and , we might use ; this relation, with its field limited to , will then give us what we want. This relation will, in the case supposed, put a selected class before another selected class if, where they first differ, chooses an earlier term than . But if the series is not well-ordered—if it is (say) of the type (cf. *263)—there may be no first member of the field of where and differ. This will happen, for example, if consists of all the first terms, and of all the second terms. Our ordering relation can be so defined as to put before in this case also, but if it is so defined, the associative law of multiplication only holds if is well-ordered. For this reason, we define our ordering relation so that, in such a case, comes neither before nor after . Again, if is not a , a member of a selected class may occur twice, once as the representative of , and once as that of , if and have terms in common. We wish to distinguish these two occurrences. Hence we proceed as follows: If and are two selected classes of , let there be one or more members of in which the -representative precedes the -representative, and which are such that, among all earlier[16] members of , the -representative is identical with the -representative.
But a further modification is desirable in order to meet the case in which two or more of the members of have the same field. Suppose, for example, we had to deal with a series consisting of all the series that can be formed out of a given set of terms: in this case, we should have to distinguish occurrences of any given term not by the field, but by the generating relation. This requires that we should make an -selection from , not an -selection from . Hence we take two members of , say and , and we arrange them or their domains on the following principle: We put before (or before ) if there is a relation in the field of such that the -representative of , i.e. , has the relation to the -representative of , and such that, if is any earlier member of , then is identical with . That is, precedes if
The relation between and so defined has the properties required of an arithmetical product; hence we put
This relation is the ordinal analogue of . The ordinal analogue of is the corresponding relation of the domains of and , i.e. ; hence we put
In case is a , we have . But when is not a , and are in general not ordinally similar. We can, however, always make a by replacing the members , , etc. of (where ) by , etc. In this way, if occurs twice in , once as a member of , and once as a member of , the two occurrences are made to correspond to and respectively, and thus we get a new relation which is a .
If every member of has a first term, will be the first term of , and will be the first term of . If further there is a last member of , i.e. if , and if this last member has a second term, the second member of is obtained by taking this second term as the representative of , and leaving all the other representatives unchanged. In any case, if exists, the earliest successors of any member of are those obtained by only varying the representative in . Thus, if exists, those members of which have a given set of representatives in all members of form a consecutive stretch of the series, and this stretch is like . If has an immediate predecessor, the stretches obtained by varying only the representative in this predecessor are again consecutive, and form a series like the said predecessor; and so on. This makes it plain why has the properties of a product.
As in the case of cardinals, the definition of exponentiation is derived from that of multiplication. We put This is an important relation, which deserves consideration apart from the fact that it is useful in connection with exponentiation. It will be found that
This is a form of the principle of first differences which is appropriate when two relations are concerned, instead of only one as in . The principle, in this case, is as follows: Let , be any two one-many relations which relate part (or the whole) of to the whole of . That is, each of the two relations assigns a representative in to every term of , but different terms of may have the same representative. Then in travelling along the series , there is to be, sooner or later, a term whose -representative is earlier than its -representative, and terms which come earlier than in are all to have their -representatives identical with their -representatives.
The relation may be subjected to various restrictions which give important results. This subject has been treated by Hausdorff. For example, if (where ), and is of the ordinal type which Cantor calls , i.e. the type of progressions (generated by transitive relations), then if is any member of , is always either or . If we impose the condition that is to be except for a finite number of values of , the resulting series is of the type of the rationals in order of magnitude, i.e. the type called . If we impose the condition that there are to be an infinite number of values of for which , the resulting series is a continuum, i.e. it is of the ordinal type called ; in this case, the contained "rational" series consists of those 's for which there are only a finite number of 's having . If we impose no limitation, is of the type presented by the real numbers when decimals ending in 9 recurring are counted separately from the terminating decimals having the same value.
We may generalize , instead of restricting it. To begin with, we may allow our and to have only part of for their converse domain, and remove the assumption that there is a first member of for which and differ; this leads to the relation Further, we may drop the restriction to one-many relations. It will be observed that if , we have . Thus we may consider the relation This relation has for its field all relations contained in . We may, if we like, drop even this restriction, and consider This represents the most general form of the principle of first differences as applied to a couple of relations and . In ordinal arithmetic, however, is sufficiently general for the uses we wish to make of it.
The formal laws, as far as they are true, can be proved without excessive difficulty. We have which connects the two kinds of multiplication; which is one form of the associative law, of which another form is Also which is the associative law for "." We have But we do not have in general which obviously would require the commutative law for multiplication, and therefore does not hold in general in spite of the fact that its cardinal analogue does always hold.
As regards the connection with cardinals, we have and we have already had Moreover the correlators by which similarity is established in cardinals generally suffice to establish likeness in the analogous cases in relation-arithmetic. Thus we have which are all closely analogous to propositions which were proved in cardinals.
The applications of the propositions of this section are almost wholly to series, and it is convenient to imagine our relations to be serial. But the hypothesis that they are serial is not necessary to the truth of any of the propositions of the present section, and it is a remarkable fact that so many of the formal laws of ordinal arithmetic hold for relations in general.
It should be observed that is not always a series when is a series and all the relations in the field of are series. A series (cf. *204) is a relation which is (1) contained in diversity, (2) transitive, (3) connected, i.e. such that every term of the field of P has the relation P or the relation to every other term of the field. It is the third condition which may fail for , and which in fact does fail whenever is not well-ordered. Thus suppose, for the sake of simplicity, that is of the type , which we will call a regression, i.e. the converse of a progression (cf. *263); and suppose that the field of consists entirely of couples. Take a selection which chooses the first term of every odd couple, and the second term of every even couple ; and take another selection which chooses the second term of every odd couple, and the first term of every even couple. Neither of these two selections has the relation to the other, for whatever term of we choose, if is the selection which chooses the first term of , there is an earlier term of (namely the immediate predecessor of ) in which chooses the first term while chooses the second. Hence there is no such as is required for ; and a similar argument holds against . In such a case, generates a number of different series, and by suitable restrictions of the field, one of these series can be extracted. Exactly similar remarks apply to .