You are here

Combinatorial Set Theory

Lorenz J. Halbeisen
Publication Date: 
Number of Pages: 
Springer Monographs in Mathematics
[Reviewed by
Michael Berg
, on

In a past, more innocent, age I was heavily enamored of set theory — well, I still am, but I’m not so innocent anymore, in that I now know better just how rough it can be. But it is still very interesting and even spellbinding in its results and claims, all modulo the understanding that upon closer inspection things are being perpetrated on the innocent reader that might very well cause anything from mild anxiety to out and out panic. Regarding the latter contingency, I recall the effect that Cantor’s “diagonal argument that fails” (showing that \([0,1)\) is uncountable) had on a friend of mine over forty years ago: as we were strolling down Westwood Boulevard near UCLA, in the wake of a class where this had been dealt with, she raged about the result in anger and, my best efforts notwithstanding, I was unable to talk her down. C’est la vie, I guess: it goes to show you never can tell — with apologies to Chuck Berry, RIP.

All right, then, let’s get to the book under review. We all know something about set theory, of course, so what’s with the “combinatorial” prefix? Clearly the place to look is the Preface, and we find this:

This book provides a self-contained introduction to Axiomatic Set Theory, the main focus being … Infinitary Combinatorics and the Forcing Technique.

Well the method of forcing goes back to Paul Cohen who famously used it to demonstrate the independence of the continuum hypothesis, but what’s infinitary combinatorics? Turn to page 3 of the book, and we find the following passage by Halbeisen:

Combinatorics is the branch of mathematics which studies collections of objects that satisfy certain criteria, and is in particular concerned with deciding how large or how small such collections might be. If the collections being considered are infinite, we speak of infinitary Combinatorics.

He goes on to give some examples (good ones!), e.g. König’s Lemma (“Every infinite, finitely branching tree contains an infinite branch”). Next, consider a classic of “ordinary” combinatorics, i.e. van der Waerden’s Theorem: “for and positive integers \(r\) and \(n\), there is a positive integer \(N\) such that for every \(r\)-coloring of the set \(\{0,1,\dots, N\}\) we can always find a monochromatic (non-constant) arithmetic progression of length \(N\).” Halbeisen goes on to contrast this result (“one of the earliest results in Ramsey theory”) with something more infinitary, viz. Ramsey’s own theorem: “… If we color all \(n\)-element subsets of \(\mathbb{N}\) with finitely many colors, then there exists an infinite subset of \(\mathbb{N}\) all of whose \(n\)-element subsets have the same color.” Ramsey theory mavens will recognize in the foregoing an infinitary counterpart to the famous party problem asking for the smallest number of people at a party such that one is guaranteed there are trios which know or don’t know each other: graph theory gives the number as six. Parenthetically, this is a very nasty business: if we go for quintettes instead of trios, “the precise number is not known — but … is conjectured [to be] 43 …”

More to the point, Halbeisen notes that Ramsey’s theorem, as given above, can do yeoman’s work in set theory without the Axiom of Choice (which is also independent, hence its dispensability) in the sense that it can aid in the construction of a choice function. This is in itself worth the price of admission.

A propos, when it comes to the independence of such things as CH (continuum hypothesis) and AC (Axiom of Choice), from ZF (Zermelo-Frankel set theory), it is famously Paul Cohen’s method of forcing that has brought home the bacon, and Halbeisen certainly gives this a lot of air-play: witness his subtitle, with its amusing play on words, “… a gentle introduction for forcing.” Additionally he notes (cf. p.6) that

[w]ith the forcing technique — invented by Paul Cohen in the early 1960s — on can show that the axioms of Set Theory do not decide CH. In other words, there are models of Set Theory in which CH holds, and other models in which CH fails … The forcing technique to construct such models is introduced in Part III…

And so we’re at the point of looking at this big book’s architecture. Part I is innocuously titled “Preliminary,” and does such things as first-order logic (“in a nutshell”), ZF and ZFC. Part II deals with combinatorial set theory and starts off with Ramsey theory. But then it departs in infinitary directions, covering such things as cardinal and ordinal numbers, different flavors of the Axiom of Choice, model theory, and then, well, I guess we’d call it infinitary Ramsey theory in keeping with the above remarks.

Part III begins with Martin’s Axiom, rather a sophisticated affair dealing with partially ordered sets satisfying a countable chain condition, and stipulating the existence of certain kinds of filters. Obviously we are not in Kansas anymore: this is serious stuff requiring quite a bit of background and/or Sitzfleisch. Suffice it to say that Halbeisen uses Martin’s Axiom to get to Cohen’s method of forcing, one goal of which is to be able to construct models of appropriate bounded cardinalities, in which certain axioms fail, as already hinted earlier.

After all this we get to Part IV, the book’s last part, titled “Combinatorics of forcing extensions.” Yes, this is very serious set theory, as is suggested by such chapters as “How many Ramsey ultrafilters exist?” and (the perhaps somewhat innocuous sounding chapter) “Combinatorial properties of sets of partitions.” Finally the very last chapter, titled, ”Suite,” and sporting such subsections as Allemande, Sarabande, and Gigue, as befits its musical parallel, aims at “demontrat[ing] how the tools we developed in the previous chapters can be used to shed new light on a classical problem in Measure Theory.” Says Halbeisen:

Assuming the Continuum Hypothesis, Banach and Kuratowski proved a combinatorial theorem which implies that a finite measure defined for all subsets of \(\mathbb{R}\) vanishes identically if it is zero for points … It will be shown that [this result] is equivalent to the existence of a \(K\)-Suslin set of size \(\mathfrak{c}\) and that the existence of such a set is independent of \(\mathrm{ZFC}+\neg\mathrm{CH}\).

Yes, indeed: set theory with a vengeance. And that describes this book to a tee. It’s very big, very heavy, and will doubtless resonate very well with the set-theory in-crowd. Forcing has long been a big deal in set theory and so this book is right on target.

Michael Berg is Professor of Mathematics at Loyola Marymount University in Los Angeles, CA.

The table of contents is not available.