Tag Archives: book review

Book review of G. Tourlakis, Lectures in Logic and Set Theory I & II

Posted on by
Reply

[bibtex key=Hamkins2005:TourlakisBookReview]

Review of George Tourlakis, Lectures in Logic and Set Theory, volumes 1 and 2, Cambridge studies in advanced  mathematics, vol. 83.  Cambridge University Press, Cambridge, UK, 2003. This is a detailed two-volume development of mathematical logic and set theory, written  from a formalist point of view, aimed at a spectrum of  students from the third-year undergraduate to junior  graduate level. Volume 1 presents the heart of mathematical  logic, including the Completeness and Incompleteness theorems along with a bit of computability theory and accompanying ideas. Tourlakis aspires to include “the absolutely essential topics in proof, model and recursion theory” (vol. 1, p. ix). In addition, for the final third of the volume, Tourlakis provides a proof  of the Second Incompleteness Theorem “right from Peano’s axioms,…gory details and all,” which he conjectures “is the only complete proof in print [from just Peano arithmetic] other than the one that was given in Hilbert and Bernays (1968)” (vol. 1, p. x). In the opening
page of Chapter II, Tourlakis provides a lucid explanation of the proof in plain language, before diving into the details and emerging a hundred pages later with the provability predicate, the derivability conditions and a complete proof. Tempering his formalist tendencies, Tourlakis speaks “the formal language with a heavy `accent’ and using many `idioms’ borrowed from `real’ (meta)mathematics and English,” in a mathematical argot (vol. 1, p. 39). In his theorems and proofs, therefore, he stays close to the formal language without remaining inside it.

But let me focus on volume 2, a stand-alone development of axiomatic set theory, containing within it a condensed version of volume 1. The book emphasizes the formal
foundations of set theory and, like the first volume, gives considerable attention to the details of the elementary theory. Tourlakis is admirably meticulous in maintaining
the theory/metatheory distinction, with a careful explanation of the role of inductive arguments and constructions in the metatheory (vol. 2, p. 20) and a correspondingly precise treatment of axioms, theorems and their respective schemes throughout. What is more, he sprinkles the text with philosophical explanations of the theory/metatheory interaction, giving a clear account, for example, of how it is that we may use apparently set theoretic arguments in the metatheory without circularity (vol. 1, p. 10-12). After developing the logical background, he paints the motivating picture of the cumulative hierarchy, the process by which we imagine sets to be built, with Russell’s paradox as a cautionary tale. In Chapter III, the axioms of set theory march forward in succession. He presents them gradually, motivating them from the cumulative hierarchy and deriving consequences as they appear. This treatment includes the Axiom of Choice, which he motivates, impressively, by developing Goedel’s constructible universe $L$ sufficiently to see that the Axiom of Choice holds there. Later, he revisits the constructible universe more formally, and by the end of the book his formal set theoretic development encompasses even the sophisticated topic of forcing. The book culminates in Cohen’s relative consistency proof, via forcing, of the failure of the Continuum Hypothesis.

Interestingly, Tourlakis’ version of ZFC set theory, like Zermelo’s,  allows for (without insisting on) the existence of urelements, atomic objects that are not sets, but which
can be elements of sets. His reason for this is philosophical and pedagogical: he finds “it extremely counterintuitive, especially when addressing undergraduate audiences, to tell them that all their familiar mathematical objects — the `stuff of mathematics’ in
Barwise’s words — are just perverse `box-in-a-box-in-a-box\dots’ formulations built from an infinite supply of empty boxes” (vol. 2, p. xiii). The enrichment of the theory to allow
urelements requires only minor modifications of the usual  ZFC axioms, such as the restriction of Extensionality to the sets and not the urelements. The application of the
definition $a\subseteq b\iff\forall z(z\in a\implies z\in b)$ even when $a$ or $b$ are urelements, however, causes some peculiarities, such as the consequence that urelements are subsets of every object, including each other. Consequently, the axiom asserting that the urelements form a set (Axiom III.3.1), is actually deducible via the
Comprehension Axiom from Tourlakis’ version of the Power Set Axiom, which asserts that for every object $a$ there is a set $b$ such that $\forall x(x\subseteq a\implies x\in
b)$, since any such $b$ must contain all urelements.

At times, the author employs what some might take as an exaggerated formal style. For example, after introducing the Pairing Axiom, stating that for any $a$ and $b$ there
is $c$ with $a\in c$ and $b\in c$, he considers Proposition  III.5.3, the trivial consequence that $\{a,b\}$ is a set. His first proof of this is set out in eleven numbered
steps, with duly noted uses of the Leibniz axiom and modus ponens. To be sure, he later adopts what he calls a “relaxed” proof style, but even so, in the “Informal”
Example III.9.2, he fills a page with tight reasoning and explicit appeals to the deduction theorem, the principle of auxiliary constants and more, to show merely that if $x$ is
a set and $x\subseteq\{\emptyset\}$, then $x=\emptyset$ or $x=\{\emptyset\}$. Similar examples of formality can be found on pages 118, 120, 183-184 and elsewhere in volume 2, as well as volume 1.

The preface of volume 2 explains that the book weaves a middle path between those set theory books that merely build set-theoretic tools for use elsewhere and those that
aim at research in set theory. But I question this assessment. Many of the topics constituting what I take to be the beginnings of the subject appear only very late in
the book. For example, the von Neumann ordinals appear first on page 331; Cantor’s theorem on the uncountability of $P(\omega)$ occurs on page 455; the Cantor-Bernstein theorem appears on page 463; the definitions of cardinal successor and $\aleph_\alpha$ wait until page 465; and the definition of cofinality does not appear until page 478, with regular and singular cardinals on page 479. Perhaps it was the elaborate formal development of the early theory that has pushed this basic part of set theory to the end of the book. This may not be a problem, but I worry that students may wrongly understand these topics to constitute “advanced” set theory, when surely the opposite is true. Furthermore, many other elementary topics, which one might expect to find in a set theory text aimed in part at graduate students, do not appear in the text at all. This includes closed unbounded sets, stationary sets, $\omega_1$-trees (such as Souslin trees or Kurepa trees), Borel sets, regressive functions, Martin’s axiom, the
diamond principle and even ultrafilters. Large cardinals are not mentioned beyond the inaccessible cardinals. The omission of ultrafilters is particularly puzzling, given
the author’s claim to have included “all the fundamental tools of set theory as needed elsewhere in the mathematical sciences” (vol. 2, p.~xii). Certainly ultrapowers are one
of the most powerful and successful such tools, whose fundamental properties remain deeply connected with logic.

In the final chapter, the author provides a formal account of the foundations of forcing, with useful explanations again of the important theory/metatheory interaction
arising in connection with it. Because his account of forcing is based on countable transitive models, some set theorists may find it old-fashioned. This way of forcing
tends to push much of the technique into the metatheory, which Tourlakis adopts explicitly (vol. 2, p. 519), and can sometimes limit forcing to its role in independence
results. A more contemporary view of forcing makes sense within ZFC of forcing over $V$, for example via the Boolean-valued models $V^{\mathbb B}$, and allows one
sensibly to discuss the possibilities achievable by forcing over any given model of set theory.

Despite my reservations, I welcome Tourlakis’ addition to the body of logic texts. Readers with a formalist bent especially will gain from it.

Book review of The Higher Infinite, Akihiro Kanamori

Posted on by
3

[bibtex key=Hamkins2000:BookReviewKanamori]

Akihiro Kanamori. The Higher Infinite.    Large cardinals, stealing upwards through the clouds of imagined limitation like the steel skyscrapers of a ever-growing set-theoretic skyline, reach towards the stratosphere of Cantor’s absolute. In this century we have axiomatized larger and larger notions of infinity, and as we live amongst these giants, the formerly tall now seem small. Weakly inaccessible cardinals, for example, first considered by Hausdorff as a natural transfinite limit of set-theoretic operations, now occupy a floor at the entryway to the large cardinal hierarchy. In time over the past century we had Mahlo cardinals, strongly inaccessible cardinals, measurable cardinals, indescribable cardinals, weakly-compact cardinals, strongly-compact cardinals, super-compact cardinals, huge cardinals, almost huge cardinals, superhuge cardinals, and so on. And while when it comes to naming these enormous magnitudes, words have perhaps failed us, the mathematics is perfectly precise and fascinating.

Professor Kanamori has written—beautifully so—the book we large cardinal set-theorists have been lacking, a book spanning the possibilities from inaccessible to superhuge cardinals and beyond, a book full of historical insight, clear writing, interesting theorems and elegant proofs. This book is destined to become, if it has not already become, the standard reference in its field.

Finding that “a genetic account through historical progression…provides the most coherent exposition of the mathematics and holds the key to any epistemological concerns,” (p. XI) Kanamori weaves a historical perspective into the mathematics, deepening our understanding and appreciation of it. He sprinkles the text with quotations of Gödel and others, giving their mathematical-philosophical views on the mathematical developments. The introduction stands alone as a non-technical essay introducing the entire subject. From there, Kanamori begins with the smaller large cardinals, inaccessible and Mahlo cardinals, and then moves in time up to the strongest hypotheses.

So let me begin to explain a little about large cardinals. A cardinal $\kappa$ is inaccessible when it cannot be constructed from smaller cardinals, so that first, it is not the supremum of fewer than $\kappa$ many cardinals each of size less than $\kappa$ (as, for example, $\aleph_\omega=\sup_n\aleph_n$ is), and second, it cannot be reached by the power set operation in the sense that whenever $\delta$ is smaller than $\kappa$ then $2^\delta$ is also smaller than $\kappa$. It is relatively straightforward to show that if $\kappa$ is inaccessible, then $V_\kappa$ is a model of ZFC. In particular, if $\kappa$ is the least inaccessible cardinal, then $V_\kappa$ will be a model of ZFC in which there are no inaccessible cardinals. So it is relatively consistent with ZFC that there are no large cardinals at all. Furthermore, since the mere existence of an inaccessible cardinal provides a full model of ZFC, we cannot hope even for a relative consistency result of the form “If ZFC is consistent, then so is ZFC $+$ there is an inaccessible cardinal” (in the manner of results proved for the Continuum Hypothesis and the Axiom of Choice), for then the theory “ZFC $+$ there is an inaccessible cardinal” would imply its own consistency, contrary to Gödel’s Incompleteness Theorem. In short, the consistency strength of the existence of an inaccessible cardinal is greater than that of ZFC alone. At first glance, then, the logical status of the existence of even the smallest of the large cardinals is a bit startling: we can’t prove they exist; it is consistent that they don’t exist; and we can prove that we cannot prove that their existence is relatively consistent. What, then, is the point of them?

The point is that such a transcendence over ZFC in consistency strength is exactly what we want and what we need. In the decades since the invention of Cohen’s forcing technique, set theorists have set marching an infinite parade of independence results; indeed, it often seems as though almost all the interesting set-theoretic questions are independent of our ZFC axioms. We all know now that the cardinality of the set $\mathbb{R}$ of reals can be $\aleph_1$ or $\aleph_2$ or $\aleph_{1776}$ or $\aleph_{\omega+1776}$ or any cardinal you like within reason, and this unfinished nature of ZFC when it comes to basic set theoretic questions is the norm. We have learned in this sense that ZFC is a weak theory. The large cardinal axioms provide strengthenings of it, strengthenings which are fundamentally different from the strengthenings of ZFC provided by the Continuum Hypothesis, the Generalized Continuum Hypothesis, Souslin’s Hypothesis, Martin’s Axiom and many of the other principles that we know to properly extend ZFC, in that large cardinals transcend even the consistency strength of ZFC. The large cardinal hierarchy, therefore, in addition to its intrinsic mathematical interest, provides a natural structure which can be used to gauge the consistency strength of general mathematical propositions.

Let me give one example. Almost all mathematicians are familiar with Vitali’s construction of a non-Lebesgue measurable set of reals and furthermore believe that the construction makes an essential use of the Axiom of Choice AC. But what does this mean exactly? The impossibility of removing AC from the Vitali construction is equivalent to the consistency (without AC) that every set of reals is Lebesgue measurable. Now of course we need some choice principle to develop a satisfactory theory of Lebesgue measure at all, so let us keep in the base theory the principle of Dependent Choices DC, which allows us to make countably many choices in succession. Thus, we are led to consider the consistency of the theory $T=$ “ZF + DC + every set of reals is Lebesgue measurable”. Solovay [65] proved that if ZFC is consistent with the existence of an inaccessible cardinal, then $T$ is consistent; that is, if inaccessible cardinals are consistent, then we are perfectly correct in believing that you cannot remove AC from Vitali’s construction. Since most mathematicians already believed this conclusion, Solovay’s use of an inaccessible cardinal was widely seen as a defect in his argument. But Shelah [84] exploded this criticism by proving conversely that if $T$ is consistent, then so is the existence of an inaccessible cardinal. That is, the two theories are equiconsistent, and we should be exactly as confident in the consistency of inaccessible cardinals as we are in our belief that Vitali’s use of AC is essential.

After the beginnings, Kanamori moves swiftly through a chapter on partition properties, weak compactness, indiscernibles and $0^\sharp$, before moving into a longer chapter on forcing and sets of reals, in which he introduces forcing, Lebesgue measurability and topics from descriptive set theory. Next, in Chapter Four, he approaches measurability from the direction of saturated ideals, including such topics as Prikry forcing, iterated ultrapower embeddings, the inner model $L[\mu]$, $0^\dagger$ and, curiously, a chess problem for the solution of which he will pay a small prize. The strongest hypotheses appear in Chapter five along with the combinatorial backup needed to support them. Kanamori concludes in Chapter six with the Axiom of Determinacy, giving such connections to large cardinals as can be easily given, and, whetting the appetite of the eager student, surveying the more recent, more difficult, and more amazing results.

Kanamori’s book has already been translated into Japanese by S. Fuchino, and judging by the graduate students I saw last year in Japan pouring over it, the translation seems destined to create a new generation of large cardinal set theorists in Japan.

I do have one reservation about Kanamori’s book, namely, that he didn’t include much material on the interaction between forcing and large cardinals. Admittedly, this being the focus of much of my own work, I harbor some bias in its favor, but the topics of forcing and large cardinals are two major set theoretic research areas, and the intersection is rich. It would have been relatively easy for Kanamori to include a presentation, for example, of the landmark Laver preparation, by which any supercompact cardinal $\kappa$ becomes indestructible by $\kappa$-directed closed forcing. And Laver’s result is really just the beginning of the investigation of how large cardinals are affected by forcing. I trust that much of this work will appear in volume II.

My overall evaluation is entirely positive, and I recommend the book in the strongest possible terms to anyone with an interest in large cardinals. I can hardly wait for the subsequent volume!

[84] Saharon Shelah, “Can you take Solovay’s inaccessible away?” IJM 48 (1984), 1-47.

[65] Robert M. Solovay, “The measure problem,” NAMS 12 (1965), 217.

Book review of Notes on Set Theory, Moschovakis

Posted on by
Reply

[bibtex key=Hamkins1998:BookReviewMoschovakis]

Yiannis N. Moschovakis. Notes on Set Theory. This is a sophisticated undergraduate set theory text, packed with elegant proofs, historical explanations, and enlightening exercises, all presented at just the right level for a first course in set theory. Moschovakis focuses strongly on the Zermelo axioms, and shows clearly that much if not all of classical mathematics needs nothing more. Indeed, he says, “all the objects studied in classical algebra, analysis, functional analysis, topology, probability, differential equations, etc. can be found in [the least Zermelo universe] $\cal Z$” (p. 179). The analysis of this universe $\cal Z$ and the other set-theoretic universes like it at the book’s conclusion has the metamathematical flavor of the forcing arguments one might find in a more advanced text, and ultimately spurs one deeper into set theory.

The Notes begin, pre-axiomatically, with functions and equinumerosity, proving, for example, the uncountability of $\mathbb{R}$ and the Schröder-Bernstein Theorem. In a dramatic fashion, Moschovakis then slides smoothly into the General Comprehension Principle, citing its strong intuitive appeal, and then BOOM! the Russell paradox appears.  With it, the need for an axiomatic approach is made plain. Introducing the basic Zermelo axioms of Extensionality, Empty-set, Pairing, Separation, Power set, Union, and a version of Infinity (but not yet the axioms of Choice, Foundation, or Replacement), he proceeds to found the familiar set theory on them.

Following a philosophy of faithful representation, Moschovakis holds, for example, that while functions may not actually be sets of ordered pairs, mathematics can be developed as if they were.  A lively historical approach, including periodic quotations from Cantor, brings out one’s natural curiosity, and leads to the Cardinal Assignent Problem, the problem of finding a sensible meaning for the cardinality $|A|$ of any set $A$. Among the excellent exercises are several concerning Dedekind-finite sets.

After an axiomatic treatment of the natural numbers, with special attention paid to the Recursion Theorem (three different forms) and the cardinal arithmetic of the continuum (but no definition yet of $|A|$), Moschovakis emphasizes fixed point theorems, proving stronger and better recursion theorems.  Wellorderings are treated in chapter seven, with transfinite arithmetic and recursion, but, lacking the Replacement axiom, without ordinals. After this the axiom of Choice arrives with its equivalents and consequences, but without a solution to the cardinal assignment problem.  Chapter ten, on Baire space, is an excellent introduction to descriptive set theory. The axiom of Replacement finally appears in chapter eleven and is used to analyze the least Zermelo set-theoretic universe. Replacement leads naturally in the very last chapter to the familiar von Neumann ordinals, defined as the image of a wellorder under a von Neumann surjection (like a Mostowski collapse), and with them come the $\aleph_\alpha$, $\beth_\alpha$ and $V_\alpha$ hierarchies. Two well-written appendices, one, a careful construction of $\mathbb{R}$, the other, a brief flight into the meta-mathematical territory of models of set theory and the anti-foundation axiom, conclude the book.

The text is engaging, lively, and sophisticated; yet, I would like to point out some minor matters and make one serious criticism. The minor errors which mar the text include a mis-statement of the Generalized Continuum Hypothesis, making it trivially true, and an incorrect definition of continuity in 6.22, making some of the subsequent theorems false. Since there are also some editing failures and typographical errors, an errata sheet would be worthwhile.  Moreover, the index could be improved; I could find, for example, no reference for $N^*$ and the entry for Cantor Set refers to only one of the two independent definitions. It is also curious that when proving the uncountability of $\mathbb{R}$, Moschovakis does not give the proof that many would find to be the easiest for undergraduates to grasp: direct diagonalization against decimal expansions. Rather, he diagonalizes to deduce the uncountability of $2^{\mathbb{N}}$ and then launches into a construction of the Cantor set, obtained by omitting middle thirds; then, appealing to the the completeness property, he injects $2^{\mathbb{N}}$ into it and finishes the argument.

My one serious objection to the text is that while Moschovakis shows impressively that much mathematics can be done with the relatively weak Zermelo axioms, his decision to postpone the Replacement axiom until the end of the book has the consequence that students are deprived of ordinals exactly when ordinals would help them the most: when using well-orders, cardinal arithmetic, and tranfinite recursion. Without ordinals transfinite recursion is encumbered with the notation, such as $\mathop{\rm seg}_{\langle U,\leq_U\rangle}(x)$, which arises when one must carry an arbitrary well-order $\langle U,\leq_U\rangle$ through every proof. And he is forced to be satisfied with weak solutions to the cardinal assignment problem, in which $|A|=_{\rm def}A$ is, tacitly, the best option. Additionally, the late arrival of Replacement also makes students unduly suspicious of it.

In summary, Moschovakis’ view that all of classical mathematics takes place in $\cal Z$ should be tempered by his observation (p. 239) that neither HF nor indeed even $\omega$ exist in $\cal Z$. In this sense, $\cal Z$ is a small town. And so while he says “one can live without knowing the ordinals, but not as well” (p. 189), I wish that they had come much earlier in the book. Otherwise, the book is a gem, densely packed with fantastic problems and clear, elegant proofs.