[page 77]
The definition of cardinal numbers which we gave in Chapter II. was applied in Chapter III. to finite numbers, i.e. to the ordinary natural numbers. To these we gave the name “inductive numbers,” because we found that they are to be defined as numbers which obey mathematical induction starting from 0. But we have not yet considered collections which do not have an inductive number of terms, nor have we inquired whether such collections can be said to have a number at all. This is an ancient problem, which has been solved in our own day, chiefly by Georg Cantor. In the present chapter we shall attempt to explain the theory of transfinite or infinite cardinal numbers as it results from a combination of his discoveries with those of Frege on the logical theory of numbers.
It cannot be said to be certain that there are in fact any infinite collections in the world. The assumption that there are is what we call the “axiom of infinity.” Although various ways suggest themselves by which we might hope to prove this axiom, there is reason to fear that they are all fallacious, and that there is no conclusive logical reason for believing it to be true. At the same time, there is certainly no logical reason against infinite collections, and we are therefore justified, in logic, in investigating the hypothesis that there are such collections. The practical form of this hypothesis, for our present purposes, is the assumption that, if n is any inductive number, n is not equal to n+1. Various subtleties arise in identifying this form of our assumption with [page 78] the form that asserts the existence of infinite collections; but we will leave these out of account until, in a later chapter, we come to consider the axiom of infinity on its own account. For the present we shall merely assume that, if n is an inductive number, n is not equal to n+1. This is involved in Peano’s assumption that no two inductive numbers have the same successor; for, if n=n+1, then n−1 and n have the same successor, namely n. Thus we are assuming nothing that was not involved in Peano’s primitive propositions.
Let us now consider the collection of the inductive numbers themselves. This is a perfectly well-defined class. In the first place, a cardinal number is a set of classes which are all similar to each other and are not similar to anything except each other. We then define as the “inductive numbers” those among cardinals which belong to the posterity of 0 with respect to the relation of n to n+1, i.e. those which possess every property possessed by 0 and by the successors of possessors, meaning by the “successor” of n the number n+1. Thus the class of “inductive numbers” is perfectly definite. By our general definition of cardinal numbers, the number of terms in the class of inductive numbers is to be defined as “all those classes that are similar to the class of inductive numbers”—i.e. this set of classes is the number of the inductive numbers according to our definitions.
Now it is easy to see that this number is not one of the inductive numbers. If n is any inductive number, the number of numbers from 0 to n (both included) is n+1; therefore the total number of inductive numbers is greater than n, no matter which of the inductive numbers n may be. If we arrange the inductive numbers in a series in order of magnitude, this series has no last term; but if n is an inductive number, every series whose field has n terms has a last term, as it is easy to prove. Such differences might be multiplied ad lib. Thus the number of inductive numbers is a new number, different from all of them, not possessing all inductive properties. It may happen that 0 has a certain [page 79] property, and that if n has it so has n+1, and yet that this new number does not have it. The difficulties that so long delayed the theory of infinite numbers were largely due to the fact that some, at least, of the inductive properties were wrongly judged to be such as must belong to all numbers; indeed it was thought that they could not be denied without contradiction. The first step in understanding infinite numbers consists in realising the mistakenness of this view.
The most noteworthy and astonishing difference between an inductive number and this new number is that this new number is unchanged by adding 1 or subtracting 1 or doubling or halving or any of a number of other operations which we think of as necessarily making a number larger or smaller. The fact of being not altered by the addition of 1 is used by Cantor for the definition of what he calls “transfinite” cardinal numbers; but for various reasons, some of which will appear as we proceed, it is better to define an infinite cardinal number as one which does not possess all inductive properties, i.e. simply as one which is not an inductive number. Nevertheless, the property of being unchanged by the addition of 1 is a very important one, and we must dwell on it for a time.
To say that a class has a number which is not altered by the addition of 1 is the same thing as to say that, if we take a term x which does not belong to the class, we can find a one-one relation whose domain is the class and whose converse domain is obtained by adding x to the class. For in that case, the class is similar to the sum of itself and the term x, i.e. to a class having one extra term; so that it has the same number as a class with one extra term, so that if n is this number, n=n+1. In this case, we shall also have n=n−1, i.e. there will be one-one relations whose domains consist of the whole class and whose converse domains consist of just one term short of the whole class. It can be shown that the cases in which this happens are the same as the apparently more general cases in which some part (short of the whole) can be put into one-one relation with the whole. When this can be done, [page 80] the correlator by which it is done may be said to “reflect” the whole class into a part of itself; for this reason, such classes will be called “reflexive.” Thus:
A “reflexive” class is one which is similar to a proper part of itself. (A “proper part” is a part short of the whole.)
A “reflexive” cardinal number is the cardinal number of a reflexive class.
We have now to consider this property of reflexiveness.
One of the most striking instances of a “reflexion” is Royce’s illustration of the map: he imagines it decided to make a map of England upon a part of the surface of England. A map, if it is accurate, has a perfect one-one correspondence with its original; thus our map, which is part, is in one-one relation with the whole, and must contain the same number of points as the whole, which must therefore be a reflexive number. Royce is interested in the fact that the map, if it is correct, must contain a map of the map, which must in turn contain a map of the map of the map, and so on ad infinitum. This point is interesting, but need not occupy us at this moment. In fact, we shall do well to pass from picturesque illustrations to such as are more completely definite, and for this purpose we cannot do better than consider the number-series itself.
The relation of n to n+1, confined to inductive numbers, is one-one, has the whole of the inductive numbers for its domain, and all except 0 for its converse domain. Thus the whole class of inductive numbers is similar to what the same class becomes when we omit 0. Consequently it is a “reflexive” class according to the definition, and the number of its terms is a “reflexive” number. Again, the relation of n to 2n, confined to inductive numbers, is one-one, has the whole of the inductive numbers for its domain, and the even inductive numbers alone for its converse domain. Hence the total number of inductive numbers is the same as the number of even inductive numbers. This property was used by Leibniz (and many others) as a proof that infinite numbers are impossible; it was thought self-contradictory that [page 81] “the part should be equal to the whole.” But this is one of those phrases that depend for their plausibility upon an unperceived vagueness: the word “equal” has many meanings, but if it is taken to mean what we have called “similar,” there is no contradiction, since an infinite collection can perfectly well have parts similar to itself. Those who regard this as impossible have, unconsciously as a rule, attributed to numbers in general properties which can only be proved by mathematical induction, and which only their familiarity makes us regard, mistakenly, as true beyond the region of the finite.
Whenever we can “reflect” a class into a part of itself, the same relation will necessarily reflect that part into a smaller part, and so on ad infinitum. For example, we can reflect, as we have just seen, all the inductive numbers into the even numbers; we can, by the same relation (that of n to 2n) reflect the even numbers into the multiples of 4, these into the multiples of 8, and so on. This is an abstract analogue to Royce’s problem of the map. The even numbers are a “map” of all the inductive numbers; the multiples of 4 are a map of the map; the multiples of 8 are a map of the map of the map; and so on. If we had applied the same process to the relation of n to n+1, our “map” would have consisted of all the inductive numbers except 0; the map of the map would have consisted of all from 2 onward, the map of the map of the map of all from 3 onward; and so on. The chief use of such illustrations is in order to become familiar with the idea of reflexive classes, so that apparently paradoxical arithmetical propositions can be readily translated into the language of reflexions and classes, in which the air of paradox is much less.
It will be useful to give a definition of the number which is that of the inductive cardinals. For this purpose we will first define the kind of series exemplified by the inductive cardinals in order of magnitude. The kind of series which is called a “progression” has already been considered in Chapter I. It is a series which can be generated by a relation of consecutiveness: [page 82] every member of the series is to have a successor, but there is to be just one which has no predecessor, and every member of the series is to be in the posterity of this term with respect to the relation “immediate predecessor.” These characteristics may be summed up in the following definition:—1
A “progression” is a one-one relation such that there is just one term belonging to the domain but not to the converse domain, and the domain is identical with the posterity of this one term.
It is easy to see that a progression, so defined, satisfies Peano’s five axioms. The term belonging to the domain but not to the converse domain will be what he calls “0”; the term to which a term has the one-one relation will be the “successor” of the term; and the domain of the one-one relation will be what he calls “number.” Taking his five axioms in turn, we have the following translations:—
(1) “0 is a number” becomes: “The member of the domain which is not a member of the converse domain is a member of the domain.” This is equivalent to the existence of such a member, which is given in our definition. We will call this member “the first term.”
(2) “The successor of any number is a number” becomes: “The term to which a given member of the domain has the relation in question is again a member of the domain.” This is proved as follows: By the definition, every member of the domain is a member of the posterity of the first term; hence the successor of a member of the domain must be a member of the posterity of the first term (because the posterity of a term always contains its own successors, by the general definition of posterity), and therefore a member of the domain, because by the definition the posterity of the first term is the same as the domain.
(3) “No two numbers have the same successor.” This is only to say that the relation is one-many, which it is by definition (being one-one).
[page 83]
(4) “0 is not the successor of any number” becomes: “The first term is not a member of the converse domain,” which is again an immediate result of the definition.
(5) This is mathematical induction, and becomes: “Every member of the domain belongs to the posterity of the first term,” which was part of our definition.
Thus progressions as we have defined them have the five formal properties from which Peano deduces arithmetic. It is easy to show that two progressions are “similar” in the sense defined for similarity of relations in Chapter VI. We can, of course, derive a relation which is serial from the one-one relation by which we define a progression: the method used is that explained in Chapter IV., and the relation is that of a term to a member of its proper posterity with respect to the original one-one relation.
Two transitive asymmetrical relations which generate progressions are similar, for the same reasons for which the corresponding one-one relations are similar. The class of all such transitive generators of progressions is a “serial number” in the sense of Chapter VI.; it is in fact the smallest of infinite serial numbers, the number to which Cantor has given the name ω, by which he has made it famous.
But we are concerned, for the moment, with cardinal numbers. Since two progressions are similar relations, it follows that their domains (or their fields, which are the same as their domains) are similar classes. The domains of progressions form a cardinal number, since every class which is similar to the domain of a progression is easily shown to be itself the domain of a progression. This cardinal number is the smallest of the infinite cardinal numbers; it is the one to which Cantor has appropriated the Hebrew Aleph with the suffix 0, to distinguish it from larger infinite cardinals, which have other suffixes. Thus the name of the smallest of infinite cardinals is ℵ0.
To say that a class has ℵ0 terms is the same thing as to say that it is a member of ℵ0, and this is the same thing as to say [page 84] that the members of the class can be arranged in a progression. It is obvious that any progression remains a progression if we omit a finite number of terms from it, or every other term, or all except every tenth term or every hundredth term. These methods of thinning out a progression do not make it cease to be a progression, and therefore do not diminish the number of its terms, which remains ℵ0. In fact, any selection from a progression is a progression if it has no last term, however sparsely it may be distributed. Take (say) inductive numbers of the form nn, or nnn. Such numbers grow very rare in the higher parts of the number series, and yet there are just as many of them as there are inductive numbers altogether, namely, ℵ0.
Conversely, we can add terms to the inductive numbers without increasing their number. Take, for example, ratios. One might be inclined to think that there must be many more ratios than integers, since ratios whose denominator is 1 correspond to the integers, and seem to be only an infinitesimal proportion of ratios. But in actual fact the number of ratios (or fractions) is exactly the same as the number of inductive numbers, namely, ℵ0. This is easily seen by arranging ratios in a series on the following plan: If the sum of numerator and denominator in one is less than in the other, put the one before the other; if the sum is equal in the two, put first the one with the smaller numerator. This gives us the series
1, 1/2, 2, 1/3, 3, 1/4, 2/3, 3/2, 4, 1/5, …
This series is a progression, and all ratios occur in it sooner or later. Hence we can arrange all ratios in a progression, and their number is therefore ℵ0.
It is not the case, however, that all infinite collections have ℵ0 terms. The number of real numbers, for example, is greater than ℵ0; it is, in fact, 2ℵ0, and it is not hard to prove that 2n is greater than n even when n is infinite. The easiest way of proving this is to prove, first, that if a class has n members, it contains 2n sub-classes—in other words, that there are 2n ways [page 85] of selecting some of its members (including the extreme cases where we select all or none); and secondly, that the number of sub-classes contained in a class is always greater than the number of members of the class. Of these two propositions, the first is familiar in the case of finite numbers, and is not hard to extend to infinite numbers. The proof of the second is so simple and so instructive that we shall give it:
In the first place, it is clear that the number of sub-classes of a given class (say α) is at least as great as the number of members, since each member constitutes a sub-class, and we thus have a correlation of all the members with some of the sub-classes. Hence it follows that, if the number of sub-classes is not equal to the number of members, it must be greater. Now it is easy to prove that the number is not equal, by showing that, given any one-one relation whose domain is the members and whose converse domain is contained among the set of sub-classes, there must be at least one sub-class not belonging to the converse domain. The proof is as follows:2 When a one-one correlation R is established between all the members of α and some of the sub-classes, it may happen that a given member x is correlated with a sub-class of which it is a member; or, again, it may happen that x is correlated with a sub-class of which it is not a member. Let us form the whole class, β say, of those members x which are correlated with sub-classes of which they are not members. This is a sub-class of α, and it is not correlated with any member of α. For, taking first the members of β, each of them is (by the definition of β) correlated with some sub-class of which it is not a member, and is therefore not correlated with β. Taking next the terms which are not members of β, each of them (by the definition of β) is correlated with some sub-class of which it is a member, and therefore again is not correlated with β. Thus no member of α is correlated with β. Since R was any one-one correlation of all members [page 86] with some sub-classes, it follows that there is no correlation of all members with all sub-classes. It does not matter to the proof if β has no members: all that happens in that case is that the sub-class which is shown to be omitted is the null-class. Hence in any case the number of sub-classes is not equal to the number of members, and therefore, by what was said earlier, it is greater. Combining this with the proposition that, if n is the number of members, 2n is the number of sub-classes, we have the theorem that 2n is always greater than n, even when n is infinite.
It follows from this proposition that there is no maximum to the infinite cardinal numbers. However great an infinite number n may be, 2n will be still greater. The arithmetic of infinite numbers is somewhat surprising until one becomes accustomed to it. We have, for example,
ℵ0+1 | =ℵ0, |
ℵ0+n | =ℵ0, where n is any inductive number, |
ℵ02 | =ℵ0. |
(This follows from the case of the ratios, for, since a ratio is determined by a pair of inductive numbers, it is easy to see that the number of ratios is the square of the number of inductive numbers, i.e. it is ℵ02; but we saw that it is also ℵ0.)
| ℵ0n | =ℵ0, where n is any inductive number. |
(This follows from | ℵ02 | =ℵ0 by induction; for if ℵ0n=ℵ0, |
then | ℵ0n+1 | =ℵ02=ℵ0.) |
But | 2ℵ0 | > ℵ0. |
In fact, as we shall see later, 2ℵ0 is a very important number, namely, the number of terms in a series which has “continuity” in the sense in which this word is used by Cantor. Assuming space and time to be continuous in this sense (as we commonly do in analytical geometry and kinematics), this will be the number of points in space or of instants in time; it will also be the number of points in any finite portion of space, whether [page 87] line, area, or volume. After ℵ0, 2ℵ0 is the most important and interesting of infinite cardinal numbers.
Although addition and multiplication are always possible with infinite cardinals, subtraction and division no longer give definite results, and cannot therefore be employed as they are employed in elementary arithmetic. Take subtraction to begin with: so long as the number subtracted is finite, all goes well; if the other number is reflexive, it remains unchanged. Thus ℵ0−n=ℵ0, if n is finite; so far, subtraction gives a perfectly definite result. But it is otherwise when we subtract ℵ0 from itself; we may then get any result, from 0 up to ℵ0. This is easily seen by examples. From the inductive numbers, take away the following collections of ℵ0 terms:—
(1) All the inductive numbers—remainder, zero.
(2) All the inductive numbers from n onwards—remainder, the numbers from 0 to n−1, numbering n terms in all.
(3) All the odd numbers—remainder, all the even numbers, numbering ℵ0 terms.
All these are different ways of subtracting ℵ0 from ℵ0, and all give different results.
As regards division, very similar results follow from the fact that ℵ0 is unchanged when multiplied by 2 or 3 or any finite number n or by ℵ0. It follows that ℵ0 divided by ℵ0 may have any value from 1 up to ℵ0.
From the ambiguity of subtraction and division it results that negative numbers and ratios cannot be extended to infinite numbers. Addition, multiplication, and exponentiation proceed quite satisfactorily, but the inverse operations—subtraction, division, and extraction of roots—are ambiguous, and the notions that depend upon them fail when infinite numbers are concerned.
The characteristic by which we defined finitude was mathematical induction, i.e. we defined a number as finite when it obeys mathematical induction starting from 0, and a class as finite when its number is finite. This definition yields the sort of result that a definition ought to yield, namely, that the finite [page 88] numbers are those that occur in the ordinary number-series 0, 1, 2, 3, … But in the present chapter, the infinite numbers we have discussed have not merely been non-inductive: they have also been reflexive. Cantor used reflexiveness as the definition of the infinite, and believes that it is equivalent to non-inductiveness; that is to say, he believes that every class and every cardinal is either inductive or reflexive. This may be true, and may very possibly be capable of proof; but the proofs hitherto offered by Cantor and others (including the present author in former days) are fallacious, for reasons which will be explained when we come to consider the “multiplicative axiom.” At present, it is not known whether there are classes and cardinals which are neither reflexive nor inductive. If n were such a cardinal, we should not have n=n+1, but n would not be one of the “natural numbers,” and would be lacking in some of the inductive properties. All known infinite classes and cardinals are reflexive; but for the present it is well to preserve an open mind as to whether there are instances, hitherto unknown, of classes and cardinals which are neither reflexive nor inductive. Meanwhile, we adopt the following definitions:—
A finite class or cardinal is one which is inductive.
An infinite class or cardinal is one which is not inductive. All reflexive classes and cardinals are infinite; but it is not known at present whether all infinite classes and cardinals are reflexive. We shall return to this subject in Chapter XII.
[Chapter VIII notes]
1. Cf. Principia Mathematica, vol. ii. *123.
2. This proof is taken from Cantor, with some simplifications: see Jahresbericht der Deutschen Mathematiker-Vereinigung, i. (1892), p. 77.