From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931

Contents:

302 Mathematical Logic

The foundations of elementary arithmetic established by means of the recursive mode of thought, without the use of apparent variables ranging over infinite domains

THORALF SKOLEM n/a

(1923)

1923 *Begründung der elementaren Arithmetik durch die rekurrierende Denkweise ohne Anwendung scheinbarer Veränderlichen mit unendlichem Ausdehnungsbereich, Videnskapsselskapets skrifter, I. Matematisk-naturvidenskabelig klasse, no. 6 (302–333 of the present volume).

Written in 1919, after Skolem had studied Principia mathematica, and published in 1923, the present paper offers a new way of developing arithmetic, a way that avoids the difficulties presented by the paradoxes and the complexities of the theory of types. Unbounded quantifiers are not used, and the theorems become free-variable formulas. Of course, such formulas constitute a limited means of expression as compared to those of an arithmetic embedded in the full predicate calculus of first order. To take a simple example, we can state and prove in free-variable arithmetic that there exist infinitely many primes, in the sense that, for any prime x, there exists a prime y such that The existential quantifier used here is bounded and can easily be dispensed with. But that there exist infinitely many pairs of twin primes cannot (today) be stated by means of a free-variable formula.

In the arithmetic developed by Skolem the limitations of free-variable formulas are overcome, so far as possible, by the use of primitive recursive definitions for the introduction of new functions or predicates and the use of the rule of mathematical induction for proofs. This is what Skolem calls the "recursive mode of thought". Bounded quantifiers are simply a convenient shorthand notation. This arithmetic is now known as primitive recursive arithmetic.

Relinquishing existence as a primitive notion or as the negation of universalization brings Skolem’s work somewhat close to intuitionism. Skolem himself wrote (1929a, p. 13) that in the present paper, "independently of Brouwer and without knowing his writings, I set forth similar ideas, confining myself, to be sure, to elementary arithmetic". Actually, intuitionistic arithmetic, while it refuses to apply the principle of excluded middle to negations of universal propositions, does contain such negations (even as antecedents of conditionals) and is wider than primitive recursive arithmetic.

Now consider a formula F of primitive recursive arithmetic and replace the variables by numerals. The defining equations of the primitive recursive functions that F may contain allow us to compute the values of these functions for the arguments selected. When the functions of F are replaced by their values, F becomes a variable-free numerical formula, which we shall call an instance of F; the truth of this instance can be determined 303 by the truth-table method. If all the instances of F are true, we say that F is verifiable. The existence of instances gives to free-variable formulas a transparent meaning that other formulas lack. It is true that free-variable formulas are equivalent, from the point of view of derivation and that of interpretation, to their universal closures. But prenex occurrences of universal quantifiers do not raise the same problems as those whose scope is not the whole formula. With or the equivalent contrast This last formula has no instances; in fact, it is equivalent to and the existential quantifier involves an infinite search in the sequence of natural numbers. If we have a proof of a free-variable formula F in a free-variable system of arithmetic and if we consider an instance of F, the proof of F can be transformed into a proof of this instance of F: variables are replaced by numerals, function values are computed, and an application of the rule of mathematical induction is replaced by a sequence of conditionals (see Hilbert and Bernays 1934, pp. 298–299). Hence a proof of the formula F in free-variable arithmetic can be regarded as a schema that, by effective (and easy) transformations, yields proofs of the instances of F.

Skolem does not raise any metamathe-matical questions about primitive recursive arithmetic. First, he does not work within a formal system but simply in "naïve" arithmetic. Then, what he does is to derive theorems to see how far one can go with the limited means that he has adopted. He reaches the greatest common divisor and the least common multiple, as well as elementary theorems about prime numbers.

Hilbert and Bernays (1934, pp. 307–346) gave an ample presentation of Skolem’s work. Their interest in it was apparently prompted by the fact that they considered the arguments carried out in this arithmetic to be "finitary". Gödel’s constructive arguments in his incompleteness proof for arithmetic (1931) are carried out in what is actually primitive recursive arithmetic (see, for instance, definitions 1–45 below, pp. 603–606; see also footnote 34, p. 603). Hilbert and Bernays (1934, p. 325) remark that the theorems of this arithmetic are verifiable formulas and that this fact directly yields the consistency of the arithmetic. A consistency proof carried out in a formalized metalanguage was given by H. E. Rose (1961), together with some incompleteness results. For further results on, and applications of, primitive recursive arithmetic see Church 1955, 1957, 1957a, and Rose 1962.

Gödel (1931, pp. 180–181; below, pp. 602–603) and, following him but in greater detail, Hilbert and Bernays (1934, pp. 310–312) showed that in primitive recursive arithmetic a truth function of equations is equivalent to an equation of the form Using this idea, Curry (1941) and Goodstein (1941, 1957) were able to develop primitive recursive arithmetic as a logic-free calculus (see some historical notes on that point in Goodstein 1957, p. 187).

The translation is by Stefan Bauer-Mengelberg, and it is printed here with the kind permission of Professor Skolem and the Norske Videnskaps-Akademi i Oslo.

The fundamental notions of logic that are customarily regarded as necessary for the foundations of mathematics (see, for example, Whitehead and Russell 1910, 1912, and 1913) are, in the first place, the following: the notions proposition and propositional function of one, two, or more variables; the three operations of (1) conjunction (expressed in ordinary language by means of the word "and" or the words "—— as well as ——"), (2) disjunction (customarily expressed by means of the words 304 "either —— or ——"), and (3) negation (indicated by the word "not"); and finally Russell and Whitehead’s notions "always" and "sometimes". These last two notions express the idea that a proposition holds in all cases or in at least one case, respectively. To say that a proposition holds in at least one case is to state an existential proposition, and that is customarily done by means of the words "there exists". Throughout the present work I shall use capital letters as symbols for propositional functions, so that A(x), B(x), . . . denote propositional functions of one variable, A(x, y), B(x, y), . . . denote propositional functions of two variables, and so on. Furthermore, I employ Schröder’s signs (1890) for conjunction, disjunction, and negation, so that, if A and B are propositions, AB means the proposition "A as well as B", the proposition "either A or B", and finally the negation of A. In addition, however, Russell and Whitehead introduce the notion "descriptive function". A descriptive function is an expression having an unambiguously determined meaning; it is a kind of functional proper name. Finally, according to Russell and Whitehead, it is necessary to introduce as a sort of functional assertions propositions that hold generally. We say that we have a functional assertion when it is asserted that a proposition holds for the indeterminate case.

Now what I wish to show in the present work is the following: If we consider the general theorems of arithmetic to be functional assertions and take the recursive mode of thought as a basis, then that science can be founded in a rigorous way without use of Russell and Whitehead’s notions "always" and "sometimes". This can also be expressed as follows: A logical foundation can be provided for arithmetic without the use of apparent logical variables. To be sure, it will often be advantageous to introduce apparent variables; but we shall require that these variables range over only finite domains, and by means of recursive definitions we shall then always be able to avoid the use of such variables. All this will become clear in what follows.

I wish to remark, incidentally, that I really regard all functions as descriptive; the propositional functions are just characterized by the fact that they can have only the two values "true" and "false", which, of course, are also among the fundamental logical notions.

I regard the descriptive functions as functional proper names, that is, proper names whose meaning depends upon what we choose for one or more variables. For instance, I regard "the number following n", as being the name of a number, but one that, depending on what we choose for n, denotes different numbers.

According to Russell and Whitehead, descriptive functions, such as "the author of Waverley", do not really mean anything but are merely incomplete symbols. This conception does not seem to me to be beyond doubt; but even if it were correct for the descriptive functions of ordinary language, we would not need to adopt it for the descriptive functions of arithmetic.

Russell and Whitehead reason as follows. "The author of Waverley" cannot mean Scott; for then the proposition "Scott is the author of Waverley" would mean "Scott is Scott", and that is an entirely empty proposition. On the other hand, "the author of Waverley" cannot mean any other person; for then the proposition "Scott is the author of Waverley" would be false, which, as is well known, is not the case. Consequently, "the author of Waverley" means nothing; it is an incomplete symbol.

This proof, which has a rather philosophical character, does not, however, seem 305 entirely compelling to me. What is to prevent us from regarding "the author of X"—let us write V(X) for short—as a kind of variable proper name? Then surely, "the author of Waverley" names the same person as does "Scott". But the two names are distinct, and that is why the proposition "Scott is the author of Waverley" cannot be replaced by the proposition "Scott is Scott". The latter proposition is empty, but not the former, and the reason for this is that one already knows something in advance about the person called V(X), since, after all, it is generally accepted that a person is to be called V(X) if and only if he and no one else wrote X. The information conveyed is, in my opinion, of the same kind as in the following case: A man has two proper names, A and B. At one time we have heard something about A, for example that he has five children. On another occasion we are introduced to Mr, B, and we are told that B is Mr. A. This proposition then contains information about B, namely that B has five children, because we had some prior knowledge about A. The proposition "Bis A" is therefore entirely different from the propositions "A is A" and "B is B"; the latter are completely empty, but the former is not, if something is already known in advance about A but not about B, or about B but not about A.

The use of the equal sign in what follows is always to be understood in the sense that two names or expressions mean or designate the same thing. That is also why I regard it as obvious that I can everywhere replace equals by equals, and I do this throughout.

The notions "natural number" and "the number following the number n" (thus, the descriptive function ) as well as the recursive mode of thought are taken as basis.1

§1. ADDITION

I wish to introduce a descriptive function of two variables, a and b, which I shall call the sum of a and b; I denote it by since for it is to mean precisely the number following a, namely, This function is therefore to be regarded as already defined for for arbitrary a. To define it generally, I then need only define it for for arbitrary a if it is already assumed to be defined for b for arbitrary a. This is accomplished by the following definition:

Definition 1.

Thus the sum of a and is set equal to the number following If, therefore, addition is already defined for arbitrary values of a for a certain number b, then by Definition 1 addition is defined for arbitrary a for and is thereby defined generally. This is a typical example of a recursive definition.

THEOREM 1. (The associative law.)

Proof. The proposition holds for by virtue of Definition 1. I assume that it holds for a certain c for arbitrary values of a and b. Necessarily, then, for arbitrary values of a and b,

306

since, according to Definition 1, But according to Definition 1 necessarily also

Now, according to the assumption, whence

According to Definition 1 we finally also have

From (α), (β), (γ), and (δ), it follows that

which proves the proposition for for unspecified a and b. Thus the proposition holds generally. This is a typical example of a recursive proof (proof by mathematical induction).

Lemma.

Proof. The proposition holds for I prove that it holds for assuming that it holds for a. In fact, we obtain

by virtue of the assumption made and Definition 1. Thus the proposition holds generally.

THEOREM 2. (The commutative law.)

Proof. In consequence of the lemma the proposition holds for I assume that it is true for arbitrary a for a certain b and then prove that it is true for for arbitrary a. This is done as follows:

by use of Theorem 1 and the lemma. The functional assertion is therefore true.

§2. THE RELATIONS < (LESS THAN) AND > (GREATER THAN)

Closely connected with addition are the relations "less than" and "greater than", denoted by < and >, respectively. Since the latter relation is just the converse of the former, only the relation < need be defined. This is customarily done by means of an apparent logical variable, with the use of the logical notion of existence, or Russell and Whitehead’s "sometimes". The usual definition, in fact, has the form

where Schröder’s sign is used to express that a proposition holds in at least one case (Schröder then speaks of propositional summation [Aussagensummation] and denotes it by Σ). In words the definition is as follows: "a is said to be less than b if 307 and only if there exists a number x such that Hence this definition involves the use of the logical notion of existence, or, in other words, the use of an apparent variable. But we can easily avoid using this notion by defining the relation "less than" recursively. This can, in fact, be done thus:

Definition 2. is false.

It is easily seen that this is a perfectly legitimate recursive definition; for, first, it specifies under what conditions if namely, none; and, second, it specifies under what conditions the relation < is to obtain between an arbitrary a and a certain if it is already defined for b for arbitrary a. As we see, no logical Σ-sign occurs in this definition.

Definition 2.1.

THEOREM 3. or, which is the same thing, In words this theorem reads: If both and hold, then

Proof. The proposition holds for arbitrary a and b when for, according to Definition 2, is false, that is, is true. I therefore want to prove that the proposition is true for whenever it is true for c (with the values of a and b unspecified). From it follows, according to Definition 2, either that or that But, according to the assumption, from it follows that whence, by Definition 2, From of course, also follows, whence again In every case, therefore, if both and hold, so that the proposition must also be true for arbitrary a and b for This proves Theorem 3.

Definition 3.

Definition 3.1.

These definitions, like Definition 2.1, merely introduce notational variants; they are therefore theoretically superfluous, which is not the case for recursive definitions.

Lemma 1 (for Theorem 4).

In words: Either a is not less than b, or is less than or equal to b. But it is better to state it thus: From it follows that

Proof. For an unspecified a the proposition holds for I assume that it is true for arbitrary a for a certain b and then prove that it is true for arbitrary a for From it follows (Definition 2) either that whence, in consequence of the assumption, which in turn yields (Definition 2) or that whence clearly which yields (Definition 3) The proposition thus holds, for arbitrary values of a, for also and therefore holds generally.

Lemma 2 (for Theorem 4).

Proof. The proposition holds for From the assumption that it holds for a, that is, that it follows (Definitions 2 and 3) that which yields (Definition 3) that is, the proposition also holds for

THEOREM 4.

Proof. The proposition holds for since according to Lemma 2 necessarily either or I assume that the proposition is true for b with unspecified a and prove that it is true for for arbitrary a. For, if it is not the case that 308 neither nor is possible (Definition 2); but then, in consequence of the assumption, whence (Lemma 1)

Lemma.

This proposition can be expressed in words thus: From it follows that and conversely.

Proof. From it follows (Lemma 1 for Theorem 4) that whence (Definition 2) From it follows (Definition 2) either that or that Hence in either case

THEOREM 5. that is, no number is less than itself.

Proof. This is true for (Definition 2). I assume that it is true for a certain a. From it would follow, according to the last lemma, that which conflicts with the assumption made.

Corollary to Theorems 3 and 5. [For distinct a and b]

In words: If then not and conversely.

For, if we were to have and at the same time it would follow (Theorem 3) that

Corollary. 2 that is, if then a is not equal to b. For from it would follow that

The three relations and are thus mutually exclusive, while on account of Theorem 4 in every case one of them must be satisfied.

THEOREM 6.

Proof. According to the lemma for Theorem 5 this is certainly true when We assume that it has already been proved to be true for arbitrary a and b for a certain c. From it then follows that whence, by virtue of Theorem 1 and the same lemma, Conversely, it follows from by virtue of Theorem 1 and this lemma that whence, according to the assumption,

THEOREM 7.

That is, if both and hold,

Proof. From it follows (Theorem 6) that From it follows (Theorems 2 and 6) that From the assumption that both and hold it follows (Theorem 3) that

This is a typical example of a nonrecursive proof, one that consists merely of a finite combination of earlier theorems, whereas a proof by mathematical induction represents an infinite process. We have, incidentally, already had several other examples of nonrecursive proofs (namely, those of the lemma for Theorem 5 and of the corollaries to Theorems 3 and 5).

THEOREM 8.

That is, from it follows that Clearly, the converse is also true.

Proof. If then necessarily (Theorem 4) either or From however, it follows (Theorem 6) that and from in the same way, 309 that and both contradict (corollary to Theorem 5) the equation

The special case of this theorem asserts that there can exist at most one number having a certain successor, or, in other words, each number can have one predecessor at most.

THEOREM 9.

Proof. True for for unspecified a (Definition 2). We assume that the proposition is true for arbitrary a for a certain b. But from we obtain further (Definition 2) that is (Definition 1),

§ 3. MULTIPLICATION

Definition 4.

This is a recursive definition of a descriptive function ab of two variables, a and b, which is called the product of a and b.

THEOREM 10. (First distributive law.)

Proof. The proposition holds (Definition 4) for We therefore assume that it holds for arbitrary a and b for a certain c. We then obtain

making use of Theorem 1, Definition 4, and the assumption made.

THEOREM 11. (The associative law.)

Proof. The proposition holds (Definition 4) for We therefore assume that it is true for arbitrary a and b for a certain c. Then we obtain

applying Definition 4, Theorem 10, and the assumption made.

THEOREM 12. (Second distributive law.)

Proof. When the proposition is true (Definition 4). We assume that it is true for arbitrary a and b for a certain c. Then by applying Definition 4 and Theorems 1 and 2 we obtain

Lemma.

Proof. True for (Definition 4). If the proposition is true for a, then that is, it is also true for

THEOREM 13. (The commutative law.)

Proof. This proposition holds (by the lemma) for arbitrary a when From the assumption that it is true for b for arbitrary a it follows (Theorem 12 and the lemma) that

THEOREM 14.

310

In words: From it follows that and conversely.

Proof. Clearly, the proposition is true for arbitrary a and b when Therefore we now assume that it holds for arbitrary a and b for a certain c. Then from it follows that whence (Theorem 7) that is (Definition 4), The converse must also be true; for from it would follow that and from according to what has been proved, that

Corollary. that is, from it follows that

THEOREM 15.

Proof. True for (Definition 4). From the assumption that the proposition is true for b it follows by Theorem 3, since (Theorem 9) that that is, the proposition is also true for

Corollary. From it follows that or, alternatively,

§ 4. THE RELATION OF DIVISIBILITY

Closely connected with multiplication is the notion of divisibility. It is generally defined by means of an apparent variable. For we say that a is divisible by b if there exists a number x such that If we use Schröder’s symbols and let D(a, b) mean the propositional function "a is divisible by b", this definition takes the following form:

Such a definition involves an infinite task—that means one that cannot be completed—since the criterion of divisibility is whether, by successive trials through the entire number sequence, we can find a number x such that

Here, however, it is easy to free ourselves from the infinitude that adheres to this definition. For it is clear that a number x having the required property, if such a one exists at all, must occur among the numbers 1, 2, . . ., a; for from it follows by Theorem 15 that Therefore the relation of divisibility can equally well be defined as follows:

To be sure, an apparent variable x still occurs here; but it ranges over a finite domain only, namely, just the values from 1 to a. Therefore this definition furnishes us with a finite criterion of divisibility; we can in every case, by completing a finite task, that is, by performing a finite number of operations, ascertain whether the proposition D(a, b) holds or not. Since now the Schröder propositional sum in this definition is a finite one, it can itself in turn be defined by recursion, and thus the use of an apparent variable can ultimately be avoided altogether. To achieve this we need only define, as a first step, a ternary relation Δ(a, b, c) that is to mean that a is equal to b multiplied by a number between 1 and c (both inclusive). The precise definition of Δ(a, b, c) reads as follows:

Definition 5.

By means of the propositional function Δ the divisibility relation D is defined thus:

Definition 6.

311

It is very easy to see that the propositional equivalence

obtains, so that Definition 6 coincides completely with the finite definition of divisibility mentioned above. In fact this equivalence holds for since the propositional sum on the right then reduces to the single term and from the assumption that it is true for c it follows that it is true for for, after all, means the same as

THEOREM 16. that is, from it follows that Δ(a, b, c).

This immediately follows from Definition 5.

THEOREM 17.

This can also be expressed thus: From it follows that Δ(a, b, c′).

Proof. Clearly, the proposition is true for We assume that it is true for a certain c′ for arbitrary values of a, b, and c. From it follows either that which, together with Δ(a, b, c) yields, according to the assumption, Δ(a, b, c′) and consequently (Definition 5) also or that which, together with Δ(a, b, c), of course yields Hence the proposition is also true for for arbitrary values of a, b, and c and thus holds in full generality.

THEOREM 18. that is, from Δ(a, b, c) it follows that D(a, b).

Proof. From Δ(a, b, 1), that is, it follows by Theorem 17, since (Lemma 2 for Theorem 4) that Δ(a, b, a), that is, D(a, b). Let us now assume that the proposition holds for c. From it follows (Definition 5) either that Δ(a, b, c), whence, in consequence of the assumption, D(a, b), or that whence (Theorem 15) but from it follows (Theorem 17) that Δ(a, b, a), that is, D(a, b).

Corollary to Theorems 16 and 18. that is, from it follows that D(a, b).

THEOREM 19. that is, from it follows that Δ(a, c, de).

Proof. If then from it thus follows that whence (Theorem 16) Δ(a, c, d). We therefore assume that the proposition is true for e (with arbitrary a, b, c, and d). From we obtain (Definition 5) either whence Δ(a, c, de), whence in turn by Theorem 17 since ( by Theorem 9) or whence which again yields (Theorem 16)

Corollary to Theorems 18 and 19. that is, from it follows that D(a, c).

For from it follows (Theorem 19) that Δ(a, c, bd), whence (Theorem 18) D(a, c).

THEOREM 20.

Proof. From Δ(a, b, 1)D(b, c) it follows, of course, that D(a, c), since We assume that the proposition is true for arbitrary a, b, and c for a certain d. From we obtain (Definition 5) either Δ(a, b, d)D(b, c), whence, 312 in consequence of the assumption, D(a, c), or whence, according to the corollary to Theorems 18 and 19, it follows that D(a, c). This proves that the proposition is true for

Corollary. ; that is, from D(a, b)D(b, c) it follows that D(a, c).

This is in fact just the special case that we obtain from Theorem 20 if we put

This last proposition, that D(a, c) follows from D(a, b)D(b, c), is closely related to the proposition that states that follows from but it has a quite different meaning. Even according to the ordinary conception that makes use of apparent variables ranging over an infinite domain, the two propositions are quite different in content, as becomes clear immediately the two are formulated precisely. The one proposition is, in Schröder’s symbols,

The other proposition is

When, nevertheless, one proves that the proposition or (α), is true by proving proposition (β), as is usually done, he does so on the basis of certain logical schemata concerning the use of the signs Π and Σ; in ordinary mathematical thinking, however, these schemata are passed over in silence.

THEOREM 21. .

Proof. From or, in other words, it follows that and thence (Theorem 16) that The proposition is therefore true for We assume that it is true for a certain d and prove as follows that it is true for From it follows either that whence, in consequence of the assumption, which in turn implies (Theorems 1 and 2, and Definition 5) or that whence which again implies (Theorem 16)

Corollary.

THEOREM 22.

Proof. According to the corollary to Theorem 21 this holds for We therefore assume that the proposition is true for a certain e and prove as follows that it is true for From we obtain either and thence, in consequence of the assumption, which in turn implies or whence (Theorem 21)

Corollary.

In words: If both a and b are divisible by c, then too is divisible by c.

For from we obtain, by Theorem 22,

Lemma.

Proof. From it follows (Definition 5) either that which is, 313 however, impossible, since necessarily (Theorem 9) and since (Theorem 5) the relations > and = are mutually exclusive, or that whence (since from it must follow, according to Theorem 8, that Thus our lemma is true for We assume that it holds for c and then prove it for From it follows in fact either that whence, in consequence of the assumption, Δ(a, b, c) and therefore also or that whence (Theorem 8) which again implies

By making use of subtraction, even before it is introduced (see § 5), we can also state this lemma in the following form: From it follows that For this is true when because the hypothesis is then false. Whenever the proposition holds for c, it holds also for ; for from we obtain, according to what has just been proved, Δ(a, b, c), and (see Definition 7 [below]).

THEOREM 23.

Proof. In case we are back at the lemma. We therefore assume that the proposition is true for d and prove that it is true for From it follows (Definition 5) either that or that In the first case, since (Theorem 10) , we obtain (Theorem 8) whence (Theorem 16) Δ(a, b, c). In the second case, since necessarily (Lemma 2 for Theorem 4, and Theorem 9) , we obtain, by the lemma, whence , which, according to the assumption, implies Δ(a, b, c).

THEOREM 24.

Proof. This is true for ; for from we obtain, according to the lemma for Theorem 23, Δ(a, c, d) and therefore also . We shall therefore assume that the proposition is true for e (with arbitrary a, b, c, and d) and then prove that it is true for (for arbitrary values of a, b, c, and d). From we obtain either , which, according to the assumption, implies , in other words , or , whence (Theorem 23) Δ(a, c, d), which again implies (Theorem 17) .

Corollary. .

For, first, must follow (Theorem 24) from and, second, D(b, c) is a consequence (Theorem 18) of

After the introduction of subtraction we shall be able to write this theorem also as follows: .

That is, if both a and b are divisible by c and if a is greater than b (so that the difference exists), then is divisible by c

THEOREM 25. .

Proof. Clearly, the proposition holds for . If we assume that it holds for c, we obtain from either Δ(a, b, c), which thus yields , or , from which (Theorem 15) also follows.

Corollary 1. .

Corollary 2. .

314

For from it must follow (Theorem 5) that .

THEOREM 26. .

In words: From Δ(a, b, d) it follows that Δ(ac, bc, d), and conversely.

Proof. The proposition is true for ; for from it follows, according to the corollary to Theorem 14, that , and conversely from it of course follows that We assume that the proposition is true for d and prove that it is true for From we obtain either Δ(a, b, d), which according to the assumption implies Δ(ac, bc, d) and therefore also , or , whence (Theorems 11 and 13) , and from it again follows (Theorem 16) that . Likewise we obtain from either Δ(ac, bc, d), whence Δ(a, b, d) and therefore also , or , whence, in consequence of the corollary to Theorem 14, , whence (Theorem 16)

Corollary.

THEOREM 27. .

Proof, True for We therefore assume that the proposition is true for e and prove that it is true for . From we obtain either Δ(d, c, e) which together witch yields, according to the assumption, Δ(a, bc, e) and therefore also or , which together with yields (Theorem 11) , whence (Theorem 16) .

§ 5. SUBTRACTION AND DIVISION. DESCRIPTIVE FUNCTIONS WITH A RESTRICTED DOMAIN OF EXISTENCE

Subtraction, as is well known, can be defined in the following manner:

Definition 7.

It is clear that in this way a descriptive function , called the difference, is defined; for, by means of the equation , a is uniquely determined by b and c. This, however, is a descriptive function with a restricted domain of existence; for, if , no equation of the form can obtain, and then according to Deftniton 7 the inequality obtains for every number a; that is, is not equal to any number. On the other hand it can be proved that will certainly have a value when . One would be inclined to formulate this proposition thus:

where the propositional summation over x would have to be extended over "all" numbers from 1 to ∞. But it is not necessary to adduce such an actual infinity here either; we can in fact prove the following proposition:

which, after all, will more readily serve to secure the existence of a value for . But the propositional function

315

of the three variables x, y, and z again can be defined recursively, so that we can avoid the apparent variable u altogether. The theorem that is to be proved is then obviously the following:

THEOREM 28.

In words this theorem reads as follows: If , there exists among the numbers from 1 to c a number x such that , or, in other words,

We need the recursive definition of the function L and a few simple theorems about it.

Definition 8.

THEOREM 29. .

Proof. True for . I assume that it is true for z′ and from that prove that it is true for . From it in fact follows either that , which together with L(x, y, z), according to the assumption, yields L(x, y, z′) and therefore (Definition 8) also , or that , which with L(x, y, z) obviously yields

THEOREM 30. .

Proof. True when ; for from it follows (Theorems 1 and 2) that . I assume that the proposition is true for z and prove that it is true for . From it follows (Definition 8) either that L(x, y, z), whence, according to the assumption made, and therefore also follow, or that , whence (Theorems 1 and 2) , whence (Definition 8)

Now the proof of Theorem 28 can be carried out.

The proposition stated as Theorem 28 is certainly true for ; for, in that case, already is true. I therefore assume that it is true for c and prove that it is true for . From we obtain (see Lemma 1 for Theorem 4, the lemma for Theorem 5, and Theorem 8) either , which, according to the assumption made, gives us L(c, b, c), whence it further follows (Theorem 30) that , or whence (Theorem 2) ; hence (Definition 8) and thence (Theorem 29) again

Division is introduced in a manner analogous to subtraction.

Definition 9. .

The expression c/b, called the quotient, is clearly again a function with a restricted domain of definition; for from it follows (corollary to Theorems 16 and 18) that D(c, b), so that c/b has a value only if D(c, b) is true. Conversely, this is also sufficient; for, the proposition D(c, b), or, in other words (see Definition 6), Δ(c, b, c), is equivalent to the propositional sum

(see p. 311), and so that this propositional sum can be formulated in words thus: Among the numbers from 1 to c [inclusive] there exists a number x such that or, in other words,

316

The propositional function D(c, b) is therefore completely equivalent to the assertion that between 1 and c there exists a value for c/b.

I now give some simple theorems about differences and quotients. Presumably I do not have to give the proofs, which are trivial; these theorems are, after all, mere transformations of the simplest theorems about sums and products.

THEOREM

° 6. GREATEST COMMON DIVISOR AND LEAST COMMON MULTIPLE

The customary definitions of the greatest common divisor and the least common multiple of two numbers make use of apparent variables that range over an infinite domain. In Schröder’s symbols these definitions in fact have the following form:

(c is the greatest common divisor of a and b)

(c is the least common multiple of a and b)

Since, however, follows (Corollary 1 to Theorem 25) from D(a, x), the infinite domain over which the variable ranges in the definition of the greatest common divisor can at once be cut down to a finite one, and we can just as well write

(c is the greatest common divisor of a and b)

A disadvantage of this definition is, however, that it is asymmetric with respect to a and b. But this, too, can easily be remedied, since over the sign Π we can write instead of the upper bound a, or even better Min(a, b), where Min(a, b) is the minimum of the numbers a and b. For the definition of the least common multiple such a reduction of the range of the variable to a finite domain cannot be carried out quite so easily.

In what follows I shall introduce these notions in a different way, one that avoids apparent variables altogether. In doing this, however, I must make use of the recur-sive method of definition in a different way from before (though, as I shall soon show, the difference is purely superficial). Until now we have always given recursive definitions strictly as follows: we defined a notion for the number 1 and then, on the 317 assumption that the definition for an arbitrarily given number n is already complete, we defined the notion for Furthermore, a formal logical principle will be used here, namely, that we can give separate definitions for each one of mutually exclusive cases. I introduce two descriptive functions of two variables a and b, namely and , which I shall later show to be identical with the greatest common divisor and the least common multiple, respectively.

Definition 10.

This is a perfectly legitimate recursive definition of the descriptive function ; if we assume that it is already defined for those values of a and b for which , then by Definition 10 it is defined for . For, if a and b are two numbers such that , then or or , and these three cases are mutually exclusive, while Definition 10 specifies for each case what is to mean. Moreover, Definition 10 gives us the value of when , in which case necessarily

In the proofs of some of the theorems that follow I shall also make use of mathematical induction in a different way from before (though, as I shall soon show, the difference is purely superficial). Until now this inductive inference has always been made thus: we prove a proposition for the number 1 and then we prove it for on the assumption that it holds for n. Now I shall also prove inductively as follows: I prove a proposition for 1, and then, assuming that it holds for an arbitrary number , I prove it for n.

Lemma.

Proof. True for in consequence of Definition 10. If we assume that the proposition is true for a, we obtain, according to Definition 10, since (Theorem 9) , and therefore also

Likewise it can be proved that In general, of course,

THEOREM 37.

Proof. This proposition is true for arbitrary a for and for arbitrary a for for, according to the lemma, . I assume that the proposition is true for and then prove that it is true for . For if, first, , then, according to Definition 10, , and consequently the proposition holds. If, second, then , and then, in consequence of the assumption, holds. But, according to Definition 10, and we therefore obtain whence by the corollary to Theorem 22 and by Theorem also follows. The proposition, therefore, is true in this ease also. If, third, we can proceed in an exactly analogous way.

THEOREM 38.

Proof. The proposition holds for arbitrary b when and for arbitrary a when ; for then it follows from D(a, c), or D(b, c), respectively, that I assume that the proposition holds for such a and b as will make , and I prove from that assumption that it holds for such a and b as will make . Therefore, let a and b be numbers such that . First, then, it may be that ; in this case, according to Definition 10, and the proposition is therefore true. Second, it may be that . Since must, by the 318 assumption, follow from but in turn is a consequence of D(a, c)D(b, c) (corollary to Theorem 24), and finally (Definition 10) in this case Thus follows from D(a, c)D(b, c). In the third case, we proceed in exactly the same way.

Theorems 37 and 38 together express the characteristic properties of the greatest common divisor.

THEOREM 39.

Proof. In consequence of Theorem 37 we have On the other hand, follows (Theorem 38) from D(a, b)D(b, b). From however, it follows (Corollary 2 to Theorem 25) that

Corollary.

THEOREM 40.

Proof. The proposition is true for arbitrary a for and for arbitrary b for as immediately follows from the lemma for Theorem 37 and the corollary to Theorem 39. We therefore assume that we have already proved that the proposition holds for and on this basis we prove that it holds for such a and b that It is possible, first, that Then also and, according to Definition 10, we have and which yield The second case is Since we have, according to the assumption made, But furthermore and since, then, also (Theorem 14) we necessarily, according to Definition 10, have Finally (Theorem 35), Thus the equation holds. In the third case, when we of course proceed in the same way.

Definition. We say that two numbers a and b are relatively prime if I do not introduce a special symbol for this, since we can always use the short equation as an expression for it.

THEOREM 41.

This is the well-known theorem that a number b that divides a product ac whereas it is relatively prime to the factor a must divide the other factor, c.

Proof. From D(ac, b)D(bc, b) it follows (Theorem 38) that But from it follows (Theorem 40) that so that D(c, b) must be true.

THEOREM 42.

Proof. In consequence of Theorem 37, holds; but from it follows (corollary to Theorem 20) that which together with yields (Theorem 38) Then from it must therefore surely follow that for from D(1, α) it follows (Corollary 1 to Theorem 25) that

THEOREM 43. .

Proof. If a number d divides a as well as bc, then necessarily (Theorem 42) as well as provided obtains. Further, it must, according to Theorem 41, follow from that D(b, d). But from D(b, d) it follows (Theorem 39) that on the other hand, we had ; therefore But now (Theorem 37) divides a as well as bc; therefore .

319

THEOREM 44. (Generalization of Theorem 41.)

Proof. In the first place it is clear that necessarily for, by Theorem 40, we have From D(ac, b) it follows (corollary to Theorem 26) that whence, according to Theorem 41, since and are relatively prime.

Definition 11.

HEOREM 45.

Proof. True when ; for from it follows that D(b, c), whence (Theorem 39) and consequently, by Definition 11, I assume that the proposition is true for d and prove that it is true for . From it follows either that Δ(a, b, d), which together with D(a, c) yields, according to the assumption, and therefore also or that which together with D(a, c) yields (Theorem 44) But from we again obtain by Theorem 27.

THEOREM 46.

Proof. According to Theorem 37, holds, whence (corollary to Theorem 26) that is, Likewise implies that is true.

THEOREM 47.

This is merely a special case of Theorem 45, which results when d and a are equated.

Theorems 46 and 47 together express the characteristic properties of the least common multiple of two numbers a and b. Thus denotes the least common multiple of a and b.

An important special case of Theorem 47 is the one in which From it follows that D(c, ab).

We have, corresponding to Theorem 39,

THEOREM 48. .

That this proposition is true follows immediately from Theorem 39 and Definition 11.

We have, corresponding to Theorem 40,

THEOREM 49.

Proof. here use is made of Theorems 11, 13, 32, and 40.

I want to conclude this section by giving a proof that the more involved kinds of recursive definition and recursive proof used above differ only formally, not actually, from the ordinary simple recursive procedure that goes from n to The standard form of a recursive definition, after all, is as follows: a propositional function U(x) is defined first for and then, if U(n) has already been defined, for But above we also considered recursive definitions of the following kind: first we defined U(1) and then, with U(m) assumed to have been defined for arbitrary U(n). It is clear that the value of the propositional function for arbitrarily selected x and y will be known if U(y) is defined for the y in question; but conversely it will also be known whether U(y) is true or false for a if U(y) 320 is defined for the x and y in question. To define U(x), therefore, it will suffice to define for arbitrary x and y; here we can observe that, for every pair of values (x, y) for which must necessarily be false. To specify the value of generally, we can now apply the standard recursive procedure. For is necessarily false, according to the definition of the relation "less than", whenever ; we thus need merely specify U(1) in order to have the value of for arbitrary y. Further, we specify the value of for for arbitrary y when it has already been specified for x for arbitrary y. Whenever is false. When we already know the value of the propositional function; that is, we must merely specify Therefore, to specify the value ofwhen this function is regarded as known for arbitraryamounts precisely to specifying the value of the propositional functionforfor arbitrary y when this propositional function is already known forfor arbitrary y. Thus the apparently divergent kind of recursive definition has been reduced to the standard form.

Likewise it is easy to see that the more complicated form of inductive inference, which consists in proving a proposition for n when it is assumed to be true for arbitrary , differs only formally but not actually from the standard form of inductive inference, the inference from n to To say that U(y) has been proved for arbitrary is, after all, equivalent to saying that has been proved for this x for arbitrary y, and it is then not difficult to see that to proveU(x), with U(y) assumed to be true for arbitraryis equivalent to provingfor arbitrary y whenhas already been proved for arbitrary y.

§ 7. THE NOTION OF PRIME NUMBER

Definition 12. P(x, 1) is true.

Definition 13.

The propositional function P(x) means "x is a prime number".

Definition 14, De(x, 1) is false.

Definition 15. Dp(x, 1) is false.

Definition 16. T(1) is true.

In the customary definition of the notion of prime number an apparent variable is used. If the relation of divisibility is regarded as already defined, the definition of prime number can be given as follows:

An infinite propositional product (or, in other words, Russell and Whitehead’s "always") occurs here. But in Definitions 12 and 13 above no apparent variable occurs. The infinite propositional product can be avoided since it can immediately be replaced by a finite one. For, according to the corollary to Theorem 25, we necessarily have if D(x, y) is true, and thence it follows that in the infinite product all factors for which holds become inoperative. Consequently we can just as well define P(x) thus:

321

The finite propositional product occurring here is nothing but the factor P(x, x) on the right side of Definition 13; P(x, y) is recursively defined by Definition 12 and is equivalent to the product

Precisely because these propositional products are finite can they be defined recursively and thus apparent variables avoided altogether.

The remaining propositional functions introduced above, De, Dp, and T, have, as is easily seen, the following meanings in words:

De(x, y) means "x is divisible by a number and ".

Dp(x, y) means "x is divisible by a prime

T(x) means that all numbers from 2 to x are divisible by at least one prime

THEOREM 50.

Proof. When the proposition is clearly true. I prove the proposition for assuming that it holds for y. From it follows that either or From , together with P(x, y) (which follows from and D(x, z), we obtain, according to the assumption, either or From together with (which also follows from and D(x, z), we obtain

Corollary.

For from it follows (Theorem 25) that whence, according to the theorem just proved,

THEOREM 51.

Proof. Since is true (Theorem 37), we necessarily have, whenever P(y) holds, either or according to the corollary to Theorem 50; but from it follows (Theorem 37) that D(x, y).

THEOREM 52.

Proof. According to the preceding theorem, if P(z) is true, either D(x, z) or holds. From D(xy, z)P(z), therefore, either D(x, z) or must follow; but from it in turn follows (Theorem 41) that D(y, z).

THEOREM 53.

Proof. True for since (Definition 12) P(x, 1) already is true. I assume that the proposition is true for y and on this basis prove that it is true for From it follows (Definition 12) either that whence we have De(x, y) and consequently (Definition 14) also or that whence (Corollary 1 to Theorem 25) which, on account of Definition 14, yields

THEOREM 54.

Proof. Clearly true when I assume that the proposition is true for y′ and then prove that it is true for From it follows either that which together with Dp(x, y), according to the assumption, implies Dp(x, y′) and therefore (Definition 15) also or that which together with Dp(x, y) of course implies

THEOREM 55.

322

Proof. For this proposition is true, since (Definition 15) Dp(y, 1) is false. I therefore assume that the proposition holds for z and then prove that it holds for From we obtain (Definition 15) either Dp(y, z), which together with D(x, y) implies Dp(x, z) and consequently also or which together with D(x, y), according to the corollary to Theorem 20, makes true, whence, according to Definition 15,

THEOREM 56.

Proof. According to Definition 15 this must be true for I assume that it is true for y and prove that it is true for From it follows either that Dp(x, y), whence we have Dp(x, x), or that whence, according to Corollary 1 to Theorem 25, but from it follows (Theorem 54) that Dp(x, x).

THEOREM 57.

Proof. The proposition holds for for De(x, 1) is false. I assume that the proposition holds for y and prove it for From it follows either that whence (Definition 16) De(x, y)T(y), whence, in consequence of the assumption, Dp(x, x), or that whence (Definition 16) whence in turn, according to Theorem 55, which implies (Theorem 54) that Dp(x, x) holds.

THEOREM 58. T(x).

Proof. True for (Definition 16). I prove that holds on the assumption that T(x) does. According to Definition 16 I need only prove in order to accomplish this. According to Definition 13 we have either or From it follows, according to Definition 15, that From it follows, according to Theorem 53, that which must (see Definition 14) have as a consequence; but from it follows, according to Theorem 57, that

Corollary.

For from it follows (Definition 16) that

This is the theorem to the effect that every number is divisible by at least one prime. really means that is divisible by at least one prime

Now, to be able to formulate and prove the theorem that every number is a product of primes, I introduce a ternary relation P(x, y, z) that is to mean "x is the product of y primes that are all ".

Definition 17. P(x, y, 1) is false.

This is a doubly recursive definition, for it is recursive with respect to y as well as z. P(x, 1, z) is defined for arbitrary z (and x) and, if it is assumed that is already defined for arbitrary z (and x), then, by means of the first equation of Definition 17 and the stipulation that P(x, y, 1) is to be false, we have a recursive definition of the propositional function P(x, y, z), recursive, that is, with respect to z. Through the last stipulation of Definition 17, P(x, y, 1) is determined and, through 323 the first equation, P(x, y, z) is determined on the basis of the assumption that is already known.

I want to introduce three additional propositional functions.

Definition 18.

Definition 19.

Definition 20. Π⁜(1) is true.

The proposition P′(x, y, z) obviously means that x is a product of at most y primes, each The proposition Π(x) means that x is a product of at most x primes, each means that every number y from 1 to x either is equal to 1 or is a product of at most y primes or, in other words, that every number y from 2 to x is a product of at most y primes . The real purpose of the considerations that follow is to prove that holds.

THEOREM 59.

Proof. Clearly, the proposition is true when I prove it for on the assumption that it holds for z′. From it follows either that which together with P(x, y, x) has P(x, y, z′) and therefore also (Definition 17) as consequences, or that and from it clearly again follows that

Lemma 1 (for Theorem 60).

Proof. Truer for ; for (Definitions 17 and 13) P(x, 1, 1) already is false. I prove the proposition for on the assumption that it holds for z. From it follows according to Definition 17 that whence we have which in turn has as a consequence, or that or that But from it follows (Definition 17) that We proceed analogously in the third case.

Lemma 2 (for Theorem 60).

Proof. According to Lemma 1 this is true for 1 prove that the proposition is true for on the assumption that it holds for y. Now, in case we indeed obtain from for is false. Therefore, on the assumption that the inductive step from y to holds for z, I prove that it holds for From we obtain (Definition 17) three possibilities: (1) already holds; then according to the assumption we have whence (Definition 17) (2) We have but from it follows, since our proposition was assumed to be true for y for arbitrary z, that which together with by virtue of Definition 17 implies (3) We have but from this we obtain (Definition 17)

THEOREM 60.

Proof. On account of Lemma 2, when or this proposition is certainly true for arbitrary values of the remaining variables. Thus it surely holds for the least possible value of the sum namely 4, for which necessarily 324 I now prove that the proposition is true for values of y1, y2, z, and u such that assuming it to be true for those cases in which P(x1, y1, z) is equivalent to either or Furthermore we have either or The first possibility is therefore But, since it follows according to the assumption made that and thence (Definition 17) in turn that The second possibility is But, since here, too, necessarily it follows that The third possibility is But thence it follows, since that and thence (Definition 17) again that

Corollary.

Lemma.

Proof. True for (Definition 18 and Lemma 2 for Theorem 60). I prove that the proposition is true for on the assumption that it holds for y1. From it follows either that P′(x1, y1, z) which together with P(x2, y2, z) has, according to the assumption, and therefore also as consequences, or that whence together with P(x2, y2, z) it follows according to the corollary to Theorem 60 that whence (Definition 18) again

THEOREM 61.

Proof. According to the lemma this is true for I prove that the proposition is true for on the assumption that it is true for y2. From it follows (Definition 18) either that P′(x2, y2, z), whence together with P′(x1, y1, z), according to the assumption made, and therefore also or that which together with P′(x1, y1, z), according to the lemma, implies

Lemma.

Proof. By virtue of Definitions 17 and 18 this is true for I prove the proposition for on the assumption that it holds for y. From it follows either that P′(x, y, z), whence we obtain hence (Definition 18) in turn or that whence (Definition 17) hence (Definition 18)

THEOREM 62.

Proof. Clearly true when I assume that the proposition is true for z′ and then prove it for From either it follows that , and then from it follows, according to the assumption made, that P′(x, y, z′) and thence, according to the lemma, that or it follows that and thence together with P′(x, y, z) it clearly follows that

THEOREM 63.

Proof. Clearly true when I assume that the proposition is true for y′. From it follows either that or that Now, according to the assumption it follows from that P′(x, y′, z) and therefore 325 (Definition 18) also that From it follows, of course, that Thus the proposition holds for too.

THEOREM 64.

Proof. Since according to Theorem 15 necessarily and likewise it follows according to Theorem 62 from P′(x, x, x)P′(y, y, y), that is, from Π(x)Π(y), that P′(x, x, xy)P′(y, y, xy). But according to Theorem 61 it follows from P′(x, x, xy) P′(y, y, xy) in turn that If now in addition then so that by using Theorem 63 we obtain P′(xy, xy, xy), that is, Π(xy). Thus from it follows that Π(xy), which was to be proved.

Lemma 1 (for Theorem 65).

Proof. Clearly true for I assume that the proposition is true for x. From it follows either that or that From it follows (Definition 20) that Π′(x), and therefore it follows from first that and thence further that Π′(y). From it follows, of course, that Π′(y).

Lemma 2 (for Theorem 65).

Proof. This is true when I assume that the proposition is true for z. From it follows (Definition 5) either that Δ(x, y, z) or that From we obtain, according to Definition 20, Δ(x, y, z) and thence, according to the assumption made, Π(x). From it follows (Definition 20) that and thence, according to Theorem 64, that Π(x). Thus the proposition holds for too.

Lemma 3 (for Theorem 65).

Proof, This holds for as may be seen from Definition 14. I assume that the proposition holds for y. From it follows (Definition 14) either that De(x, y) or that From it must follow, according to the assumption, that Π(x). According to Definition 2, must be equivalent to but from it follows (Lemma 1) that whence (Definition 20) and since furthermore, as is easily seen, we necessarily (see Definitions 5 and 6) have it follows from according to Lemma 2, that Π(x).

THEOREM 65. Π′(x).

Proof. True for (Definition 20). I assume that is true and then prove Π(x), which also proves (Definition 20) Π′(x). Either P(x) or holds. From P(x) it follows (Definition 17) that P(x, 1, x), that is (Definition 18), that P′(x, 1, x), whence, according to Theorem 63, P′(x, x, x), that is, Π(x). From it follows (Definition 13) that whence (Theorem 53) De(x, x). But, according to Lemma 3, implies Π(x).

Corollary.

For, according to Definition 20, follows from This, however, is the important theorem that every number is a product of prime numbers.

326

§ 8. SOME EXPLICIT USES OF FINITE LOGICAL SUMS AND PRODUCTS

If we are concerned with avoiding only the use of logical variables ranging over infinite domains, we can, of course, still make free use of variables ranging over finite domains; we need not trouble ourselves either about ways in which these might be avoided by means of recursive definitions or about ways in which the conclusions they allow us to reach might be derived, by mathematical induction, from those that hold for propositions not containing apparent variables.

If we take this approach, then the theory of prime factorization, for example, can be presented more simply, as I show below. I use the definition of prime numbers given on page 320:

Definition.

THEOREM 66.

Proof. Holds for Assume that the proposition holds for all with Then either the proposition or its negation holds (since here is equivalent to and to In the latter case we have D(n, n)P(n). In the former case, according to the assumption, holds; consequently whence

Since D(n, p) is equivalent to the propositional sum we have the

Corollary.

I now define recursively a propositional function that in words is "n is equal to a product of μ prime factors, all of which are

Definition 21.

The theorem on the factorization of any number into a product of primes can then be formulated as follows:

THEOREM 67.

Proof. Holds for Assume that the proposition holds for when Then, according to the corollary to Theorem 66, holds. However, from it follows (Theorem 15) that and thus, according to the assumption, Hence and further which is whence

I want to prove, further, the theorem on the existence of infinitely many primes. First I define the function n! by

Definition 22.

Lemma.

327

Proof. Clearly true for Assume that it is true for a certain n. If not then either or (that is, According to Definition 22 and Theorem 18 we have If we have, according to the assumption, D(n!, m), and, since (Theorems 16 and 18) also holds, we obtain (corollary to Theorem 20)

THEOREM 68. (In words: For arbitrary n there is a prime and

Proof. According to Theorem 66 the proposition holds. But from it follows that For, if we had it would follow, according to the lemma, that D(n!, p), and this together with would imply (corollary to Theorem 24) D(1, p) and therefore which is impossible on account of P(p).

To prove the uniqueness of the factorization of a number into a product of prime factors I must first advance some considerations on sums and products of arbitrarily many terms or factors, as well as define a function I(a, b; m, n).

Let f(r) be an arbitrary descriptive function. I define the expressions and recursively as follows:

Definition 23.

Instead of f(r) we often write ar, br, and so forth. For an arbitrary descriptive function ar I state

Definition 24. if and

THEOREM 69.

Proof. I need consider only the sum. The proposition holds when . Assume that it holds for n. To show that it then holds for also, first let Then

and furthermore Consequently (according to Definition 24)

and thence

On the other hand, let Then for Consequently

In many derivations we make use of the argument that such a sum (or product) remains unchanged whenever the terms (or factors) a are replaced by numbers b, 328 provided these are in some sequential order identical with the a. To be able to formulate this conveniently I introduce a propositional function I(a, b; m, n), where a and b are signs for two arbitrary descriptive functions.

Definition 25. is false. I(a, b; m, 1) is false. (b(v) was defined in Definition 24).

I(a, b; m, n) then means in words: "The numbers are in some ordering identical with the numbers ".

THEOREM 70.

Proof. True when by Definition 25. Assume that it is true for m. From it follows that But implies Hence

THEOREM 71.

Proof. I consider only the sum. First, when it follows that and the proposition clearly holds. Assume that it holds for From I(a, b; m, n) it follows that But, according to the assumption, yields and furthermore we have (Theorem 69) From and it therefore follows that

THEOREM 72.

Proof. The proposition holds for assume that it holds for a certain n. From it follows (Theorem 52) that From it follows, according to the assumption, that Thus in any case which is holds.

THEOREM 73.

Proof. By Theorem 72, from we derive From D(pr, q)P(pr) P(q), however, it follows that hence Therefore

The theorem on the uniqueness of the prime factorization now reads as follows:

THEOREM 74.

Proof. I first prove the proposition for If then it follows, according to Theorem 73, that Further, from and the equation follows, which is impossible if

329

Assume that the proposition is true for a certain μ. Then from the proposition it follows that whence in turn, according to Theorem 73, Furthermore and we therefore obtain whence, according to the assumption, which is

Finally I wish to engage in some reflections of a more general kind. We have the following

THEOREM 75a. where U denotes an arbitrary propositional function.3

In words: If we know a number n for which the proposition U is true, there exists a least number for which U is true. It must be noted here that the propositions with which we are now concerned are always regarded as given without apparent variables ranging over infinite domains, so that it is always finitely decidable whether U(x) is true or not for an arbitrary x.

Proof. For the proposition is clearly true. Assume that it is true for all a certain n. Then if is true, so is either In the former case, therefore, holds. In the latter case it follows from according to the assumption, that4 and therefore a fortiori that

THEOREM 75b. From it follows that

This theorem expresses the uniqueness of the least number.

Proof. If we had we would have But from it follows at once that and likewise, from that

Because of this uniqueness we can introduce a very important descriptive function of the general propositional function U, which denotes the least number for which U is true. This descriptive function, to be sure, has a restricted domain of definition since it has no value if the proposition U is true of no number. But it must be emphasized here that we are concerned only with the natural numbers up to certain upper bound, which, however, may be chosen arbitrarily large. The descriptive function, therefore, may be denoted here by Min(U, n). This means the least number among the numbers 1 to n for which U is true, and it has no meaning if U is false for all these 330 numbers. Thus we are not dealing with a function Min(U), or Min(U, ∞), that would mean the least number satisfying the proposition U and would have no meaning if U is false for every number; for all this would require the "actual infinite", hence the use of apparent logical variables ranging over infinite domains. But the restriction that we must here impose on the meaning of this minimum function does no harm in practice; for, whenever we use the theorem asserting that in a class of positive integers there exists a least, we must in any case first have come to know a number n of this class, and then we can make do with this very function Min(U, n).

Finally I wish to make some remarks on the notion of cardinality [zum Anzahlbegriffe]. If certain objects (numbers, number pairs, number triples, and so forth, or perhaps descriptive functions) are mapped one-to-one onto all numbers a certain number n, then I say that their cardinality is n.

In order to show that this number n is invariant with respect to the different mappings, we must prove the following

THEOREM 76. From where f is an arbitrary descriptive function, it follows that

In words: Assume that the numbers that are are mapped one-to-one onto all numbers then

Proof. I first take the case in which From it follows on account of the uniqueness of f(1) that necessarily

Assume that the proposition holds for a certain m. Then, if I take the value in any case necessarily Otherwise from we would obtain as well as whereas we were supposed to have had Consequently we can write instead of n, and we must now prove that

Consider first the assumption Then or Since furthermore it follows that From it follows that that is,

which is By virtue of the assumption made, therefore, necessarily

Consider next the assumption According to the assumption that we have that is,

hence Here the number μ is uniquely determined. Now I introduce a new descriptive function f′, which is defined thus: if and 331 Further, We must then show merely that f′ satisfies the same conditions as f.

From it follows that since in this case Besides, clearly both f′(μ) and f′(m) are Thus

From it follows that

whence which is Thus from it follows that also.

According to the assumption, holds. If we have

then it follows immediately that If we have

then

holds and consequently Similarly if

Finally,

yields

and therefore also

and consequently Thus the proposition

is true.

Remark. When a certain class of objects is given, one will be tempted to say: that these objects are n in number, n being finite, means that a one-to-one mapping of these objects onto the first n numbers exists. But an apparent logical variable (the mapping) occurs in this definition, and there is no a priori reason to expect that the domain over which this variable ranges is finite, unless one has in advance a theorem asserting that the number of possible mappings is finite. From the strictly finitist point of view adopted here, therefore, such a theorem would first have to be proved if the 332 notion of cardinality is to be definable for the objects in question. This seems to be a vicious circle, but it is not: we do not need the general definition, given above, of the notion of cardinality in order to establish a special theorem asserting that certain objects are n in number, for we can establish such a theorem by actually giving a mapping; in this way we avoid treating the mapping as a logical variable. Thus even in the cases mentioned we can first establish a special theorem to the effect that the number of mappings that are possible at all is finite and after that give the general definition of the notion of cardinality for classes of objects.

For any class, the number of positive integers that are and belong to that class can be given in a general way by a function definable in the following manner.

Let U be an arbitrary propositional function; I state5

Definition 26. and

In words: The descriptive function NU(x) will have the value 1 or 0 for according to whether U(1) is true or not. Furthermore will be equal to or NU(n) according to whether is true or not.

It is easy to show that NU(n) then in fact gives the number of numbers for which U(x) is true. I do not go into this more closely here.

It is frequently the case that certain objects are numbered by means of integers, but in such a way that several numbers are assigned as subscripts to each object. The number of distinct objects among them can then be given by means of a function T(x) that I now define.

Let the objects be we state

Definition 27.

Furthermore, by means of the function Min(U, n), defined on page 329, a uniquely determined choice of a complete system of representatives of distinct objects a can be given. Besides, it is possible to define the associated frequencies [Häufigkeits-zahlen], which indicate how often each distinct object occurs in the sequence and so on. I do not want to elaborate this any further here.

CONCLUDING REMARK

This paper was written in the autumn of 1919, after I had studied the work of Russell and Whitehead. It occurred to me that already the use of the logical variables that they call "real" would surely suffice to provide a foundation for large parts of mathematics. (In this connection, then, it must be noted that apparent variables ranging over finite domains can be removed by means of recursive definitions.) The justification for introducing apparent variables ranging over infinite domains therefore seems very problematic; that is, one can doubt that there is any justification for the actual infinite or the transfinite.

On the other hand, I myself am no longer satisfied with the way in which the 333 logical elaboration proceeds here, since by following the pattern of Russell and Whitehead’s work I made it too cumbersome from the purely formal point of view. Yet, even in providing a foundation for mathematics it is the substance that is important, not the notation. Soon I shall publish another work on the logical foundations of mathematics that is free from this formal cumbrousness.6 But that work, too, is a consistently finitist one; it is built upon Kronecker’s principle that a mathematical definition [Bestimmung] is a genuine definition if and only if it leads to the goal by means of a finite number of trials.

1 The frequently cumbersome formalism of propositional functions in what follows is due to the fact that the present paper was written as a kind of sequel [in Anschluβ] to Russell and Whitehead’s work.

2 I write as one customarily does, to express the fact that a is not equal to b, that is, that holds.

3 Of course, we can, for example, also write

4 [In the German text the matrix of the formula that follows is, erroneously, .]

5 Strictly speaking, the number 0 has not been introduced; but we can make the convention that the cardinality 0 is to mean that there are no "objects".

6 [Never published.]

Contents:

Related Resources

None available for this document.

Download Options


Title: From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931

Select an option:

*Note: A download may not start for up to 60 seconds.

Email Options


Title: From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931

Select an option:

Email addres:

*Note: It may take up to 60 seconds for for the email to be generated.

Chicago: "From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931," From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931 in From Frege to Godel: a Source Book in Mathematical Logic, 1879-1931, ed. Jean Van Heijenoort (Cambridge: Harvard University Press, 1967), Original Sources, accessed March 29, 2024, http://www.originalsources.com/Document.aspx?DocID=4ZDN4SQTKEJ66ET.

MLA: . "From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931." From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931, in From Frege to Godel: a Source Book in Mathematical Logic, 1879-1931, edited by Jean Van Heijenoort, Cambridge, Harvard University Press, 1967, Original Sources. 29 Mar. 2024. http://www.originalsources.com/Document.aspx?DocID=4ZDN4SQTKEJ66ET.

Harvard: , 'From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931' in From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931. cited in 1967, From Frege to Godel: a Source Book in Mathematical Logic, 1879-1931, ed. , Harvard University Press, Cambridge. Original Sources, retrieved 29 March 2024, from http://www.originalsources.com/Document.aspx?DocID=4ZDN4SQTKEJ66ET.