Almost disjoint sets

It is intuitive and easy to see that if $A$ is a countable set and $\{ A_\gamma \}_{\gamma \in \Gamma}$, where $A_\gamma \subset A$, is a disjoint collection of subsets, then $\Gamma$ 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 $A_{\gamma}$ 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 $A$ be a set. We call a collection of its subsets $\{ A_\gamma \}_{\gamma \in \Gamma}$, $A_\gamma \subset A$ almost disjoint, if for any $\gamma_1, \gamma_2\in\Gamma$ the intersection $A_{\gamma_1} \cap A_{\gamma_2}$ is finite.

The question is, if $A$ is countable and $\{ A_\gamma \}_{\gamma\in\Gamma}$ is an almost disjoint collection of its subsets, then is it true that $\Gamma$ 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 $x \in \mathbb{R}$ be a real number and let $Q_x \subseteq \mathbb{Q}$ be a bounded subset of rationals such that the only cluster point of $Q_x$ is $x$. (But $x$ is indeed a cluster point.) It is clear that there are uncountably many $Q_x$ 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 $Q_x$ has only one limit point.

Counterexample 2. (Halmos) Consider the set of lattice points $\mathbb{Z}^2$. Define the sets

$S_\theta = \mathbb{Z}^2 \cap \{ (x, y) \in \mathbb{R}^2: |x \cos \theta + y \sin \theta | \leq 2| \}$

for each $0\leq\theta < 2\pi$. $S_\theta$ is an intersection of the lattice points and a wide strip of angle $\theta$, something like this.

Because no two such strips has infinite intersection, it is easy to see that the collection $\{ S_\theta \}_{0 \leq \theta < 2\pi}$ is an almost disjoint collection of subsets of $\mathbb{Z}^2$.

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 $x = (\epsilon_1,\epsilon_2,\dots)$ 0-1 sequence associate a subset of $\mathbb{N}$ obtained by taking the union of those sets which are traversed on the path along the edges $\epsilon_1, \epsilon_2, \dots$ starting from $\{ 1 \}$. For example, the sequence $x_0 = (1,0,1,\dots)$ is associated with the set $P_{x_0} = \{ 1, 3, 6, 13, \dots \}$. Once more it is clear that $\{ P_x \}_{x\in {0,1}^\omega}$ is an almost disjoint collection from the subsets of $\mathbb{N}$, however they are not countable.