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.

A set consists of the lattice points inside the infinite blue strip

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.

Infinite rooted binary tree with labeled edges

Now, instead of vertices, we shall write singleton sets of natural numbers in a way such that each number occurs at most once.

Instead of vertices, we have a disjoint collection of sets


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 \varepsilon_1, \varepsilon_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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s