Consequences of the axiom of choice.

*(English)*Zbl 0947.03001
Mathematical Surveys and Monographs. 59. Providence, RI: American Mathematical Society (AMS). 432 p. (1998).

This book undertakes the formidable task of collecting an awesome amount of consequences of the axiom of choice (AC), published in hundreds of books and journals during the last century. The authors use two versions of set theory: Zermelo-Fraenkel set theory ZF and Zermelo-Fraenkel set theory ZF\(^0\) allowing urelements (for details see below). We will refer here to both versions as basic set theory if no confusion can arise.

While the standard work “Equivalents of the axiom of choice. Second ed.” by H. Rubin and J. E. Rubin (North-Holland, Amsterdam) (1985; Zbl 0582.03033) deals almost exclusively with sentences equivalent to AC, in this book the centre of interest is statements of set theory, called forms of the axiom of choice, that depend essentially on some “choice argument”, but do not imply full AC over basic set theory (provided basic set theory is consistent). There are two exceptions: Form 0 and its equivalents are theorems of basic set theory (without “choice”), and Form 1 and its equivalents imply the full axiom of choice.

The authors do not just list the sentences and inform the reader where he can find them in the literature. To save the reader the enormous effort of tracking them down in books and journals, in Part III (Notes) a great number of relevant definitions, proofs of related theorems, and other helpful information can be found. The authors also created two extensive tables which show—using a special code carefully explained in the Introduction—the relative strength of the various consequences of AC with respect to basic set theory.

This book differs from other mathematical books with several features; two of them are novelties reflecting our electronic age:

Firstly, it is of an encyclopaedic character listing 946 sentences, partitioned into 384 classes modulo logical equivalence (over basic set theory).

Secondly, in addition to the six printed parts of the book there is a diskette enclosed consisting of Part VII which contains the above-mentioned two tables.

Thirdly, the authors have installed a website on the Internet (mentioned in the Introduction), which provides the reader with the latest information about errors, corrections, new results etc. as soon as this is known to the authors. This feature is not without pitfalls as we will explain later on. Here we only stress the fact that the stream of information floating in via the Internet makes some of the material in the book, as well as on earlier websites, obsolete very fast. Thus, the above-mentioned 946 forms of the axiom of choice are the forms listed in the book. In order to be on sound ground we will always refer to the book in this review, unless stated otherwise.

It is a mathematical commonplace that the axiom of choice is the most discussed statement in the history of mathematics, second only to Euclid’s parallel postulate. But while the latter is no issue of controversy or even of serious investigation any more, the discussion and investigation of AC lingers on. The motives for this activity have changed throughout the last hundred years—not always in the same straight direction, but rather back and forth. For detailed and carefully investigated information see G. H. Moore’s fine book “Zermelo’s axiom of choice” (Springer-Verlag, New York) (1982; Zbl 0497.01005). The contrary views about the axiom of choice are strikingly demonstrated by an experience of Tarski’s (we follow here G. H. Moore [loc. cit.]). Tarski sent Lebesgue a note that the statement “\(\mathfrak m = \mathfrak m^2\) for every infinite \(\mathfrak m\)” is equivalent to the axiom of choice, and asked him to submit it to the Comptes Rendus. Lebesgue returned the note on the grounds that he opposed the axiom, but suggested sending it to Hadamard. But Hadamard also returned the note, saying that, since the axiom was true, what was the point of proving it from the above statement? The theorem, together with many others, was published in 1924 [A. Tajtelbaum-Tarski, Fundam. Math. 5, 147–154 (1924; JFM 50.0135.01)]. The non-constructive character and the controversial role of AC explain why this review contains, in contrast to others, several remarks about the “underlying philosophy” mathematicians have accepted in this field.

Before reviewing this extensive collection of statements in detail, it might be in order to discuss shortly the purpose this book serves and who might be interested in it.

Hence, who will benefit from this book? In the Introduction the authors themselves mention that in an article published in 1988 the question was raised whether the axiom of choice for countable families of countable sets implies the countable union theorem. In 1992 one of the authors of this book answered this question negatively. The reviewer of the 1992 article, however, pointed out that this result had already been obtained and published in 1974. The authors write in the Introduction, “This book was begun with the primary purpose of preventing such occurrences.” Thus, mathematical researchers who are interested in obtaining results about the relative strength of mathematical statements which require some (or full) “choice”, should find this book helpful for avoiding independent multi-publications of the same results. This will include set theorists as mentioned in Howard-Rubin’s example. Who else might benefit from this book? We will come back to this question later on, but want to stress here already that many mathematical practitioners are also very much interested in the question how much choice is needed to prove a particular theorem. For instance, when does sequential compactness imply compactness in \(\mathbb R\)? These practitioners believe that they get a better understanding of a particular mathematical situation if a theorem is proved under weaker assumptions, even if all these assumptions are consequences of the popular (full) axiom of choice. Applications of “the” axiom of choice are replaced, whenever possible, by weaker consequences, e.g., “local” versions of AC. From this point of view, shared by the reviewer, it is not reasonable to prove, e.g., the existence of a transcendence basis of \(\mathbb C\) over \(\mathbb Q\) by using “the” Zorn’s lemma: This is simply brute overkill! What is needed as a handy condition is the existence of a well-ordering of \(\mathbb C\) (or \(\mathbb R\)). Admittedly, this is no weak property, but still much weaker than the existence of well-orderings for all sets in the universe. There is no doubt that a set theorist can say off the cuff which local version of Zorn’s lemma is actually needed in the above-mentioned case, but many mathematical practitioners are at a loss when they are faced with this question. By the way, the classical proof of the existence of an algebraic closure of arbitrary field \(K\) is just based on a well-ordering of \(K\); hence, if \(K = \mathbb Q\), then no choice principle is needed at all (see E. Steinitz [J. Reine Angew. Math. 137, 167–309 (1910; JFM 41.0445.03)]).

An early appearance of a “local” version of AC is W. Sierpiński’s choice principle: Every \(\omega \)-sequence of non-empty disjoint subsets of \(\mathbb R\) has a subsequence with a choice function [C. R. Acad. Sci., Paris, Sér. A-B 163, 688–690 (1916; JFM 46.0295.04)]. This principle is equivalent to AC\({}_{\omega}(\mathbb R)\) (= Form 94: Every denumerable family of non-empty sets of reals has a choice function).

Though in the early days of the AC-controversy the question of consistency played a role, up to the present time the main concern has been about the non-constructive character of the axiom of choice (it is the only Zermelo axiom—other than extensionality—which is not an instance of the comprehension schema). We will come back to this point at the end of the review, and continue here with a survey of the content:

Part I: Numerical list of forms contains the complete listing of all forms the authors have collected, partitioned into 384 classes modulo logical equivalence. We will also refer to these equivalence classes as “groups”. Each group is headed by some particular statement, which we may call its “master form” here, and which is given a number from 0 to 383. Each master form is followed by all equivalent statements the authors have collected, and which they also call “forms of the axiom of choice”. Statements of the same equivalence class are marked by letters added to the number of the master form; for instance, Form 14 is followed by forms [14 A], [14 B], etc. The authors point out in the Introduction that the forms (other than Form 0 and Form 1) are numbered in the order they encountered them in the literature. Thus, forms the reader would view as closely related might appear far apart in the list. But you get used to this soon, and you keep many “interesting” numbers in your head, as, e.g., Form 8 (AC\({}_{\omega}\)), Form 14 (ultrafilter theorem), and Form 43 (axiom of dependent choices). The numeric resp. alphanumeric denotation of a form is sometimes followed by a special notation and a name [e.g., Form 31. \(UT(\aleph_0,\aleph_0,\aleph_0)\): The countable union theorem], then by the formulation of the statement and (mostly) a reference to the article where this result can be found in the literature. Finally, a reference to a note in Part III is often added to provide further information (for details see below).

Part II: Topical list of forms arranges the bulk of the forms not in groups of logically equivalent statements, but according to the topic, i.e., the mathematical subject matter they are dealing with. There are 12 main sections as, e.g., Algebraic Forms, Cardinal Numbers, Topological Forms (including Properties of \(\mathbb R\)), etc.; some of them are further divided into subsections.

For each topic the forms appear in the same order as in Part I. It can happen that a certain form belonging to several different topics is listed more than once, while others which cannot conveniently be classified do not appear at all in the Topical List.

Part III: Models is the gem of the book for those readers who are not only interested in the independence results, but who also want to get information about the models used in the proofs. This part, headed by a very helpful table of contents, consists of two sections: § 1. Cohen models, denoted (mostly) by \(\mathcal M_k\), and § 2. Fraenkel-Mostowski models, i.e., permutation models, denoted by \(\mathcal N_k\), \(0 < k\in \omega\). For each model listed there is a short description, including forms that are “true” resp. “false” in the model and references to the proofs. All descriptions end with two lists, one with all forms known to be true in the model, and the other with all forms known to be false. The authors have collected and pass over to the reader an impressive amount of information.

Part IV: Notes is a collection of 149 notes referred to in other parts of the book. As in Part III, this part is also headed by a very useful table of contents providing keyword descriptions of the subject matter of every note. The authors usually omit proofs readily available in the literature. If this is not the case—according to the authors’ judgement—proofs are included together with necessary definitions etc. Since the authors refer, as far as possible, to the original literature and its wording, definitions of the same notions might appear in different notes with different formulations.

Some notes also contain new results of the authors as well as brief expositions of essential theorems as, e.g., the transfer theorems of Jech-Sochor and Pincus in Note 103, and a summary of transfer results in Note 18.

Part V: References for Relationships between Forms provides a bulk of information about the status of relations between forms: implication, non-implication or “unknown”. This part has an extensive introduction in which the special code used to indicate the status is carefully explained and demonstrated by examples, e.g., “0” means “The status of the implication is unknown”; “1” means “The implication is provable”; “2” means “The implication is provable and this follows from implications whose code numbers are 1”; “3” means “The implication is not provable in ZF”, and so on till code number “7”. If an implication or non-implication holds, there is mostly a reference to the literature and/or a note. In the case of a non-implication an appropriate model is mentioned; if a ZF-independence result is obtained using a Fraenkel-Mostowski model plus transfer, the name of the permutation model is followed by “T”, e.g., (N2T). If some form does not imply another form in ZF\({}^0\), but does so in ZF, this is also mentioned (e.g., Form 91: the power set of a well-ordered set can be well-ordered).

Part VI: Bibliography begins with a very helpful list of abbreviations of journals (3 pages), followed by a listing of all articles and books used in the book arranged alphabetically by author, and for each author ordered by date of publication.

The printed book ends with a subject index followed by an author index. Both are fortunately very detailed.

Part VII contains two tables (table 1 and table 2) on an enclosed diskette, each of 128 pages as printed out by the reviewer. Each table is a square matrix with as many rows and columns as there are forms (384 in the book, i.e., 147456 entries!). The elements of table 1 are code numbers from 0 to 7 (see above) and reflect the status of the relation between the corresponding forms. The non-zero entries of table 2 are form numbers. These two tables working together reflect the authors’ most ambitious intention to give a complete description of the quasi-order of logical implication between all listed forms of the axiom of choice; moreover, the authors want to inform the reader about the sources in the literature providing him with the proofs. If the code number is 1, 3, or 5, then there should be a direct reference in Part V. If the code number is 2, 4, or 6, then table 2 tells the reader how to find a reduction to implications and non-implications referenced in Part V. This procedure is straightforward, but sometimes lengthy. Example: It is easy to see that Form 94 (= AC\({}_{\omega}(\mathbb R)\)) implies Form 13 (every infinite subset of the reals is Dedekind-infinite). What about the converse \(13\, \longrightarrow 94\)? The entry \(\langle\)13,94\(\rangle\) in table 1 (i.e., the matrix element in row 13 and column 94) is code number 4 (= “the implication is not provable in ZF and this follows from implications whose code numbers are 1 or 3”). Hence, we know that implication \(13\, \longrightarrow 94\) is unprovable in ZF, but where can we find the proof? Well, by switching back and forth from one table to the other we can break down non-implication \(13\, \nrightarrow 94\) into the pieces \(94\, \longrightarrow 5\), \(3\, \longrightarrow 9\), \(9\, \longrightarrow 13\), and \(3\, \nrightarrow 5\), all with references in Part V. Thus, we obtain non-implication \(13\, \nrightarrow 94\), together with complete information of how to prove it.

After having surveyed the content of the book, we will continue to comment on the various parts. Before that, however, we want to point out two pitfalls to the innocent reader:

I. As we mentioned above, the authors use two versions of set theory. ZF is the usual system for Zermelo-Fraenkel set theory, and with ZF\({}^0\) the authors denote an axiom system which differs from ZF by allowing urelements (atoms). Extensionality holds for sets, and a modified axiom of foundation (regularity) requires that every non-empty set without atoms contains an \(\in\)-minimal element. Thus, every “pure” set, i.e., every set whose transitive closure consists of sets, is well-founded, and sets like \(x = \{x\}\) are excluded. This system should not be mixed up with an axiom system which is sometimes also denoted by ZF\({}^0\) in the literature. The latter axiom system, which we will denote here by ZF\({}^{-}\) in order to avoid confusion, is obtained from ZF by just dropping foundation; and ZF\({}^{-}\) (but not Howard-Rubin’s ZF\({}^0\)) can consistently be extended by adding Boffa’s axiom of superuniversality, which is a cornerstone in the abstract framework for nonstandard mathematics (see, e.g., D. Ballard [Foundational aspects of “non” standard mathematics (Contemp. Math. 176, Am. Math. Soc., Providence, RI) (1994; Zbl 0810.03054)]).

II. The same form number may denote one statement in the book and another one on a website. So, e.g., when Form 338 (every second countable metric space is Lindelöf) turned out to be equivalent to Form 94 [AC\({}_{\omega}(\mathbb R)\)], it was given the new number [94 J], whereas some time later the statement UT(\(\aleph_0,\aleph_0,\)WO) was introduced as Form 338. A reader who does not carefully keep track of the changes of numbers (and consequently those of the tables) could get confused. An example: implication \(338\, \rightarrow 34\) and non-implication \(338\, \nrightarrow 32\) hold with old Form 338, whereas implication \(338\, \rightarrow 32\) and non-implication \(338\, \nrightarrow 34\) hold with new Form 338!

Because of the huge amount of material collected from hundreds of books and journals by different collaborators it would be unfair to expect that the different contributions could have been seamlessly put together. On the one hand, it might happen that equivalent statements (which should be listed in the same group) actually appear in different groups. On the other hand, there are statements which are not equivalent to the other statements of the same group, i.e., they belong somewhere else. Examples: Form 104 (there is a regular uncountable aleph) is equivalent to Form 182 (there is an aleph whose cofinality is greater than \(\aleph_0\)), and the equivalent forms [8 T] and [8 U] show up in the wrong group; they belong to group 9.

We have mentioned here only cases which have not (yet) been corrected in later websites, and we will continue to do so if not otherwise stated. The publication of this book has kicked off an avalanche of publications and semi-publications. Proving implications or non-implications between consequences of the axiom of choice is now a booming industry. This is no surprise, since this book, and here especially table 1, is an (almost) inexhaustible Problem Book with a degree of difficulty reaching from simple exercises to \({}^{***}\)-problems. The reader could replace the zero entries in table 1 (meaning “unknown”) in his head (or in the real table) by empty spaces, and this causes almost inevitably a horror vacui in every mathematician. He will rack his brain to fill out the empty spaces of this crossword puzzle, either by remembering overlooked results in the literature or else by proving the missing implications and non-implications himself (or combining both). This is an interesting “game”, and for some time the reviewer could not resist this temptation. Here are some results about implications and non-implications whose status is marked “unknown” in the book: Implication 368 \(\rightarrow\) 170 (if \(\mathbb R\) has \(2^{\aleph_0}\)-many countable subsets, then \(\aleph_1 \leq 2^{\aleph_0}\)) is a special case of a theorem of A. Tarski’s [Fundam. Math. 32, 176–183 (1939; Zbl 0021.11003)], who also proved (loc. cit.) the equivalence of forms 170 and [170 A] (there is a function that assigns to each denumerable set \(D\) of real numbers a real number not in \(D\)), credited to W. Sierpiński [Bull. Acad. Pol. Sci., Cl. III 2, 53–54 (1954; Zbl 0056.05002)]. Sierpiński does not mention Tarski’s paper, which was obviously unknown to him. It is a ZF\({}^-\)-theorem that a subset of the reals is compact if and only if it is sequentially compact and separable (see W. Felscher [Naive Mengen und abstrakte Zahlen. II, III (B.I.-Wissenschaftsverlag, Mannheim) (1978/79; Zbl 0409.04001 and Zbl 0409.04002)]); hence we obtain immediately implication 74 \(\rightarrow\) 13 (if compact = sequentially compact for subsets of \(\mathbb R\), then every infinite subset of \(\mathbb R\) is Dedekind-infinite), since every infinite Dedekind-finite subset of the reals is sequentially compact, but not separable. Implication 170 \(\rightarrow\) 38 (if \(\aleph_1 \leq 2^{\aleph_0}\), then \(\mathbb R\) is not the union of countably many countable sets) is a theorem of E. Specker’s [Z. Math. Logik Grundlagen Math. 3, 173–210 (1957; Zbl 0079.07605)]. Implications 172 \(\rightarrow\) 6 and 31 \(\rightarrow\) 172 follow from theorems due to the reviewer [Z. Math. Logik Grundlagen Math. 38, 387–398 (1992; Zbl 0798.03051); Math. Log. Q. 46, 563–568 (2000; Zbl 0963.03068)]. Here, Form 31 is the countable union theorem, Form 6 is the countable union theorem for subsets of \(\mathbb R\), and Form 172 is the statement “the transitive closure of every hereditarily countable set is countable”. There is no space here to list a series of other results. Of course, any new result clears the status of a whole bunch of other implications and non-implications via reduction to known results. For instance, from new result 31 \(\rightarrow\) 172 and known result 31 \(\nrightarrow\) 170 follows non-implication 172 \(\nrightarrow\) 170. Finally, since the publication of the book a great number of new results have been communicated via websites.

As to the references, the authors write in their introduction, “We have tried to give the original sources of the results. However, this is not always possible. When we give references …it means that information about the results can be found there. It does not necessarily mean that it is the original source”. Indeed, it is very difficult to find information about original sources that is historically indisputable. The reviewer has to confess that he also has to rely often on sources he cannot check, or even on hearsay, and very often all of a sudden an overlooked source appears. Hence, the authors’ procedure seems to be the only practical one. We think, however, that, on the one hand, well-established attributions should only be changed with convincing reasons, and that, on the other hand, newly discovered sources should be taken into account. We give a few examples which—as we think—are worthwile mentioning:

1. The formulation of [0 AB] (every (non-empty) perfect subset of \(\mathbb R\) has cardinality \(2^{\aleph_0}\)), is followed by a reference to a note published in 1974, whereas the reader would expect G. Cantor’s name and a reference to his article [Math. Ann. 23, 453–488 (1884; JFM 16.0459.01)]. After all, this theorem was a cornerstone in Cantor’s attack on the continuum hypothesis CH proving via “Cantor-Bendixson” that at least no closed subset of \(\mathbb R\) yields a counterexample to CH.

2. Form 80 (every denumerable set of pairs has a choice function) is attributed to an article published by A. Mostowski in 1948 [Fundam. Math. 35, 127–130 (1948; Zbl 0031.28902)]. But the reader might cheerfully remember Bertrand Russell’s anecdote about the millionaire who bought denumerably many pairs of shoes as well as denumerably many pairs of socks [Introduction to mathematical philosophy (George Allen & Unwin, London) (1919; JFM 47.0036.12)]. Clearly, the millionaire owned \(\aleph_0\)-many boots, but in order to prove that he had also \(\aleph_0\)-many socks, the millionaire had to apply, as Russell pointed out, Form 80 (“multiplicative axiom” for denumerable sets of pairs). In plain words, Russell formulated Form 80 and deduced from it Form [80 A] (= the union of a denumerable set of pairs is denumerable). The converse is trivial.

3. The ZF-theorem that, for every (infinitary) similarity type \(\tau\) and every set \(M\), absolutely free algebras with basis \(M\) exist, attributed to A. Blass in Note 32, is in fact a standard theorem of universal algebra, proved and published long before Blass’s article appeared in 1983. Every proof of the existence of absolutely free algebras splits into two parts: Firstly, a proof of the existence of Peano algebras, i.e., algebras satisfying an axiom system which generalises the Dedekind-Peano axioms for the natural numbers to algebras with arbitrarily many infinitary operations and an arbitrary generating set. Secondly, a proof of the “homomorphic extension theorem”, i.e., the statement that these algebras are absolutely free [An algebra \(\mathfrak A = \langle A;(f_i)_{i\in I}\rangle\) of type \(\tau\) is called absolutely free if there exist a generating subset \(M \subseteq A\) such that every mapping \(\varphi_{0}\) from \(M\) into any algebra \(\mathfrak B\) of the same type extends to a homomorphism \(\varphi\) from \(\mathfrak A\) into \(\mathfrak B\)]. Both assertions can be proved in Z\({}^-\), i.e., without the axioms of choice, replacement and foundation. The homomorphic extension theorem for infinitary Peano algebras—generalising Dedekind’s famous recursion theorem for the very special Peano algebra of the natural numbers—faces no difficulties avoiding AC (though proofs using Zorn’s lemma have been published, e.g., in [R. S. Pierce, Introduction to the theory of abstract algebras (Holt, Rinehart and Winston, New York) (1968)]). The proof of the existence of Peano algebras is a different matter. In 1965 R. Kerkhoff [Math. Ann. 158, 109–112 (1965; Zbl 0192.09402)] published a surprisingly simple construction which does not make use of any form of the axiom of choice! Several other proofs had been published before (e.g., by Birkhoff, Löwig, Dörge, Harzheim, Pierce, Słomiński etc.); they all use consequences of the axiom of choice by assuming that the “arities” have well-ordered cardinalities, and that there exists a regular cardinal above them. Both assumptions are superfluous! Meanwhile, proofs based on constructions different from Kerkhoff’s have been published; they also cover the case of “linearly coded” Peano algebras, i.e., (infinitary) formal languages L\(_{\alpha\beta}\), and allow exact computation of the lengths and ranks (= complexity) of the expressions. All this without AC (see K.-H. Diener [“On constructing infinitary languages L\(_{\alpha\beta}\) without the axiom of choice”, Z. Math. Logik Grundlagen Math. 29, 357–376 (1983; Zbl 0549.03050)]).

4. Form 43, i.e., the axiom of dependent choices (DC), is probably the most interesting consequence of the axiom of choice, much weaker than full AC, but powerful enough to prove important theorems unprovable in ZF. DC was introduced into set theory by O. Teichmüller [Deutsche Math. 4, 567–577 (1939; Zbl 0021.29101)], a fact that seems to be widely unknown, though Teichmüller’s article is very often cited in connection with the Teichmüller-Tukey Lemma. Moreover, both reviewers, [M. Hall, MR 1,34e], and [B. L. van der Waerden, Zbl 0021.29101], recognized the novelty of “Prinzip C” and quoted it in full length: Let \(\mathfrak M\) be a set, and let \(\mathfrak N:\langle x,n\rangle\longmapsto \mathfrak N_n(x)\subseteq\mathbf P(\mathfrak M)\) be a mapping from \(\mathfrak M\times\omega\) into the power set \(\mathbf P(\mathfrak M)\) of \(\mathfrak M\) with \(\mathfrak N_n(x)\neq\emptyset\) for all \(x\in \mathfrak M\) and \(n\in \omega\). Given any \(a\in\mathfrak M\), then there is a sequence \((x_n)_{n\in \omega}\) of elements in \(\mathfrak M\) with \(x_0 = a\) and \(x_{n+1} \in \mathfrak N_n(x_n)\) for every \(n\in \omega\). Some time later slightly different versions were formulated independently by P. Bernays [J. Symb. Log. 7, 65–89 (1942; Zbl 0061.09201)] and A. Tarski [Fundam. Math. 35, 79–104 (1948; Zbl 0031.28903)] (who also coined the name “Principle of an infinite sequence of successive (dependent) choices”). Bernays’s version is Form [43 S], and Tarski’s is Form 43. Bernays’s name does not appear in the book, so his name should be mentioned in connection with [43 S] and included in the author index as well as in the subject index.

There is a remarkable amount of misprints, all trivial and easy to spot. Only one of them has a mathematical bearing: On pages 10 and 48, TC(\(S\)) has to be replaced by TC(\(\{S\)}), if TC(\(x\)) denotes the least transitive set including \(x\) as a subset. This is the most-used definition in the literature which is also in T. Jech’s book [The axiom of choice (North-Holland, Amsterdam) (1973; Zbl 0259.02051)], mentioned by the authors as a reference for set-theoretical notions and axiom systems. Some authors use another definition; they denote by TC(\(x\)) the least transitive set containing \(x\) as an element, e.g., Y. Moschovakis [Notes on set theory (Springer-Verlag, New York) (1994; Zbl 0803.04001)] and R. Smullyan and M. Fitting [Set theory and the continuum problem (Clarendon Press, Oxford) (1996; Zbl 0888.03032)]. In this case the notation TC(\(S\)) would be correct.

Almost all other misprints are due to the authors’ fight with the German language, in particular with grammatical endings, capital letters and “Umlaute”. This is a result of their effort to give “the original sources”, including work from the early days of set theory. A great number of publications were in German, since many of the pioneers of set theory and the foundations of mathematics were native Germans or used, at least for some time, the German language in their mathematical publications: Bernstein, Cantor, Dedekind, Frege, Hartogs, Hausdorff, Hessenberg, Hilbert, Jacobsthal, J. König, Mahlo, Schoenflies, E. Schröder, Zermelo as well as Bernays, Fraenkel, Gödel, Johann Neumann von Margitta (later: John von Neumann), Skolem, Tarski, to name a few. The dramatic decline of the world-wide knowledge of the German language has many reasons; the most important one is, of course, the fact that English has become the lingua franca of our time; it is the global language of the twenty-first century.

Resumé and Epilogue. This book contains an enormous wealth of material the reviewer would never even have started to collect. As the authors said in the Introduction (see above), the book was begun with the primary purpose of avoiding multi-publications of the same results concerning consequences of the axiom of choice. This purpose has already been fulfilled to a large extent, either by the material contained in the book itself or by additional information sent later to the authors and communicated via websites (provided that the book is read and the websites are viewed). Sometimes this updating happens in several steps. Example: Immediately after publication of the book it was recognised that several forms dealing with properties of \({\mathbb R}\) and listed in different groups are equivalent, as, for instance, Form 94 (AC\(_{\omega}\)), Form 92 (every subset of the reals is separable), and Form 73 (for every real function \(f:{\mathbb R}\longrightarrow~{\mathbb R}\) and every real \(x\), \(f\) is \((\epsilon,\delta)\)-continuous at \(x\) if and only if \(f\) is sequentially continuous), etc. This was communicated on a website and these results (and several others) were attributed to articles by H. Herrlich [Commentat. Math. Univ. Carol. 38, 545–552 (1997; Zbl 0938.54007)] and H. Herrlich and G. Strecker [Commentat. Math. Univ. Carol. 38, 553–556 (1997; Zbl 0938.54008)]. However, these results (and many others) were already known and published or semi-published long before the articles of Herrlich and Herrlich-Strecker appeared (see Felscher [loc. cit.], where one can find an exact account of the interdependence of compact, sequentially compact, separable, the axiom of choice for countable families of non-empty sets of reals, Sierpiński’s choice principle etc., as well as extensive and carefully investigated information about the historical background). But these findings of overlooked sources seems to be a process coming soon to an (almost) stationary status.

A last word to the question we raised in the beginning: “Who might benefit from this book?” We mentioned already that it should be of great interest to all set theorists doing research work involving any kind of choice principles. Also many practitioners might greatly benefit from this book whether they are doing some work in this field on their own or just want to get quick information of “how much choice” is needed to prove some bread and butter theorem in algebra and analysis. One should mention, however, that there are also practitioners who seem to feel contempt for these questions. For instance, in his “Foundations of modern analysis” (Academic Press, New York) (1969; Zbl 0176.00502), J. Dieudonné assumes as axioms full AC as well as the statement “finite = Dedekind finite”! Moreover, Dieudonné also says on page 6 (loc. cit.), “It can sometimes be shown that a theorem proved with the help of the axiom of choice can actually be proved without using that axiom. We shall never go into such questions, which properly belong to a course in logic.” The reviewer disagrees. Henri Cartan’s proof [C. R. Acad. Sci., Paris 211, 759–762 (1940; Zbl 0026.12401)] of the existence and uniqueness of a left invariant Haar measure on locally compact topological groups eliminating AC from André Weil’s elegant proof, which used the Tychonoff theorem for compact Hausdorff spaces, does not “properly belong to logic”. Nor is this the case for Teichmüller’s proof of the conformal mapping theorem (uniformisation theorem), eliminating the axiom of dependent choices used implicitly in earlier proofs [Teichmüller (loc. cit.)]. Cartan as well as Teichmüller have to use sophisticated mathematical tools, and, naturally, their proofs yield more information than the proofs based on the non-constructive axiom of choice. [It has to be admitted, however, that the weak axiom of countable choice AC\({}_{\omega}\) is needed for a full-fledged measure theory. On the other hand, André Weil, noticing that in his proof he could have just as well used the ultrafilter theorem instead of the Tychonoff theorem, maintained erroneously, “…le théorème d’existence des ultrafiltres implique, lui aussi, l’axiome de Zermelo, auquel il est même équivalent.” As is well-known, AC is independent from the ultrafilter theorem.]

Dieudonné’s attitude is the direct opposite of Steinitz’s. Steinitz, the pioneer in applying transfinite methods in algebra, wrote in his epochal publication (loc. cit.), “…erscheint es im Interesse der Reinheit der Methode zweckmäßig, das genannte Prinzip [= Auswahlprinzip] so weit zu vermeiden, als die Natur der Frage seine Anwendung nicht erfordert. Ich habe mich bemüht, diese Grenze scharf hervortreten zu lassen.” (translation, “…for the sake of purity of method it seems suitable to avoid the mentioned principle [= axiom of choice] as far as its application is not required by the nature of the problem concerned. I endeavoured to make this boundary clearly visible.”).

It was a habit at that time to mention any use of choice principles resp. to mark all theorems depending on AC, a habit that later became rare, but never ceased completely, and has now reached a new high. [Side remark: A. Kanamori writes in his review [MR 80k:04001] of A. Lévy’s “Basic set theory” (Springer-Verlag, Berlin) (1979; Zbl 0404.04001): “Typical of the author’s diligence is the resurrection of the Russell-Whitehead habit of attaching ‘Ac’ to all theorems proved by using the axiom of choice.” Well, this habit didn’t have to be resurrected; it was never dead, and even rather lively, when Lévy’s book was published in 1979. Kanamori could have recognised this in his own review, since he mentions K. Kuratowski and A. Mostowski’s “Set theory” (North-Holland, Amsterdam) (1968; Zbl 0165.01701), where the same habit is practised (with a circle ‘ \({}^{\circ}\) ’ instead of ‘Ac’). Lévy’s diligence is now even surpassed in recent publications, where, more and more, weaker local versions, instead of “the” axiom of choice, are applied (see, e.g., Smullyan-Fitting [loc. cit.]).

Finally, there are set theorists who voice the opinion that the axiom of choice is “true” and all alternatives to AC, e.g., the axiom of determinacy (AD), are “false”. This means downgrading all independence results concerning choice principles to mere academic exercises in (non)derivability. They don’t have any semantic bearing; after all, who would expect to obtain valuable theorems from false statements? The reviewer remembers only a single case, told in G. Birkhoff’s “Lattice theory. Rev. ed.” (Am. Math. Soc., New York) (1948; Zbl 0033.10103). There Bertrand Russell proved from the (false) hypothesis \(2 + 2 = 5\) that he was the Pope. However, these cases are rare in mathematics. When students ask the reviewer what sense it makes to do, e.g., research work on the axiom of determinacy if one believes it to be “false”, the answer is, “None”. Set theorists who do this anyway don’t interpret their own statements literally. The quoted dictum is just a provocative (“false”) formulation of a stern ontological commitment, confusing beginners.

The reviewer considers work on alternatives of AC very valuable. Here we understand by an alternative of AC a statement which is, though inconsistent with AC, still consistent with weaker consequences; moreover, such an alternative should imply new interesting theorems which in turn are inconsistent with full AC. Nobody would probably dump AC and give up ZFC for good. But it is at least feasible that different set theories will be used (this offers a comparison with geometry, a comparison, however, that has been rejected by many set theorists, including Gödel). And even if no alternative of AC will ever play an important role, its investigation may shed light on the nature of mathematical notions. Roughly speaking, sets are properties, and with a different set-theoretical background mathematical notions and objects have different properties. This is, of course, a commonplace, but its consequences are often overlooked. Alternatives might help us recognise what we have to sacrifice, when we accept AC, on the one hand, or a certain statement inconsistent with AC, on the other hand. The axiom of determinacy is the most prominent of the known alternatives. The research work on AD, done by several set theorists during recent years, yielded beautiful results, culminating in proving the consistency of AD+DC with ZF (provided some large cardinal axiom is consistent with ZFC).

The reals \(\mathbb R\) in ZFC are very different from the reals, for example, in ZF+AD+DC, where every subset of \(\mathbb R\) is Lebesgue measurable and has the Baire property, and every uncountable subset includes a non-empty perfect set. Which are the reals that match best our intuition? One can prove in ZFC that there are \(2^{2^{\aleph_0}}\) \(\mathbb C\)-automorphisms (actually, only a well-order of \(\mathbb R\) is required). All \(\mathbb C\)-automorphisms, with the exception of the identity and conjugation, are discontinuous, hence, send some reals to non-real complex numbers. One can also prove that in ZF+AD+DC only the two continuous \(\mathbb C\)-automorphisms identity and conjugation exist (actually, much less than AD is sufficient). These two \(\mathbb C\)-automorphisms leave the reals pointwise fixed. Hence, while AC “sees” \(\mathbb R\) more or less as a discrete structure, AD “glues” the reals together, so that no \(\mathbb C\)-automorphism can tear them apart. Which reals do we want?

It was no less a person than R. Dedekind who, in 1901 [Festschr. Königl. Gesellsch. Wissensch. Göttingen, 1–17 (1901; JFM 32.0207.01)], connected the problem of how many \(\mathbb C\)-automorphisms exist with the question of the very nature of the continuum, in particular, with its continuity, “the numbers of the real field seem to me so indissolubly connected by continuity that I suppose, it could not have any permutation [= restriction of a \(\mathbb C\)-automorphism to \(\mathbb R\)], except the identity; from this it would follow that the field of all numbers [= \(\mathbb C\)] has only the two mentioned permutations [= \(\mathbb C\)-automorphisms]. After some futile attempts to gain certainty about this I have given up this investigation; I would be pleased all the more if another mathematician told me a conclusive answer” (translated from German). As we have seen, the answer depends on the background theory we choose; the question is undecidable over ZF [Remark. The additions in square brackets are due to the reviewer. Dedekind’s formulation is misleading. It seems to express the statement that, if id\({}_{\mathbb R}\) is the only \(\mathbb R\)-automorphism, then id\({}_{\mathbb C}\) and conjugation are the only \(\mathbb C\)-automorphisms, which is, of course, not true]. The problem of whether there exist discontinuous \(\mathbb C\)-automorphisms was already propounded by C. Segre in 1889 [Atti R. Accad. Sci. Torino 25, 276–301, 430–457, ibid. 26, 35–71, 592–612 (1890; JFM 22.0609.01)] and answered by H. Lebesgue in 1907 [Atti R. Accad. Sci. Torino 42, 532–539 (1907; JFM 38.0096.05)]. Lebesgue showed that there are infinitely many (non-measurable) \(\mathbb C\)-automorphisms, provided \(\mathbb R\) can be well-ordered, an assumption, however, that Lebesgue opposed (for the history of this problem see also H. Kestelman [Proc. Lond. Math. Soc. (2) 53, 1–12 (1951; Zbl 0042.39304)]).

We conclude the review by pointing out that Howard-Rubin’s book is also of great help when investigating alternatives of AC. For instance, AD implies Form 94 (AC\(_{\omega}(\mathbb R\))) and is consistent with Form 43 (DC). Hence, all consequences of AC\(_{\omega}(\mathbb R)\) are also consequences of AD, and all consequences of DC, e.g., Form 8 (AC\(_{\omega}\)), are consistent with AD.

Following the publication of this book, there was an enormous echo with articles, websites, and e-mail containing new results, corrections etc. And even the (unimportant) errors and misprints in the book added to this flood of information, since this caused the readers to also send corrections. When David Hume published his Treatise of human nature, no one noticed the book; as Hume said himself, “it fell dead-born from the press”. Howard-Rubin’s book Consequences of the axiom of choice has avoided this fate. It will be the indispensable standard reference for a long time to come. The authors have accomplished an admirable task.

While the standard work “Equivalents of the axiom of choice. Second ed.” by H. Rubin and J. E. Rubin (North-Holland, Amsterdam) (1985; Zbl 0582.03033) deals almost exclusively with sentences equivalent to AC, in this book the centre of interest is statements of set theory, called forms of the axiom of choice, that depend essentially on some “choice argument”, but do not imply full AC over basic set theory (provided basic set theory is consistent). There are two exceptions: Form 0 and its equivalents are theorems of basic set theory (without “choice”), and Form 1 and its equivalents imply the full axiom of choice.

The authors do not just list the sentences and inform the reader where he can find them in the literature. To save the reader the enormous effort of tracking them down in books and journals, in Part III (Notes) a great number of relevant definitions, proofs of related theorems, and other helpful information can be found. The authors also created two extensive tables which show—using a special code carefully explained in the Introduction—the relative strength of the various consequences of AC with respect to basic set theory.

This book differs from other mathematical books with several features; two of them are novelties reflecting our electronic age:

Firstly, it is of an encyclopaedic character listing 946 sentences, partitioned into 384 classes modulo logical equivalence (over basic set theory).

Secondly, in addition to the six printed parts of the book there is a diskette enclosed consisting of Part VII which contains the above-mentioned two tables.

Thirdly, the authors have installed a website on the Internet (mentioned in the Introduction), which provides the reader with the latest information about errors, corrections, new results etc. as soon as this is known to the authors. This feature is not without pitfalls as we will explain later on. Here we only stress the fact that the stream of information floating in via the Internet makes some of the material in the book, as well as on earlier websites, obsolete very fast. Thus, the above-mentioned 946 forms of the axiom of choice are the forms listed in the book. In order to be on sound ground we will always refer to the book in this review, unless stated otherwise.

It is a mathematical commonplace that the axiom of choice is the most discussed statement in the history of mathematics, second only to Euclid’s parallel postulate. But while the latter is no issue of controversy or even of serious investigation any more, the discussion and investigation of AC lingers on. The motives for this activity have changed throughout the last hundred years—not always in the same straight direction, but rather back and forth. For detailed and carefully investigated information see G. H. Moore’s fine book “Zermelo’s axiom of choice” (Springer-Verlag, New York) (1982; Zbl 0497.01005). The contrary views about the axiom of choice are strikingly demonstrated by an experience of Tarski’s (we follow here G. H. Moore [loc. cit.]). Tarski sent Lebesgue a note that the statement “\(\mathfrak m = \mathfrak m^2\) for every infinite \(\mathfrak m\)” is equivalent to the axiom of choice, and asked him to submit it to the Comptes Rendus. Lebesgue returned the note on the grounds that he opposed the axiom, but suggested sending it to Hadamard. But Hadamard also returned the note, saying that, since the axiom was true, what was the point of proving it from the above statement? The theorem, together with many others, was published in 1924 [A. Tajtelbaum-Tarski, Fundam. Math. 5, 147–154 (1924; JFM 50.0135.01)]. The non-constructive character and the controversial role of AC explain why this review contains, in contrast to others, several remarks about the “underlying philosophy” mathematicians have accepted in this field.

Before reviewing this extensive collection of statements in detail, it might be in order to discuss shortly the purpose this book serves and who might be interested in it.

Hence, who will benefit from this book? In the Introduction the authors themselves mention that in an article published in 1988 the question was raised whether the axiom of choice for countable families of countable sets implies the countable union theorem. In 1992 one of the authors of this book answered this question negatively. The reviewer of the 1992 article, however, pointed out that this result had already been obtained and published in 1974. The authors write in the Introduction, “This book was begun with the primary purpose of preventing such occurrences.” Thus, mathematical researchers who are interested in obtaining results about the relative strength of mathematical statements which require some (or full) “choice”, should find this book helpful for avoiding independent multi-publications of the same results. This will include set theorists as mentioned in Howard-Rubin’s example. Who else might benefit from this book? We will come back to this question later on, but want to stress here already that many mathematical practitioners are also very much interested in the question how much choice is needed to prove a particular theorem. For instance, when does sequential compactness imply compactness in \(\mathbb R\)? These practitioners believe that they get a better understanding of a particular mathematical situation if a theorem is proved under weaker assumptions, even if all these assumptions are consequences of the popular (full) axiom of choice. Applications of “the” axiom of choice are replaced, whenever possible, by weaker consequences, e.g., “local” versions of AC. From this point of view, shared by the reviewer, it is not reasonable to prove, e.g., the existence of a transcendence basis of \(\mathbb C\) over \(\mathbb Q\) by using “the” Zorn’s lemma: This is simply brute overkill! What is needed as a handy condition is the existence of a well-ordering of \(\mathbb C\) (or \(\mathbb R\)). Admittedly, this is no weak property, but still much weaker than the existence of well-orderings for all sets in the universe. There is no doubt that a set theorist can say off the cuff which local version of Zorn’s lemma is actually needed in the above-mentioned case, but many mathematical practitioners are at a loss when they are faced with this question. By the way, the classical proof of the existence of an algebraic closure of arbitrary field \(K\) is just based on a well-ordering of \(K\); hence, if \(K = \mathbb Q\), then no choice principle is needed at all (see E. Steinitz [J. Reine Angew. Math. 137, 167–309 (1910; JFM 41.0445.03)]).

An early appearance of a “local” version of AC is W. Sierpiński’s choice principle: Every \(\omega \)-sequence of non-empty disjoint subsets of \(\mathbb R\) has a subsequence with a choice function [C. R. Acad. Sci., Paris, Sér. A-B 163, 688–690 (1916; JFM 46.0295.04)]. This principle is equivalent to AC\({}_{\omega}(\mathbb R)\) (= Form 94: Every denumerable family of non-empty sets of reals has a choice function).

Though in the early days of the AC-controversy the question of consistency played a role, up to the present time the main concern has been about the non-constructive character of the axiom of choice (it is the only Zermelo axiom—other than extensionality—which is not an instance of the comprehension schema). We will come back to this point at the end of the review, and continue here with a survey of the content:

Part I: Numerical list of forms contains the complete listing of all forms the authors have collected, partitioned into 384 classes modulo logical equivalence. We will also refer to these equivalence classes as “groups”. Each group is headed by some particular statement, which we may call its “master form” here, and which is given a number from 0 to 383. Each master form is followed by all equivalent statements the authors have collected, and which they also call “forms of the axiom of choice”. Statements of the same equivalence class are marked by letters added to the number of the master form; for instance, Form 14 is followed by forms [14 A], [14 B], etc. The authors point out in the Introduction that the forms (other than Form 0 and Form 1) are numbered in the order they encountered them in the literature. Thus, forms the reader would view as closely related might appear far apart in the list. But you get used to this soon, and you keep many “interesting” numbers in your head, as, e.g., Form 8 (AC\({}_{\omega}\)), Form 14 (ultrafilter theorem), and Form 43 (axiom of dependent choices). The numeric resp. alphanumeric denotation of a form is sometimes followed by a special notation and a name [e.g., Form 31. \(UT(\aleph_0,\aleph_0,\aleph_0)\): The countable union theorem], then by the formulation of the statement and (mostly) a reference to the article where this result can be found in the literature. Finally, a reference to a note in Part III is often added to provide further information (for details see below).

Part II: Topical list of forms arranges the bulk of the forms not in groups of logically equivalent statements, but according to the topic, i.e., the mathematical subject matter they are dealing with. There are 12 main sections as, e.g., Algebraic Forms, Cardinal Numbers, Topological Forms (including Properties of \(\mathbb R\)), etc.; some of them are further divided into subsections.

For each topic the forms appear in the same order as in Part I. It can happen that a certain form belonging to several different topics is listed more than once, while others which cannot conveniently be classified do not appear at all in the Topical List.

Part III: Models is the gem of the book for those readers who are not only interested in the independence results, but who also want to get information about the models used in the proofs. This part, headed by a very helpful table of contents, consists of two sections: § 1. Cohen models, denoted (mostly) by \(\mathcal M_k\), and § 2. Fraenkel-Mostowski models, i.e., permutation models, denoted by \(\mathcal N_k\), \(0 < k\in \omega\). For each model listed there is a short description, including forms that are “true” resp. “false” in the model and references to the proofs. All descriptions end with two lists, one with all forms known to be true in the model, and the other with all forms known to be false. The authors have collected and pass over to the reader an impressive amount of information.

Part IV: Notes is a collection of 149 notes referred to in other parts of the book. As in Part III, this part is also headed by a very useful table of contents providing keyword descriptions of the subject matter of every note. The authors usually omit proofs readily available in the literature. If this is not the case—according to the authors’ judgement—proofs are included together with necessary definitions etc. Since the authors refer, as far as possible, to the original literature and its wording, definitions of the same notions might appear in different notes with different formulations.

Some notes also contain new results of the authors as well as brief expositions of essential theorems as, e.g., the transfer theorems of Jech-Sochor and Pincus in Note 103, and a summary of transfer results in Note 18.

Part V: References for Relationships between Forms provides a bulk of information about the status of relations between forms: implication, non-implication or “unknown”. This part has an extensive introduction in which the special code used to indicate the status is carefully explained and demonstrated by examples, e.g., “0” means “The status of the implication is unknown”; “1” means “The implication is provable”; “2” means “The implication is provable and this follows from implications whose code numbers are 1”; “3” means “The implication is not provable in ZF”, and so on till code number “7”. If an implication or non-implication holds, there is mostly a reference to the literature and/or a note. In the case of a non-implication an appropriate model is mentioned; if a ZF-independence result is obtained using a Fraenkel-Mostowski model plus transfer, the name of the permutation model is followed by “T”, e.g., (N2T). If some form does not imply another form in ZF\({}^0\), but does so in ZF, this is also mentioned (e.g., Form 91: the power set of a well-ordered set can be well-ordered).

Part VI: Bibliography begins with a very helpful list of abbreviations of journals (3 pages), followed by a listing of all articles and books used in the book arranged alphabetically by author, and for each author ordered by date of publication.

The printed book ends with a subject index followed by an author index. Both are fortunately very detailed.

Part VII contains two tables (table 1 and table 2) on an enclosed diskette, each of 128 pages as printed out by the reviewer. Each table is a square matrix with as many rows and columns as there are forms (384 in the book, i.e., 147456 entries!). The elements of table 1 are code numbers from 0 to 7 (see above) and reflect the status of the relation between the corresponding forms. The non-zero entries of table 2 are form numbers. These two tables working together reflect the authors’ most ambitious intention to give a complete description of the quasi-order of logical implication between all listed forms of the axiom of choice; moreover, the authors want to inform the reader about the sources in the literature providing him with the proofs. If the code number is 1, 3, or 5, then there should be a direct reference in Part V. If the code number is 2, 4, or 6, then table 2 tells the reader how to find a reduction to implications and non-implications referenced in Part V. This procedure is straightforward, but sometimes lengthy. Example: It is easy to see that Form 94 (= AC\({}_{\omega}(\mathbb R)\)) implies Form 13 (every infinite subset of the reals is Dedekind-infinite). What about the converse \(13\, \longrightarrow 94\)? The entry \(\langle\)13,94\(\rangle\) in table 1 (i.e., the matrix element in row 13 and column 94) is code number 4 (= “the implication is not provable in ZF and this follows from implications whose code numbers are 1 or 3”). Hence, we know that implication \(13\, \longrightarrow 94\) is unprovable in ZF, but where can we find the proof? Well, by switching back and forth from one table to the other we can break down non-implication \(13\, \nrightarrow 94\) into the pieces \(94\, \longrightarrow 5\), \(3\, \longrightarrow 9\), \(9\, \longrightarrow 13\), and \(3\, \nrightarrow 5\), all with references in Part V. Thus, we obtain non-implication \(13\, \nrightarrow 94\), together with complete information of how to prove it.

After having surveyed the content of the book, we will continue to comment on the various parts. Before that, however, we want to point out two pitfalls to the innocent reader:

I. As we mentioned above, the authors use two versions of set theory. ZF is the usual system for Zermelo-Fraenkel set theory, and with ZF\({}^0\) the authors denote an axiom system which differs from ZF by allowing urelements (atoms). Extensionality holds for sets, and a modified axiom of foundation (regularity) requires that every non-empty set without atoms contains an \(\in\)-minimal element. Thus, every “pure” set, i.e., every set whose transitive closure consists of sets, is well-founded, and sets like \(x = \{x\}\) are excluded. This system should not be mixed up with an axiom system which is sometimes also denoted by ZF\({}^0\) in the literature. The latter axiom system, which we will denote here by ZF\({}^{-}\) in order to avoid confusion, is obtained from ZF by just dropping foundation; and ZF\({}^{-}\) (but not Howard-Rubin’s ZF\({}^0\)) can consistently be extended by adding Boffa’s axiom of superuniversality, which is a cornerstone in the abstract framework for nonstandard mathematics (see, e.g., D. Ballard [Foundational aspects of “non” standard mathematics (Contemp. Math. 176, Am. Math. Soc., Providence, RI) (1994; Zbl 0810.03054)]).

II. The same form number may denote one statement in the book and another one on a website. So, e.g., when Form 338 (every second countable metric space is Lindelöf) turned out to be equivalent to Form 94 [AC\({}_{\omega}(\mathbb R)\)], it was given the new number [94 J], whereas some time later the statement UT(\(\aleph_0,\aleph_0,\)WO) was introduced as Form 338. A reader who does not carefully keep track of the changes of numbers (and consequently those of the tables) could get confused. An example: implication \(338\, \rightarrow 34\) and non-implication \(338\, \nrightarrow 32\) hold with old Form 338, whereas implication \(338\, \rightarrow 32\) and non-implication \(338\, \nrightarrow 34\) hold with new Form 338!

Because of the huge amount of material collected from hundreds of books and journals by different collaborators it would be unfair to expect that the different contributions could have been seamlessly put together. On the one hand, it might happen that equivalent statements (which should be listed in the same group) actually appear in different groups. On the other hand, there are statements which are not equivalent to the other statements of the same group, i.e., they belong somewhere else. Examples: Form 104 (there is a regular uncountable aleph) is equivalent to Form 182 (there is an aleph whose cofinality is greater than \(\aleph_0\)), and the equivalent forms [8 T] and [8 U] show up in the wrong group; they belong to group 9.

We have mentioned here only cases which have not (yet) been corrected in later websites, and we will continue to do so if not otherwise stated. The publication of this book has kicked off an avalanche of publications and semi-publications. Proving implications or non-implications between consequences of the axiom of choice is now a booming industry. This is no surprise, since this book, and here especially table 1, is an (almost) inexhaustible Problem Book with a degree of difficulty reaching from simple exercises to \({}^{***}\)-problems. The reader could replace the zero entries in table 1 (meaning “unknown”) in his head (or in the real table) by empty spaces, and this causes almost inevitably a horror vacui in every mathematician. He will rack his brain to fill out the empty spaces of this crossword puzzle, either by remembering overlooked results in the literature or else by proving the missing implications and non-implications himself (or combining both). This is an interesting “game”, and for some time the reviewer could not resist this temptation. Here are some results about implications and non-implications whose status is marked “unknown” in the book: Implication 368 \(\rightarrow\) 170 (if \(\mathbb R\) has \(2^{\aleph_0}\)-many countable subsets, then \(\aleph_1 \leq 2^{\aleph_0}\)) is a special case of a theorem of A. Tarski’s [Fundam. Math. 32, 176–183 (1939; Zbl 0021.11003)], who also proved (loc. cit.) the equivalence of forms 170 and [170 A] (there is a function that assigns to each denumerable set \(D\) of real numbers a real number not in \(D\)), credited to W. Sierpiński [Bull. Acad. Pol. Sci., Cl. III 2, 53–54 (1954; Zbl 0056.05002)]. Sierpiński does not mention Tarski’s paper, which was obviously unknown to him. It is a ZF\({}^-\)-theorem that a subset of the reals is compact if and only if it is sequentially compact and separable (see W. Felscher [Naive Mengen und abstrakte Zahlen. II, III (B.I.-Wissenschaftsverlag, Mannheim) (1978/79; Zbl 0409.04001 and Zbl 0409.04002)]); hence we obtain immediately implication 74 \(\rightarrow\) 13 (if compact = sequentially compact for subsets of \(\mathbb R\), then every infinite subset of \(\mathbb R\) is Dedekind-infinite), since every infinite Dedekind-finite subset of the reals is sequentially compact, but not separable. Implication 170 \(\rightarrow\) 38 (if \(\aleph_1 \leq 2^{\aleph_0}\), then \(\mathbb R\) is not the union of countably many countable sets) is a theorem of E. Specker’s [Z. Math. Logik Grundlagen Math. 3, 173–210 (1957; Zbl 0079.07605)]. Implications 172 \(\rightarrow\) 6 and 31 \(\rightarrow\) 172 follow from theorems due to the reviewer [Z. Math. Logik Grundlagen Math. 38, 387–398 (1992; Zbl 0798.03051); Math. Log. Q. 46, 563–568 (2000; Zbl 0963.03068)]. Here, Form 31 is the countable union theorem, Form 6 is the countable union theorem for subsets of \(\mathbb R\), and Form 172 is the statement “the transitive closure of every hereditarily countable set is countable”. There is no space here to list a series of other results. Of course, any new result clears the status of a whole bunch of other implications and non-implications via reduction to known results. For instance, from new result 31 \(\rightarrow\) 172 and known result 31 \(\nrightarrow\) 170 follows non-implication 172 \(\nrightarrow\) 170. Finally, since the publication of the book a great number of new results have been communicated via websites.

As to the references, the authors write in their introduction, “We have tried to give the original sources of the results. However, this is not always possible. When we give references …it means that information about the results can be found there. It does not necessarily mean that it is the original source”. Indeed, it is very difficult to find information about original sources that is historically indisputable. The reviewer has to confess that he also has to rely often on sources he cannot check, or even on hearsay, and very often all of a sudden an overlooked source appears. Hence, the authors’ procedure seems to be the only practical one. We think, however, that, on the one hand, well-established attributions should only be changed with convincing reasons, and that, on the other hand, newly discovered sources should be taken into account. We give a few examples which—as we think—are worthwile mentioning:

1. The formulation of [0 AB] (every (non-empty) perfect subset of \(\mathbb R\) has cardinality \(2^{\aleph_0}\)), is followed by a reference to a note published in 1974, whereas the reader would expect G. Cantor’s name and a reference to his article [Math. Ann. 23, 453–488 (1884; JFM 16.0459.01)]. After all, this theorem was a cornerstone in Cantor’s attack on the continuum hypothesis CH proving via “Cantor-Bendixson” that at least no closed subset of \(\mathbb R\) yields a counterexample to CH.

2. Form 80 (every denumerable set of pairs has a choice function) is attributed to an article published by A. Mostowski in 1948 [Fundam. Math. 35, 127–130 (1948; Zbl 0031.28902)]. But the reader might cheerfully remember Bertrand Russell’s anecdote about the millionaire who bought denumerably many pairs of shoes as well as denumerably many pairs of socks [Introduction to mathematical philosophy (George Allen & Unwin, London) (1919; JFM 47.0036.12)]. Clearly, the millionaire owned \(\aleph_0\)-many boots, but in order to prove that he had also \(\aleph_0\)-many socks, the millionaire had to apply, as Russell pointed out, Form 80 (“multiplicative axiom” for denumerable sets of pairs). In plain words, Russell formulated Form 80 and deduced from it Form [80 A] (= the union of a denumerable set of pairs is denumerable). The converse is trivial.

3. The ZF-theorem that, for every (infinitary) similarity type \(\tau\) and every set \(M\), absolutely free algebras with basis \(M\) exist, attributed to A. Blass in Note 32, is in fact a standard theorem of universal algebra, proved and published long before Blass’s article appeared in 1983. Every proof of the existence of absolutely free algebras splits into two parts: Firstly, a proof of the existence of Peano algebras, i.e., algebras satisfying an axiom system which generalises the Dedekind-Peano axioms for the natural numbers to algebras with arbitrarily many infinitary operations and an arbitrary generating set. Secondly, a proof of the “homomorphic extension theorem”, i.e., the statement that these algebras are absolutely free [An algebra \(\mathfrak A = \langle A;(f_i)_{i\in I}\rangle\) of type \(\tau\) is called absolutely free if there exist a generating subset \(M \subseteq A\) such that every mapping \(\varphi_{0}\) from \(M\) into any algebra \(\mathfrak B\) of the same type extends to a homomorphism \(\varphi\) from \(\mathfrak A\) into \(\mathfrak B\)]. Both assertions can be proved in Z\({}^-\), i.e., without the axioms of choice, replacement and foundation. The homomorphic extension theorem for infinitary Peano algebras—generalising Dedekind’s famous recursion theorem for the very special Peano algebra of the natural numbers—faces no difficulties avoiding AC (though proofs using Zorn’s lemma have been published, e.g., in [R. S. Pierce, Introduction to the theory of abstract algebras (Holt, Rinehart and Winston, New York) (1968)]). The proof of the existence of Peano algebras is a different matter. In 1965 R. Kerkhoff [Math. Ann. 158, 109–112 (1965; Zbl 0192.09402)] published a surprisingly simple construction which does not make use of any form of the axiom of choice! Several other proofs had been published before (e.g., by Birkhoff, Löwig, Dörge, Harzheim, Pierce, Słomiński etc.); they all use consequences of the axiom of choice by assuming that the “arities” have well-ordered cardinalities, and that there exists a regular cardinal above them. Both assumptions are superfluous! Meanwhile, proofs based on constructions different from Kerkhoff’s have been published; they also cover the case of “linearly coded” Peano algebras, i.e., (infinitary) formal languages L\(_{\alpha\beta}\), and allow exact computation of the lengths and ranks (= complexity) of the expressions. All this without AC (see K.-H. Diener [“On constructing infinitary languages L\(_{\alpha\beta}\) without the axiom of choice”, Z. Math. Logik Grundlagen Math. 29, 357–376 (1983; Zbl 0549.03050)]).

4. Form 43, i.e., the axiom of dependent choices (DC), is probably the most interesting consequence of the axiom of choice, much weaker than full AC, but powerful enough to prove important theorems unprovable in ZF. DC was introduced into set theory by O. Teichmüller [Deutsche Math. 4, 567–577 (1939; Zbl 0021.29101)], a fact that seems to be widely unknown, though Teichmüller’s article is very often cited in connection with the Teichmüller-Tukey Lemma. Moreover, both reviewers, [M. Hall, MR 1,34e], and [B. L. van der Waerden, Zbl 0021.29101], recognized the novelty of “Prinzip C” and quoted it in full length: Let \(\mathfrak M\) be a set, and let \(\mathfrak N:\langle x,n\rangle\longmapsto \mathfrak N_n(x)\subseteq\mathbf P(\mathfrak M)\) be a mapping from \(\mathfrak M\times\omega\) into the power set \(\mathbf P(\mathfrak M)\) of \(\mathfrak M\) with \(\mathfrak N_n(x)\neq\emptyset\) for all \(x\in \mathfrak M\) and \(n\in \omega\). Given any \(a\in\mathfrak M\), then there is a sequence \((x_n)_{n\in \omega}\) of elements in \(\mathfrak M\) with \(x_0 = a\) and \(x_{n+1} \in \mathfrak N_n(x_n)\) for every \(n\in \omega\). Some time later slightly different versions were formulated independently by P. Bernays [J. Symb. Log. 7, 65–89 (1942; Zbl 0061.09201)] and A. Tarski [Fundam. Math. 35, 79–104 (1948; Zbl 0031.28903)] (who also coined the name “Principle of an infinite sequence of successive (dependent) choices”). Bernays’s version is Form [43 S], and Tarski’s is Form 43. Bernays’s name does not appear in the book, so his name should be mentioned in connection with [43 S] and included in the author index as well as in the subject index.

There is a remarkable amount of misprints, all trivial and easy to spot. Only one of them has a mathematical bearing: On pages 10 and 48, TC(\(S\)) has to be replaced by TC(\(\{S\)}), if TC(\(x\)) denotes the least transitive set including \(x\) as a subset. This is the most-used definition in the literature which is also in T. Jech’s book [The axiom of choice (North-Holland, Amsterdam) (1973; Zbl 0259.02051)], mentioned by the authors as a reference for set-theoretical notions and axiom systems. Some authors use another definition; they denote by TC(\(x\)) the least transitive set containing \(x\) as an element, e.g., Y. Moschovakis [Notes on set theory (Springer-Verlag, New York) (1994; Zbl 0803.04001)] and R. Smullyan and M. Fitting [Set theory and the continuum problem (Clarendon Press, Oxford) (1996; Zbl 0888.03032)]. In this case the notation TC(\(S\)) would be correct.

Almost all other misprints are due to the authors’ fight with the German language, in particular with grammatical endings, capital letters and “Umlaute”. This is a result of their effort to give “the original sources”, including work from the early days of set theory. A great number of publications were in German, since many of the pioneers of set theory and the foundations of mathematics were native Germans or used, at least for some time, the German language in their mathematical publications: Bernstein, Cantor, Dedekind, Frege, Hartogs, Hausdorff, Hessenberg, Hilbert, Jacobsthal, J. König, Mahlo, Schoenflies, E. Schröder, Zermelo as well as Bernays, Fraenkel, Gödel, Johann Neumann von Margitta (later: John von Neumann), Skolem, Tarski, to name a few. The dramatic decline of the world-wide knowledge of the German language has many reasons; the most important one is, of course, the fact that English has become the lingua franca of our time; it is the global language of the twenty-first century.

Resumé and Epilogue. This book contains an enormous wealth of material the reviewer would never even have started to collect. As the authors said in the Introduction (see above), the book was begun with the primary purpose of avoiding multi-publications of the same results concerning consequences of the axiom of choice. This purpose has already been fulfilled to a large extent, either by the material contained in the book itself or by additional information sent later to the authors and communicated via websites (provided that the book is read and the websites are viewed). Sometimes this updating happens in several steps. Example: Immediately after publication of the book it was recognised that several forms dealing with properties of \({\mathbb R}\) and listed in different groups are equivalent, as, for instance, Form 94 (AC\(_{\omega}\)), Form 92 (every subset of the reals is separable), and Form 73 (for every real function \(f:{\mathbb R}\longrightarrow~{\mathbb R}\) and every real \(x\), \(f\) is \((\epsilon,\delta)\)-continuous at \(x\) if and only if \(f\) is sequentially continuous), etc. This was communicated on a website and these results (and several others) were attributed to articles by H. Herrlich [Commentat. Math. Univ. Carol. 38, 545–552 (1997; Zbl 0938.54007)] and H. Herrlich and G. Strecker [Commentat. Math. Univ. Carol. 38, 553–556 (1997; Zbl 0938.54008)]. However, these results (and many others) were already known and published or semi-published long before the articles of Herrlich and Herrlich-Strecker appeared (see Felscher [loc. cit.], where one can find an exact account of the interdependence of compact, sequentially compact, separable, the axiom of choice for countable families of non-empty sets of reals, Sierpiński’s choice principle etc., as well as extensive and carefully investigated information about the historical background). But these findings of overlooked sources seems to be a process coming soon to an (almost) stationary status.

A last word to the question we raised in the beginning: “Who might benefit from this book?” We mentioned already that it should be of great interest to all set theorists doing research work involving any kind of choice principles. Also many practitioners might greatly benefit from this book whether they are doing some work in this field on their own or just want to get quick information of “how much choice” is needed to prove some bread and butter theorem in algebra and analysis. One should mention, however, that there are also practitioners who seem to feel contempt for these questions. For instance, in his “Foundations of modern analysis” (Academic Press, New York) (1969; Zbl 0176.00502), J. Dieudonné assumes as axioms full AC as well as the statement “finite = Dedekind finite”! Moreover, Dieudonné also says on page 6 (loc. cit.), “It can sometimes be shown that a theorem proved with the help of the axiom of choice can actually be proved without using that axiom. We shall never go into such questions, which properly belong to a course in logic.” The reviewer disagrees. Henri Cartan’s proof [C. R. Acad. Sci., Paris 211, 759–762 (1940; Zbl 0026.12401)] of the existence and uniqueness of a left invariant Haar measure on locally compact topological groups eliminating AC from André Weil’s elegant proof, which used the Tychonoff theorem for compact Hausdorff spaces, does not “properly belong to logic”. Nor is this the case for Teichmüller’s proof of the conformal mapping theorem (uniformisation theorem), eliminating the axiom of dependent choices used implicitly in earlier proofs [Teichmüller (loc. cit.)]. Cartan as well as Teichmüller have to use sophisticated mathematical tools, and, naturally, their proofs yield more information than the proofs based on the non-constructive axiom of choice. [It has to be admitted, however, that the weak axiom of countable choice AC\({}_{\omega}\) is needed for a full-fledged measure theory. On the other hand, André Weil, noticing that in his proof he could have just as well used the ultrafilter theorem instead of the Tychonoff theorem, maintained erroneously, “…le théorème d’existence des ultrafiltres implique, lui aussi, l’axiome de Zermelo, auquel il est même équivalent.” As is well-known, AC is independent from the ultrafilter theorem.]

Dieudonné’s attitude is the direct opposite of Steinitz’s. Steinitz, the pioneer in applying transfinite methods in algebra, wrote in his epochal publication (loc. cit.), “…erscheint es im Interesse der Reinheit der Methode zweckmäßig, das genannte Prinzip [= Auswahlprinzip] so weit zu vermeiden, als die Natur der Frage seine Anwendung nicht erfordert. Ich habe mich bemüht, diese Grenze scharf hervortreten zu lassen.” (translation, “…for the sake of purity of method it seems suitable to avoid the mentioned principle [= axiom of choice] as far as its application is not required by the nature of the problem concerned. I endeavoured to make this boundary clearly visible.”).

It was a habit at that time to mention any use of choice principles resp. to mark all theorems depending on AC, a habit that later became rare, but never ceased completely, and has now reached a new high. [Side remark: A. Kanamori writes in his review [MR 80k:04001] of A. Lévy’s “Basic set theory” (Springer-Verlag, Berlin) (1979; Zbl 0404.04001): “Typical of the author’s diligence is the resurrection of the Russell-Whitehead habit of attaching ‘Ac’ to all theorems proved by using the axiom of choice.” Well, this habit didn’t have to be resurrected; it was never dead, and even rather lively, when Lévy’s book was published in 1979. Kanamori could have recognised this in his own review, since he mentions K. Kuratowski and A. Mostowski’s “Set theory” (North-Holland, Amsterdam) (1968; Zbl 0165.01701), where the same habit is practised (with a circle ‘ \({}^{\circ}\) ’ instead of ‘Ac’). Lévy’s diligence is now even surpassed in recent publications, where, more and more, weaker local versions, instead of “the” axiom of choice, are applied (see, e.g., Smullyan-Fitting [loc. cit.]).

Finally, there are set theorists who voice the opinion that the axiom of choice is “true” and all alternatives to AC, e.g., the axiom of determinacy (AD), are “false”. This means downgrading all independence results concerning choice principles to mere academic exercises in (non)derivability. They don’t have any semantic bearing; after all, who would expect to obtain valuable theorems from false statements? The reviewer remembers only a single case, told in G. Birkhoff’s “Lattice theory. Rev. ed.” (Am. Math. Soc., New York) (1948; Zbl 0033.10103). There Bertrand Russell proved from the (false) hypothesis \(2 + 2 = 5\) that he was the Pope. However, these cases are rare in mathematics. When students ask the reviewer what sense it makes to do, e.g., research work on the axiom of determinacy if one believes it to be “false”, the answer is, “None”. Set theorists who do this anyway don’t interpret their own statements literally. The quoted dictum is just a provocative (“false”) formulation of a stern ontological commitment, confusing beginners.

The reviewer considers work on alternatives of AC very valuable. Here we understand by an alternative of AC a statement which is, though inconsistent with AC, still consistent with weaker consequences; moreover, such an alternative should imply new interesting theorems which in turn are inconsistent with full AC. Nobody would probably dump AC and give up ZFC for good. But it is at least feasible that different set theories will be used (this offers a comparison with geometry, a comparison, however, that has been rejected by many set theorists, including Gödel). And even if no alternative of AC will ever play an important role, its investigation may shed light on the nature of mathematical notions. Roughly speaking, sets are properties, and with a different set-theoretical background mathematical notions and objects have different properties. This is, of course, a commonplace, but its consequences are often overlooked. Alternatives might help us recognise what we have to sacrifice, when we accept AC, on the one hand, or a certain statement inconsistent with AC, on the other hand. The axiom of determinacy is the most prominent of the known alternatives. The research work on AD, done by several set theorists during recent years, yielded beautiful results, culminating in proving the consistency of AD+DC with ZF (provided some large cardinal axiom is consistent with ZFC).

The reals \(\mathbb R\) in ZFC are very different from the reals, for example, in ZF+AD+DC, where every subset of \(\mathbb R\) is Lebesgue measurable and has the Baire property, and every uncountable subset includes a non-empty perfect set. Which are the reals that match best our intuition? One can prove in ZFC that there are \(2^{2^{\aleph_0}}\) \(\mathbb C\)-automorphisms (actually, only a well-order of \(\mathbb R\) is required). All \(\mathbb C\)-automorphisms, with the exception of the identity and conjugation, are discontinuous, hence, send some reals to non-real complex numbers. One can also prove that in ZF+AD+DC only the two continuous \(\mathbb C\)-automorphisms identity and conjugation exist (actually, much less than AD is sufficient). These two \(\mathbb C\)-automorphisms leave the reals pointwise fixed. Hence, while AC “sees” \(\mathbb R\) more or less as a discrete structure, AD “glues” the reals together, so that no \(\mathbb C\)-automorphism can tear them apart. Which reals do we want?

It was no less a person than R. Dedekind who, in 1901 [Festschr. Königl. Gesellsch. Wissensch. Göttingen, 1–17 (1901; JFM 32.0207.01)], connected the problem of how many \(\mathbb C\)-automorphisms exist with the question of the very nature of the continuum, in particular, with its continuity, “the numbers of the real field seem to me so indissolubly connected by continuity that I suppose, it could not have any permutation [= restriction of a \(\mathbb C\)-automorphism to \(\mathbb R\)], except the identity; from this it would follow that the field of all numbers [= \(\mathbb C\)] has only the two mentioned permutations [= \(\mathbb C\)-automorphisms]. After some futile attempts to gain certainty about this I have given up this investigation; I would be pleased all the more if another mathematician told me a conclusive answer” (translated from German). As we have seen, the answer depends on the background theory we choose; the question is undecidable over ZF [Remark. The additions in square brackets are due to the reviewer. Dedekind’s formulation is misleading. It seems to express the statement that, if id\({}_{\mathbb R}\) is the only \(\mathbb R\)-automorphism, then id\({}_{\mathbb C}\) and conjugation are the only \(\mathbb C\)-automorphisms, which is, of course, not true]. The problem of whether there exist discontinuous \(\mathbb C\)-automorphisms was already propounded by C. Segre in 1889 [Atti R. Accad. Sci. Torino 25, 276–301, 430–457, ibid. 26, 35–71, 592–612 (1890; JFM 22.0609.01)] and answered by H. Lebesgue in 1907 [Atti R. Accad. Sci. Torino 42, 532–539 (1907; JFM 38.0096.05)]. Lebesgue showed that there are infinitely many (non-measurable) \(\mathbb C\)-automorphisms, provided \(\mathbb R\) can be well-ordered, an assumption, however, that Lebesgue opposed (for the history of this problem see also H. Kestelman [Proc. Lond. Math. Soc. (2) 53, 1–12 (1951; Zbl 0042.39304)]).

We conclude the review by pointing out that Howard-Rubin’s book is also of great help when investigating alternatives of AC. For instance, AD implies Form 94 (AC\(_{\omega}(\mathbb R\))) and is consistent with Form 43 (DC). Hence, all consequences of AC\(_{\omega}(\mathbb R)\) are also consequences of AD, and all consequences of DC, e.g., Form 8 (AC\(_{\omega}\)), are consistent with AD.

Following the publication of this book, there was an enormous echo with articles, websites, and e-mail containing new results, corrections etc. And even the (unimportant) errors and misprints in the book added to this flood of information, since this caused the readers to also send corrections. When David Hume published his Treatise of human nature, no one noticed the book; as Hume said himself, “it fell dead-born from the press”. Howard-Rubin’s book Consequences of the axiom of choice has avoided this fate. It will be the indispensable standard reference for a long time to come. The authors have accomplished an admirable task.

Reviewer: K.-H.Diener (Köln)

##### MSC:

03-00 | General reference works (handbooks, dictionaries, bibliographies, etc.) pertaining to mathematical logic and foundations |

03E25 | Axiom of choice and related propositions |

03-02 | Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations |