Mathematical Induction

by Bertrand Russel

The series of natural numbers, can all be defined if we know what we mean by the three terms "0," "number", and "successor." But we may go a step farther: we can define all the natural numbers if we know what we mean by "0" and "successor." It will help us to understand the difference between finite and infinite to see how this can be done, and why the method by which it is done cannot be extended beyond the finite. We will not yet consider how "0" and "successor" are to be defined: we will for the moment assume that we know what these terms mean, and show how thence all other natural numbers can be obtained.

It is easy to see that we can reach any assigned number, say 30,000. We first define "1" as "the successor of 0," then we define "2" as "the successor of 1," and so on. In the case of an assigned number, such as 30,000, the proof that we can reach it by proceeding step by step in this fashion may be made, if we have the patience, by actual experiment: we can go on until we actually arrive at 30,000. But although the method of experiment is available for each particular natural number, it is not available for proving the general proposition that all such numbers can be reached in this way, i.e. by proceeding from 0 step by step from each number to its successor. Is there any other way by which this can be proved?

Let us consider the question the other way around. What are the numbers that can be reached, given the terms "0" and "successor"? Is there any way by which we can define the whole class of such numbers? We reach 1, as the successor of 0; 2, as the successor of 1; 3, as the successor of 2; and so on. It is this "and so on" that we wish to replace by something less vague and indefinite. We might be tempted to say that "and so on" means that the process of proceeding to the successor may be repeated any finite number of times; but the problem upon which we are engaged is the problem of defining "finite number," and therefore we must not use this notion in our definition. Our definition must not assume that we know what a finite number is.

The key to our problem lies in mathematical induction. It will be remembered that this was the fifth of the five primitive propositions which we laid down about the natural numbers. It stated that any property which belongs to 0, and to the successor of any number which has the property, belongs to all the natural numbers. This was then presented as a principle, but we shall now adopt it as a definition. It is not difficult to see that the terms obeying it are the same as the numbers that can be reached from 0 by successive steps from next to next, but as the point is important we will set forth the matter in some detail.

We shall do well to begin with some dehnitions, which will be useful in other connections also.

A property is said to be "hereditary" in the natural-number series if, whenever it belongs to a number n, it also belongs to n + 1, the successor of n. Similarly a class is said to be "hereditary" if, whenever n is a member of the class, so is n + 1. It is easy to see, though we are not yet supposed to know, that to say a property is hereditary is equivalent to saying that it belongs to all the natural numbers not less than some one of them, e.g. it must belong to all that are not less than 100, or all that are not less than 1000, or it may be that it belongs to all that are not less than 0, i.e. to all without exception.

A property is said to be "inductive" when it is a hereditary property which belongs to 0. Similarly a class is "inductive" when it is a hereditary class of which 0 is a member.

Given a hereditary class of which 0 is a member, it follows that 1 is a member of it, because a hereditary class contains the successors of its members, and 1 is the successor of 0. Similarly, given a hereditary class of which 1 is a member, it follows that 2 is a member of it; and so on. Thus we can prove by a step-by-step procedure that any assigned natural number, say 30,000, is a member of every inductive class.

We will define the "posterity" of a given natural number with respect to the relation "immediate predecessor" (which is the converse of "successor") as all those terms that belong to every hereditary class to which the given number belongs. It is again easy to see that the posterity of a natural number consists of itself and all greater natural numbers; but this also we do not yet officially know.

By the above definitions, the posterity of 0 will consist of those terms which belong to every inductive class.

It is now not difficult to make it obvious that the posterity of 0 is the same set as those terms that can be reached from 0 by successive steps from next to next. For, in the li.rst place, 0 belongs to both these sets (in the sense in which we have defined our terms) ; in the second place, if n belongs to both sets, So does n + 1. It is to be observed that we are dealing here with the kind of matter that does not admit of precise proof, namely, the comparison of a relatively vague idea with a relatively precise one. The notion of "those terms that can be reached from 0 by successive steps from next to next" is vague, though it seems as if it conveyed a dell&e meaning; on the other hand, "the posterity of 0" is precise and explicit just where the other idea is hazy. It may be taken as giving what we meant to mean when we spoke of the terms that can be reached from 0 by successive steps.

We now lay down the following definition:-
    The "natural numbers" are the posterity of 0 with respect to the relation "immediate predecessor" (which is the converse of "successor").

We have thus arrived at a definition of one of Peano’s three primitive ideas in terms of the other two. As a result of this definition, two of his primitive propositions-namely, the one asserting that 0 is a number and the one asserting mathematical induction-become unnecessary, since they result from the definition. The one asserting that the successor of a natural number is a natural number is only needed in the weakened form "every natural number has a successor."

We can, of course, easily define "0" and "successor" by means of the definition of number in general. The number 0 is the number of terms in a class which has no members, i.e. in the class which is called the "null-class." By the general detlnition of number, the number of terms in the null-class is the set of all classes similar to the null-class, i.e. (as is easily proved) the set consisting of the null-class all alone, i.e. the class whose only member is the null-class. (This is not identical with the null-class: it has one member, namely, the null-class, whereas the null-class itself has no members. A class which has one member is never identical with that one member, as we shall explain when we come to the theory of classes.) Thus we have the following purely logical detition:- 0 is the class whose only member is the null-class.

It remains to define "successor." Given any number n, let α be a class which has n members, and let x be a term which is not a member of &aplha;. Then the class consisting of α with x added on will have n + 1 members. Thus we have the following detiition:-
    The successor of the number of terms in the class α is the number of terms in the class consisting of α together with x,where x is any term not belonging to the class.

Certain niceties are required to make this definition perfect, but they need not concern us. It will be remembered that we have already given a logical detition of the number of terms in a class, namely, we defined it as the set of all classes that are similar to the given class.

We have thus reduced Peano’s three primitive ideas to ideas of logic: we have given definitions of them which make them definite, no longer capable of an insnity of different meanings, as they were when they were only determinate to the extent of obeying Peano’s five axioms. We have removed them from the fundamental apparatus of terms that must be merely apprehended, and have thus increased the deductive articulation of mathematics.

As regards the five primitive propositions, we have already succeeded in making two of them demonstrable by our delition of "natural number." How stands it with the remaining three? It is very easy to prove that 0 is not the successor of any number, and that the successor of any number is a number. But there is a diaculty about the remaining primitive proposition, namely, "no two numbers have the same successor." The difficulty does not arise unless the total number of individuals in the universe is finite; for given two numbers m and n, neither of which is the total number of individuals in the universe, it is easy to prove that we cannot have m + 1 = n + 1 unless we have m = n. But let us suppose that the total number of individuals in the universe were (say) 10; then there would be no class of 11 individuals, and the number 11 would be the null-class. So would the number 12. Thus we should have 11 = 12; therefore the successor of 10 would be the same as the successor of 11, although 10 would not be the same as 11. Thus we should have two merent numbers with the same successor. This failure of the third axiom cannot arise, however, if the number of individuals in the world is not finite. We shall return to this topic at a later stage.

Assuming that the number of individuals in the universe is not tite, we have now succeeded not only in defining Peano’s three primitive ideas, but in seeing how to prove his five primitive propositions, by means of primitive ideas and propositions belonging to logic. It follows that all pure mathematics, in so far as it is deducible from the theory of the natural numbers, is only a prolongation of logic. The extension of this result to those modern branches of mathematics which are not deducible from the theory of the natural numbers offers no difficulty of principle, as we have shown elsewhere.

The process of mathematical induction, by means of which we detlned the natural numbers, is capable of generalisation. We defined the natural numbers as the "posterity" of 0 with respect to the relation of a number to its immediate successor. If we call this relation N, any number m will have this relation to m + 1. A property is "hereditary with respect to N," or simply "N-hereditary," if, whenever the property belongs to a number m, it also belongs to m + 1, i.e. to the number to which m has the relation N. And a number n will be said to belong to the "posterity" of m with respect to the relation N if n has every N-hereditary property belonging to n. These definitions can all be applied to any other relation just as well as to N.

Thus if R is any relation whatever, we can lay down the following definitions:

A property is called "R-hereditary" when, if it belongs to a term x, and x has the relation R to y, then it belongs to y.

A class is R-hereditary when its defining property is R-hereditary.

A term x is said to be an "R-ancestor" of the term y if y has every R-hereditary property that x has, provided x is a term which has the relation R to something or to which something has the relation R. (This is only to exclude trivial cases.)

The "R-posterity" of x is all the terms of which x is an R-ancestor.

We have framed the above definitions so that if a term is the ancestor of anything it is its own ancestor and belongs to its own posterity. This is merely for convenience.

It will be observed that if we take for R the relation "parent," "ancestor" and "posterity" will have the usual meanings, except that a person will be included among his own ancestors and posterity. It is, of course, obvious at once that "ancestor" must be capable of detiition in terms of "parent," but until Frege developed his generalised theory of induction, no one could have defined "ancestor" precisely in terms of "parent." A brief consideration of this point will serve to show the importance of the theory. A person confronted for the fist time with the problem of defining "ancestor" in terms of "parent" would naturally say that A is an ancestor of Z if, between A and Z, there are a certain number of people, B, C, . . . , of whom B is a child of A, each is a parent of the next, until the last, who is a parent of Z. But this definition is not adequate unless we add that the number of intermediate terms is to be finite. Take, for example, such a series as the following:-

- 1, - 1/2, - 1/4, - 1/8, . . . 1/8, 1/4, 1/2, 1.

Here we have first a series of negative fractions with no end, and then a series of positive fractions with no beginning. Shall we say that, in this series, - 1/8 is an ancestor of 1/8 ? It will be so according to the beginner’s definition suggested above, but it will not be so according to any definition which will give the kind of idea that we wish to define. For this purpose, it is essential that the number of intermediaries should be finite. But, as we saw, "finite" is to be defined by means of mathematical induction, and it is simpler to define the ancestral relation generally at once than to define it first only for the case of the relation of n to n + 1, and then extend it to other cases.Here, as constantly elsewhere, generality from the first, though it may require more thought at the start, will be found in the long run to economise thought and increase logical power.

The use of mathematical induction in demonstrations was, in the past, something of a mystery. There seemed no reasonable doubt that it was a valid method of proof, but no one quite knew why it was valid. Some believed it to be really a case of induction, in the sense in which that word is used in logic. Poincare considered it to be a principle of the utmost importance, by means of which an i&rite number of syllogisms could be condensed into one argument. We now know that all such views are mistaken, and that mathematical induction is a definition, not a principle. There are some numbers to which it can be applied, and there are others to which it cannot be applied. We define the "natural numbers" as those to which proofs by mathematical induction can be applied, i.e. as those that possess all inductive properties. It follows that such proofs can be applied to the natural numbers, not in virtue of any mysterious intuition or axiom or principle, but as a purely verbal proposition. If "quadrupeds" are defined as animals having four legs, it will follow that animals that have four legs are quadrupeds; and the case of numbers that obey mathematical induction is exactly similar.

We shall use the phrase "inductive numbers" to mean the same set as we have hitherto spoken of as the "natural numbers." The phrase "inductive numbers" is preferable as affording a reminder that the definition of this set of numbers is obtained from mathematical induction.

Mathematical induction affords, more than anything else, the essential characteristic by which the finite is distinguished from the infinite. The principle of mathematical induction might be stated popularly in some such form as "what can be inferred from next to next can be inferred from first to last." This is true when the number of intermediate steps between first and last is finite, not otherwise. Anyone who has ever watched a goods train beginning to move will have noticed how the impulse is communicated with a jerk from each truck to the next, until at last even the hindmost truck is in motion. When the train is very long, it is a very long time before the last truck moves. If the train were infinitely long, there would be an infinite succession of jerks, and the time would never come when the whole train would be in motion. Nevertheless, if there were a series of trucks no longer than the series of inductive numbers (which, as we shall see, is an instance of the smallest of infinites), every truck would begin to move sooner or later if the engine persevered, though there would always be other trucks further back which had not yet begun to move. This image will help to elucidate the argument from next to next, and its connection with finitude. When we come to infinite numbers, where arguments from mathematical induction will be no longer valid, the properties of such numbers will help to make clear, by contrast, the almost unconscious use that is made of mathematical induction where finite numbers are concerned.