290 Mathematical Logic
Some remarks on axiomatized set theory
THORALF SKOLEM n/a
(1922)
1922 *Einige Bemerkungen zur axiomatischen Begründung der Mengenlehre, Matematikerkongressen i Helsingfors den 4–7 Juli 1922, Den femte skandinaviska matematikerkongressen, Redogörelse (Akademiska Bokhandeln, Helsinki, 1923), 217–232 (290–301 of the present volume).
This is the text of an address delivered before the Fifth Congress of Scandinavian Mathematicians (Helsinki, 4–7 August 1922). It deals with several questions encountered in the axiomatization of set theory and contains eight points, which are listed in the fourth paragraph. Point 2, on Zermelo’s notion "definite property", was discussed in the introductory note to Fraenkel’s paper (above, p. 285).
Point 3 presents a new proof of Löwenheim’s theorem and discusses some of the implications of the theorem for formalized set theory. Löwenheim’s theorem states that, if a formula of the predicate calculus of first order is satisfiable, it is . Skolem had proved the theorem earlier (1920) and generalized it to a denumerably infinite set of formulas. The 1920 proof (see above, pp. 256–259) makes use of the axiom of choice and of a result of Dedekind’s about chains. The new proof dispenses with the axiom of choice and, instead of Dedekind’s result, uses an argument whose first part is already in Löwenheim’s paper. From the satisfiability of the formula both Löwenheim and Skolem conclude that there is, for every n, a solution of the nth level (for a definition of this expression see below, p. 508). At that point Löwenheim states without justification that the formula is (see above, p. 240). Skolem supplies the missing step (which Quine (1955b, p. 254) called the "law of infinite conjunction"), and he does so without using the axiom of choice (the gap is now frequently bridged with the help of König’s infinity lemma (1926, 1927)).
Skolem then uses Löwenheim’s theorem to show that any formalized set theory has a denumerable model. Since natural numbers can be defined in terms of sets (for example, by means of Dedekind’s "chains" or in Zermelo’s way), he sees the possibility that there might be two distinct models of set theory giving rise to two distinct systems of natural numbers. In a later paper (1929, § 7) Skolem comes back to this question in greater detail; then (1933, 1934) he actually exhibits a nonstandard model of arithmetic.
For Skolem the discrepancy between an intuitive set-theoretic notion and its formal counterpart leads to the "relativity" of set-theoretic notions. Thus, two sets are equivalent if there exists a one-to-one mapping of the first onto the second; but this mapping is itself a collection of ordered pairs of elements. If, in a formalized set theory, this collection exists as a set, the two given sets are equivalent in the theory; if it does not, the sets are not equivalent in the theory and, when one set is that of the natural numbers as defined in the theory, the other becomes "nondenumerable". The existence of such a "relativity" is sometimes referred to as the Löwenheim-Skolem paradox. But, of course, it is not a paradox in the sense of an antinomy; 291 it is a novel and unexpected feature of formal systems.
In Point 4 Skolem indicates a limitation of Zermelo’s set theory: it does not ensure the existence of some "large" sets, such as the set where Z_{0} is the set of natural numbers and Z_{i} the power set of If the continuum hypothesis is assumed, this means that all of Zermelo’s sets are of cardinalities less than To remedy this deficiency Skolem proposes a new axiom, the axiom of replacement, which will become a standard part of set theory. At about the same time Fraenkel (1922a, but see also 1921 and 1922) and Lennes (1922) make similar suggestions. (See above, p. 114, line 22, for an early formulation of the axiom of replacement in Cantor.)
In Point 6 Skolem deals with the non-categoricity of Zermelo’s axioms, not, however, by using the Löwenheim-Skolem theorem, but by actually exhibiting various models that are subdomains of some initial model B (assumed to exist). In footnote 9 he invokes this non-categoricity to suggest that set theory is perhaps unable to solve all questions concerning cardinality and, in particular, that the continuum hypothesis may be independent of the axioms of set theory (see also below, p. 368).
These indications do not exhaust the content of a rich and clearly written paper, which when it was published did not receive the attention it deserved, although it heralded important future developments.
The translation is by Stefan Bauer-Mengelberg, and it is printed here with the kind permission of Professor Skolem.
Set theory in its original version led, as we know, to certain contradictions (antinomies), and no one has yet succeeded in giving a clarification of them that has won general acceptance. In view of this threat to set theory, attempts have been made to develop that theory by means of certain fundamental assumptions, or axioms, in such a way that the part presumed to be correct and useful would remain provable while the contradictions would be avoided.
Until now, so far as I know, only one such system of axioms has found rather general acceptance, namely, that constructed by Zermelo (1908a). Russell and White-head, too, constructed a system of logic that provides a foundation for set theory; if I am not mistaken, however, mathematicians have taken but little interest in it. In what follows I therefore concern myself almost exclusively with Zermelo’s axiomatization, and I touch upon Russell and Whitehead’s at only a single point, albeit a rather important one.
Zermelo considers a domain B of objects, among which are the sets. Between these objects there obtain relations of the form (a is an element of b) and of the form ^{1} In this domain, then, seven axioms, for which I refer the reader to Zermelo’s paper, are to be satisfied. I shall use the same numbering and nomenclature for the axioms here as does Zermelo.
In this address I wish to discuss the following eight points:
1. The peculiar fact that, in order to treat of "sets", we must begin with "domains" that are constituted in a certain way;
292
2. A definition, much to be desired, that makes Zermelo’s notion "definite proposition" precise;
3. The fact that in every thoroughgoing axiomatization set-theoretic notions are unavoidably relative;
4. The fact that Zermelo’s system of axioms is not sufficient to provide a foundation for ordinary set theory;
5. The difficulties caused by the nonpredicative stipulations when one wants to prove the consistency of the axioms;
6. The nonuniqueness [Mehrdeutigkeit] of the domain B;
7. The fact that mathematical induction is necessary for the logical investigation of abstractly given systems of axioms;
8. A remark on the principle of choice.
1. If we adopt Zermelo’s axiomatization, we must, strictly speaking, have a general notion of domains in order to be able to provide a foundation for set theory. The entire content of this theory is, after all, as follows: for every domain in which the axioms hold, the further theorems of set theory also hold. But clearly it is somehow circular to reduce the notion of set to a general notion of domain. If, however, it were maintained that only the notion of the single domain B is necessary, hence not a general notion "domain", this consideration could also be applied to the sets themselves; thus, if a proposition should be advanced about some unspecified set, we could say: no general notion "set" is needed, but only the idea of a single set that we assume to be given.
It must be noted, incidentally, that the domain B is not uniquely determined by the axioms (see Section 6 below). Moreover, it will appear clearly from what follows that one cannot undertake logical investigations of such domains without to a certain extent applying set-theoretic considerations to them as well, if, that is, one wishes to follow the purely set-theoretic method and avoid including the notion of number among the fundamental ones.
Furthermore, it seems to be clear that, when founded in such an axiomatic way, set theory cannot remain a privileged logical theory; it is then placed on the same level as other axiomatic theories.
2. A very deficient point in Zermelo is the notion "definite proposition". Probably no one will find Zermelo’s explanations of it satisfactory. So far as I know, no one has attempted to give a strict formulation of this notion; this is very strange, since it can be done quite easily and, moreover, in a very natural way that immediately suggests itself. In order to explain this, and also with a view to later considerations, I mention the five basic operations of mathematical logic here, using Schröder’s notation (1890):
(1_{×}) Conjunction, denoted by a dot or by juxtaposition;
(1_{+}) Disjunction, denoted by the sign +;
(2) Negation, denoted by a bar over the expression to be negated;
(3_{×}) Universal quantification, denoted by the sign Π;
(3_{+}) Existential quantification, denoted by the sign Σ.
As is well known, only three of these five operations are really needed, since (1_{×}) and (1_{+}), like (3_{×}) and (3_{+}), are mutually definable by means of (2).
By a definite proposition we now mean a finite expression constructed from elementary 293 propositions of the formorby means of the five operations mentioned. This is a completely clear notion and one that is sufficiently comprehensive to permit us to carry out all ordinary set-theoretic proofs. I therefore adopt this conception as a basis here.
3. This third point is the most important: If the axioms are consistent, there exists a domain B in which the axioms hold and whose elements can all be enumerated by means of the positive finite integers.
To prove this I must first explain a theorem proved by Löwenheim (1915). By a first-order proposition [Zählaussage] (Löwenheim says "first-order expression" ["Zählausdruck"]) is meant a finite expression constructed from class and relative coefficients in the sense of Schröder (1895) by means of the five logical operations mentioned above. Then Löwenheim’s theorem reads as follows:
If a first-order proposition is satisfied in any domain at all, it is already satisfied in a denumerably infinite domain.
Löwenheim’s proof is unnecessarily complicated, and moreover the complexity is rather essential to his argument, since he introduces subscripts when he expands infinite logical sums or products; in this way he obtains logical expressions with a nondenumerably infinite number of terms. Thus he must make a detour, so to speak, through the nondenumerable. In a previous paper (1920) I therefore gave a simplified proof of Löwenheim’s theorem, along with some generalizations of it. One of these generalizations, which is of importance here, reads:
Let there be given an infinite sequenceof first-order propositions numbered with the integers; if, now, it is consistent to assume that all these propositions hold simultaneously, they can all be simultaneously satisfied in the infinite sequence of the positive integers, 1, 2, 3, . . ., by a suitable determination of the class and relation symbols occurring in the propositions.
I proved these theorems by forming an intersection and using the principle of choice. The formation of the intersection can be avoided immediately by use of a recursive definition; but here, where we are concerned with an investigation in the foundations of set theory, it will be desirable to avoid the principle of choice as well. Therefore I now indicate very briefly how this can be done. It will also appear from the proof that general set-theoretic notions are unnecessary for the understanding of the content of these theorems.
Since the proof of the generalization mentioned can very easily be carried out in the same way as the proof of Löwenheim’s theorem, I will concern myself only with the latter here.
As I have shown (1920), every first-order proposition can be put into what I called a normal form, provided some auxiliary classes and relations are defined. A first-order proposition in normal form has the following structure:
where is a proposition constructed from class and relation symbols (class and relative coefficients in the sense of Schröder) by means of the first three of the logical operations mentioned above. Let, therefore, such a first-order proposition in normal form be given; we assume it to be consistent.
294
The proof proceeds by way of an infinite sequence of steps. For the first step we choose Then it must be possible to choose among the numbers in such a way that is satisfied. Thus we obtain one or more solutions of the first step, that is, assignments determining the classes and relations in such a way that is satisfied. The second step consists in choosing, for every permutation with repetitions of the numbers taken m at a time, with the exception of the permutation 1, 1, . . ., 1, already considered in the first step. For at least one of the solutions obtained in the first step, it must then be possible, for each of these permutations, to choose among the numbers in such a way that, for each permutation taken within the segment of the number sequence, the proposition holds for a corresponding choice of taken within the segment Thus from certain solutions gained in the first step we now obtain certain continuations, which constitute solutions of the second step. It must be possible to continue the process in this way indefinitely if the given first-order proposition is consistent.
In order now to obtain a uniquely determined solution for the entire number sequence, we must be able to choose a single solution from among all those obtained in a given step. To achieve this, we can always take the first from all of the solutions obtained in an arbitrary step, once they have been ordered in a sequence in the following way.
The relative coefficients occurring in the given first-order proposition can be linearly ordered so that the relative coefficients formed within the segment 1, 2, . . ., n of the number sequence precede all new relative coefficients that are formed within the segment For any two different solutions L and L′ of an arbitrary step, write if and only if is equal to 0 in L and 1 in L′, where is the first relative coefficient having different values in L and L′.^{2} From and it then follows that we can also readily see that for two solutions L_{n} and of the nth step that are, respectively, continuations of the solutions L_{v} and of the vth step implies
Let be the solutions of the nth step. If we now form the sequence of the first solutions, we can verify without difficulty that they converge in the logical sense. For let L_{1,n} be a continuation of Then, if But, since the number can only have the values 1 to e_{v}, it must remain constant for all sufficiently large n. Thus we can obtain as "limit" the fact that the first-order proposition is satisfied in the domain of the entire number sequence. Q. e. d.
Now the previously mentioned generalization of Löwenheim’s theorem can be applied in the present case, that of Zermelo’s axiom system, in the following way.
The definite first-order propositions can be enumerated according to their form by means of the positive integers; for we can order them according to how many symbols for sets occur in them, and for a given number of such symbols there is only a finite number of propositions, so that these in turn can be thought of as ordered 295 according to some rule. Consequently, Axiom III (axiom of separation) can be replaced by an infinite sequence of simpler axioms—which, like the rest of Zermelo’s axioms, are first-order propositions in the sense of Löwenheim—containing the two binary relations ε and =. We may then conclude: If Zermelo’s axiom system, when made precise, is consistent, it must be possible to introduce an infinite sequence of symbols 1, 2, 3, . . . in such a way that they form a domain B in which all of Zermelo’s axioms hold provided these symbols are suitably grouped into pairs of the form
This is to be understood in the following way: one of the symbols 1, 2, 3, . . . will be the null set (that is, among the remaining symbols there is none that has the relation ε to the symbol in question); if a is one of the symbols, then {a} is another;^{3} if M is one of the symbols, then UM, SM, and DM are others;^{4} and so forth.
So far as I know, no one has called attention to this peculiar and apparently paradoxical state of affairs. By virtue of the axioms we can prove the existence of higher cardinalities, of higher number classes, and so forth. How can it be, then, that the entire domain B can already be enumerated by means of the finite positive integers? The explanation is not difficult to find. In the axiomatization, "set" does not mean an arbitrarily defined collection; the sets are nothing but objects that are connected with one another through certain relations expressed by the axioms. Hence there is no contradiction at all if a set M of the domain B is nondenumerable in the sense of the axiomatization; for this means merely that within B there occurs no one-to-one mapping Φ of M onto Z_{0} (Zermelo’s number sequence). Nevertheless there exists the possibility of numbering all objects in B, and therefore also the elements of M, by means of the positive integers; of course, such an enumeration too is a collection of certain pairs, but this collection is not a "set" (that is, it does not occur in the domain B). It is also clear that the set UZ_{0} cannot contain as elements arbitrarily definable parts of the set Z_{0}. For, since the elements of UZ_{0} are to be found among the objects of the domain B, they can be numbered with the positive integers just like the elements of Zermelo’s number sequence Z_{0}, and in a well-known way a new part of Z_{0} can then be defined; but this part will not be a set, that is, will not belong to B.
Even the notions "finite", "infinite", "simply infinite sequence", and so forth turn out to be merely relative within axiomatic set theory. A set M is finite, according to Dedekind’s definition, if it is not equivalent to any of its proper subsets. But the fact that the axioms hold does not rule out the possibility that we can define, first, parts of M that are not subsets or, second, correspondences that are not mappings, that is, "sets" of pairs. It is therefore quite possible that, within a domain B in which Zermelo’s axioms hold, there exist sets that are "finite" in the sense of Dedekind and for which there are one-to-one mappings onto some of their proper parts; but these "mappings" are not sets of the domain.
Likewise, the notion "simply infinite sequence" or that of the Dedekind "chain" has only relative significance. If Z is a set having the property required by Axiom VII, Zermelo’s number sequence Z_{0} is defined as the intersection of all subsets of Z 296 that have the same (chain) property. But being a subset of Z is not merely to be in some way definable, and nothing can prevent a priori the possibility that there exist two different Zermelo domains B and B′ for which different Z_{0} would result.
These peculiar relativities could easily be illustrated in more detail for simpler axiom systems; but I cannot go into that, lest I make this address too prolix.
Thus, axiomatizing set theory leads to a relativity of set-theoretic notions, and this relativity is inseparably bound up with every thoroughgoing axiomatization.
The relativity is due to the fact that to be an object in B means something different and far more restricted than merely to be in some way definable. That this relativity must be inseparably bound up with every thoroughgoing axiomatization is clear; for it rests upon the general theorems of mathematical logic mentioned above. In order to obtain something absolutely nondenumerable, we would have to have either an absolutely nondenumerably infinite number of axioms or an axiom that could yield an absolutely nondenumerable number of first-order propositions. But this would in all cases lead to a circular introduction of the higher infinities; that is, on an axiomatic basis higher infinities exist only in a relative sense.
With a suitable axiomatic basis, therefore, the theorems of set theory can be made to hold in a merely verbal sense, on the assumption, of course, that the axiomatization is consistent; but this rests merely upon the fact that the use of the word "set" has been regulated in a suitable way. We shall always be able to define collections that are not called sets; if we were to call them sets, however, the theorems of set theory would cease to hold.
4. It is easy to show that Zermelo’s axiom system is not sufficient to provide a complete foundation for the usual theory of sets. I intend to show, for instance, that if M is an arbitrary set, it cannot be proved that and so forth ad infinitum form a "set". To prove this I introduce the notion "level" ["Stufe"] of a set. Such sets as I call sets of the first level; they are characterized by the fact that there exists a nonnegative integer n such that ^{5} The set Z_{0} (Zermelo’s number sequence) already constitutes an example of a set that is not of the first level, since, for every n, By a set M of the second level I mean one that is not itself of the first level but for which there exists a nonnegative integer n such that all elements of S^{n}M are sets of the first level. Thus Z_{0} is a set of the second level. In a similar way sets of the third, fourth, and higher levels can be defined. We need not discuss whether with every set a level number is associated.
Now let a domain B in which the axioms hold be given. Then the sets in B that are of the first or second level form a partial domain B′, and it is easy to see that the axioms must hold in B′ too. The set Z_{0} belongs to B′; if the infinite sequence formed a set M in B′, however, it would clearly not be of the second level but of the third, and such a set just does not occur in B′. For it is evident that, for every n, S^{n}M will contain the set Z_{0} as an element. Thus the sets do not form the elements of a set in B′, even though Zermelo’s axioms hold in B′; that is to say, the existence of such a set is not provable.
297
In order to remove this deficiency of the axiom system we could introduce the following axiom: Let U be a definite proposition that holds for certain pairs (a, b) in the domain B; assume, further, that for every a there exists at most one b such that U is true. Then, as a ranges over the elements of a set M_{a}, b ranges over all elements of a set M_{b}.
The addition of such an axiom does not, of course, change anything so far as the relativity explained above is concerned.^{6}
5. It has presumably not yet been proved that Zermelo’s axiom system is consistent, and it will no doubt be very difficult to do so. In particular, the nonpredicative stipulations governing the formation of sets will cause difficulties. It is not far-fetched to think of the axioms as generating principles of some sort; we generate new sets according to certain rules from sets already known. If, now, the formation of sets were a mere matter of constructing each new set solely from a finite number of prior sets, we could easily ascertain through an infinite process whether the axioms are consistent. But the difficulty is that we have to form some sets whose existence depends upon all sets. We then have what is called a nonpredicative definition. Poincaré criticized this kind of definition and regarded it as the real logical weakness of set theory.^{7}
In Russell and Whitehead’s system this point has been formally taken into account, namely, in the theory of what they call the logical types, but they, too, simply content themselves with circumventing the difficulty by introducing a stipulation, the axiom of reducibility. Actually, this axiom decrees that the nonpredicative stipulations will be satisfied. There is no proof of that; besides, so far as I can see, such a proof must be impossible from Russell and Whitehead’s point of view as well as from Zermelo’s. For it could probably be carried out only through the actual construction of a domain B with the desired properties by a procedure similar to that used in the proof of Löwenheim’s theorem given above. There, however, the idea of the finite and the recursive mode of thought are employed. But neither in Russell and 298 Whitehead’s system nor in Zermelo’s are these notions supposed to be taken as basic; rather, they in turn are supposed to have their foundation in set theory. Thus we would come to a vicious circle.
It is clear that Zermelo’s Axioms I–VI (VII excluded) are consistent; for with these axioms the domain B need contain only finite sets, formed by means of Axiom II alone.
6. I do not know whether anyone has proved rigorously that Zermelo’s domain B is not uniquely determined by his axioms. That it is not so determined is a priori very plausible. But it does not suffice (as it would, for example, in the case of a commutative field [Rationalitätsbereich]) to say that we need only adjoin one new object in order to obtain a more comprehensive domain by means of the axioms; for we could, after all, imagine (though it is very improbable) that the axioms might then lead to contradictions, even if this were not the case before. I now present some of my reflections on this question.
If M is an arbitrary set, we can construct sequences of the form
I call them descending ε-sequences.
We now see almost immediately that in a domain B the sets M for which every ε-sequence necessarily terminates after a finite number of terms must form a part B′ of B in which the axioms still hold. If now B′ is a proper part of B, that is, if there are sets in B for which infinite descending ε-sequences exist, we already have two distinct Zermelo domains B and B′. But if every ε-sequence of an arbitrary set M in B terminates after a finite number of terms, the sets for which every ε-sequence terminates with the null set again form a part B′ of B in which the axioms hold. If, therefore, B and B′ are different, we again have two distinct Zermelo domains.
Let us now consider a domain B for whose sets every ε-sequence is finite and terminates with 0. Then with every set M we can associate a corresponding ε-tree [ε-Verzweigungssystem] that specifies how M is built up of elements, these in turn of elements, and so forth. Such a tree, then, is so constituted that infinitely many branches may indeed originate at one node; but, if we follow a connected sequence of branches (an ε-sequence), we reach 0 after a finite number of steps. If, now, a is an object not belonging to B, we can form an extended Zermelo domain B′ containing a as follows.
Let M be an arbitrary set, N an arbitrary subset of with n arbitrary, F the tree associated with M, and G the part of this system that consists of the points corresponding to N. Then from F we form a tree F′ by inserting into all points of G a branch ending with a; that is, we adjoin a as a new element to each element of N. The trees thus obtained can then be regarded as sets of a more comprehensive domain B′.
We could now prove, by going through the axioms, that they hold for B′ if they hold for B. The proof is very easy for all the axioms except Axiom III, for which the general formulation of the proof becomes rather involved. I therefore do not go into the matter in more detail here.
It would in any case be of much greater interest if we could prove that a new 299 subset of Z_{0} could be adjoined^{8} without giving rise to contradictions; but this would probably be very difficult.^{9}
7. In the investigation of an axiom system with respect to the logical dependence of the individual axioms upon one another, it has been regarded as sufficient simply to take other theories as a basis. But we cannot always be so fortunate as to be able to proceed on the basis of theories developed previously; we must insist on having a procedure that allows us to investigate the logical character of the axioms directly.
That B follows from A, if these are statements concerning certain objects, would, of course, from the point of view of set theory have to be regarded as follows: always, that is, for every set, the proposition holds. It is, of course, often possible to prove this by means of set-theoretic axioms; but in the first place the question of the consistency of the axioms of set theory then arises, and in the second place we must take into consideration the fact that, whenever an axiomatic foundation has been provided, set-theoretic notions are relative, with the result that collections may yet be definable for which does not hold. Now, if we were to investigate the axioms of set theory themselves in this way, we would have to prove that "domains" exist for which the axioms in question hold. If we do not again want to take axioms for domains as a basis (and so on ad infinitum), I see no other way out than to pass on to considerations such as those employed above in the proof of Löwenheim’s theorem, considerations in which the idea of the finite integer is taken as basic.
Besides, the notion that really matters in these logical investigations, namely, "proposition following from certain assumptions", also is an inductive (recursive) one: the propositions we consider are those that are derivable by means of an arbitrary finite number of applications of the axioms. Thus the idea of the arbitrary finite is essential, and it would necessarily lead to a vicious circle if the notion "finite" were itself based, as in set theory, on certain axioms whose consistency would then in turn have to be investigated.
Set-theoreticians are usually of the opinion that the notion of integer should be defined and that the principle of mathematical induction should be proved. But it is clear that we cannot define or prove ad infinitum; sooner or later we come to something that is not further definable or provable. Our only concern, then, should be that the initial foundations be something immediately clear, natural, and not open to question. This condition is satisfied by the notion of integer and by inductive inferences, but it is decidedly not satisfied by set-theoretic axioms of the type of Zermelo’s or anything else of that kind; if we were to accept the reduction of the former notions to the latter, the set-theoretic notions would have to be simpler than mathematical induction, and reasoning with them less open to question, but this runs entirely counter to the actual state of affairs.
300
In a paper (1922) Hilbert makes the following remark about Poincaré’s assertion that the principle of mathematical induction is not provable: "His objection that this principle could not be proved in any way other than by mathematical induction itself is unjustified and is refuted by my theory." But then the big question is whether we can prove this principle by means of simpler principles and without using any property of finite expressions or formulas that in turn rests upon mathematical induction or is equivalent to it. It seems to me that this latter point was not sufficiently taken into consideration by Hilbert. For example, there is in his paper (bottom of page 170), for a lemma, a proof in which he makes use of the fact that in any arithmetic proof in which a certain sign occurs that sign must necessarily occur for a first time. Evident though this property may be on the basis of our perceptual intuition of finite expressions, a formal proof of it can surely be given only by means of mathematical induction. In set theory, at any rate, we go to the trouble of proving that every ordered finite set is well-ordered, that is, that every subset has a first element. Now why should we carefully prove this last proposition, but not the one above, which asserts that the corresponding property holds of finite arithmetic expressions occurring in proofs? Or is the use of this property not equivalent to an inductive inference?
I do not go into Hilbert’s paper in more detail, especially since I have seen only his first communication. I just want to add the following remark: It is odd to see that, since the attempt to find a foundation for arithmetic in set theory has not been very successful because of the logical difficulties inherent in the latter, attempts, and indeed very contrived ones, are now being made to find a different foundation for it—as if arithmetic had not already an adequate foundation in inductive inferences and recursive definitions.
8. So long as we are on purely axiomatic ground there is, of course, nothing special to be remarked concerning the principle of choice (though, as a matter of fact, new sets are not generated univocally by applications of this axiom); but if many mathematicians—indeed, I believe, most of them—do not want to accept the principle of choice, it is because they do not have an axiomatic conception of set theory at all. They think of sets as given by specification of arbitrary collections; but then they also demand that every set be definable. We can, after all, ask: What does it mean for a set to exist if it can perhaps never be defined? It seems clear that this existence can be only a manner of speaking, which can lead only to purely formal propositions—perhaps made up of very beautiful words—about objects called sets. But most mathematicians want mathematics to deal, ultimately, with performable computing operations and not to consist of formal propositions about objects called this or that.
Concluding remark
The most important result above is that set-theoretic notions are relative. I had already communicated it orally to F. Bernstein in Göttingen in the winter of 1915–16. There are two reasons why I have not published anything about it until now: first, I have in the meantime been occupied with other problems; second, I believed that it was so clear that axiomatization in terms of sets was not a satisfactory ultimate 301 foundation of mathematics that mathematicians would, for the most part, not be very much concerned with it. But in recent times I have seen to my surprise that so many mathematicians think that these axioms of set theory provide the ideal foundation for mathematics; therefore it seemed to me that the time had come to publish a critique.
^{1} If all objects of the domain are sets this relation can be reduced to the relation by means of the axiom of extensionality. For, if a and b are sets, then (see the definitions in Section 2) means the same as
^{2} Here 0 and 1 are Schröder’s propositional values; 0 means "false" and 1 means "true".
^{3} {a} is the set containing a and only a as an element.
^{4}UM, SM, and DM are, respectively, the power set, the union set, and the intersection set of M.
^{5}S^{n}M is the nth union; thus SM is the (first) union associated with M, and
^{6} That this axiom indeed suffices for the proof of the existence of sets of the type mentioned can be seen as follows. (I must content myself here with the sketch of a proof.)
The segments (as they are called) A of Z_{0} form, according to Axioms III and IV, the elements of a set. On the other hand, we can consider sets C that have the following, obviously definite properties:
(1) C is finite;
(2) ;
(3) If there exists an such that except if
The sets C are obviously of the form
Furthermore it can be shown by means of inductive inferences (which here are in turn provable on the basis of the definition of Z_{0} as an "intersection" or a "chain") that every set C is equivalent to one and only one segment A of Z_{0}, and conversely. If we form the proposition C satisfies (1), (2), and (3); A is a segment of Z_{0}", it too is definite and of the kind required by the axiom mentioned. Since a set exists that contains all segments A of Z_{0}, the sets C according to this axiom also constitute all the elements of a set T. Then the associated union, ST, is the desired set, which contains and so forth ad infinitum, as elements.
^{7} A typical nonpredicative stipulation is, for example, that the intersection of all sets that have an arbitrary definite property E again be a set. This in fact follows from the axioms. For, first, the intersections [M, M′], where M is a fixed set having the property E while M′ ranges over all sets having this property, constitute according to Axioms III and IV all the elements of a set T; this set, then, is already nonpredicatively introduced. Second, the intersection DT associated with T must obviously be the intersection of all sets having the property E.
^{8} As was explained above (Section 3), B, after all, does not have to contain every "definable" subset of Z_{0}.
^{9} Since Zermelo’s axioms do not uniquely determine the domain B, it is very improbable that all cardinality problems are decidable by means of these axioms. For example, it is quite probable that what is called the continuum problem, namely, the question whether is greater than or equal to is not solvable at all on this basis; nothing need be decided about it. The situation may be exactly the same as in the following case: an unspecified commutative field is given, and we ask whether it contains an element x such that This is just not determined, since the domain is not unique.