It is intuitive and easy to see that if is a countable set and , where , is a disjoint collection of subsets, then is countable. (Although one has to be careful with saying “intuitive” and “easy to see” in set theory.) A natural question is, what happens if we allow the sets to have nonempty but finite intersections? This question was posed in Halmos’ classic problem book Problems for Mathematicians: Young and Old, and this short post is dedicated to a few solutions.
Definition. Let be a set. We call a collection of its subsets , almost disjoint, if for any the intersection is finite.
The question is, if is countable and is an almost disjoint collection of its subsets, then is it true that is countable?
The answer is surprisingly no. I shall give three counterexamples for this. The first two is due to Halmos (which can be found in his magnificent book Problems for Mathematicians: Young and Old), the third one is my construction.
Counterexample 1. (Halmos) Let be a real number and let be a bounded subset of rationals such that the only cluster point of is . (But is indeed a cluster point.) It is clear that there are uncountably many sets as there are uncountably many real numbers. It is also quite easy to see that they are almost disjoint, because if they are not, it contradicts the assumption that each has only one limit point.
Counterexample 2. (Halmos) Consider the set of lattice points . Define the sets
for each . is an intersection of the lattice points and a wide strip of angle , something like this.
Because no two such strips has infinite intersection, it is easy to see that the collection is an almost disjoint collection of subsets of .
Counterexample 3. Imagine an infinite rooted binary tree with its edges labelled using zeros and ones. If an edge points to the right, it has label 1, otherwise it has label 0. Something like this, just infinite.
Now, instead of vertices, we shall write singleton sets of natural numbers in a way such that each number occurs at most once.
It is known that the set of infinite 0-1 sequences is not countable. For each 0-1 sequence associate a subset of obtained by taking the union of those sets which are traversed on the path along the edges starting from . For example, the sequence is associated with the set . Once more it is clear that is an almost disjoint collection from the subsets of , however they are not countable.