Cardinal Rules

1. Pick your favorite countable set S. Let F be a 'nested' family of distinct subsets of S; that is, if A, B are members of F, then either A is contained in B or B is contained in A.

Then clearly F can be at most countable... right?


A puzzle from Bollobas' recent book.


2. Given a collection C of functions from N = {1, 2, 3, ...} to N, say that C is unbounded if for any function f (in C or not), there exists a function g in C such that g(i) > f(i) for infinitely many i.

Clearly the class C of all functions from N to N is unbounded. Also, standard diagonalization techniques tell us that no countable collection C can be unbounded (exercise).

The question then becomes: what is the smallest cardinality of any unbounded collection C? Assuming the Continuum Hypothesis is false, where does the threshold lie?

Fortunately or unfortunately, there seems to be little we can say about this issue within the standard axioms of set theory. Assuming CH is false, the threshold could be as low as the first uncountable cardinal, or as large as the continuum, or in between--this I learned from Jech's encyclopedic book Set Theory. There are many questions of this flavor, where the key construction (in our case, constructing a 'bounding function' for a given 'small' collection C) is easy to do in the countable setting, but essentially impossible to analyze when there are uncountably many requirements floating around.

The need to satisfy uncountable collections of requirements in a construction is so common that new axioms for set theory are put forward expressly to assert the possibility of doing so (under some restrictions that make the axioms plausible); 'Martin's Axiom' is an especially widely used axiom of this type. Kunen's book on set theory seems like a good reference for MA (though I'm just starting to learn about it).

Of course, the Continuum Hypothesis itself makes it easier to satisfy collections of requirements of size smaller than continuum, since such requirements are then at most countable! This leads to some bizarre constructions, the possibility of many of which stands or falls with the CH itself. The excellent book Problems and Theorems in Classical Set Theory gives many of these, and Bill Gasarch recently exposited one such application in Euclidean Ramsey theory. On the other hand, Martin's Axiom, which is independent of CH, allows set theorists to prove many interesting results while remaining more 'agnostic' about cardinality issues.


I think that set theory is a blast, and that its logical structure resonates with issues in computer science. But I'm far from expert on the subject, so if I've said anything inaccurate please let me know.