Challenge II: Almost Disjoint Sets, solved by HS-Scientist

[Greg Bernhardt]

Written by micromass:

The newest challenge was the following:

Prove that ##\mathbb{N}## contains uncountably many subsets ##(N_\alpha)_{\alpha \in \mathbb{R}}## such that ##N_\alpha\cap N_\beta## is finite if ##\alpha\neq \beta##.

This was solved by HS-Scientist. Here's his solution:

For any [itex] a \in [0.1,1) [/itex], define [itex] S_a=(\lfloor 10a \rfloor,\lfloor 100a \rfloor...,\lfloor 10^na \rfloor...) [/itex]. For example, [itex] S_\frac{\pi}{10}=(3,31,314,...) [/itex]

Note that for all a, [itex] S_a [/itex] has exactly one n-digit number for every natural n because [itex] 10^{n-1} \leq \lfloor 10^na \rfloor< 10^n [/itex] if [itex] a \in [0.1,1) [/itex]

Since for every n, the n-digit element of [itex] S_a [/itex] corresponds to the first n digits of a, the only way that [itex] S_a [/itex] and [itex] S_b [/itex] can share infinitely many elements is if a and b are equal.


Now, to extend this to all real numbers, we to prove the existence of a bijection from the set of real numbers to [0.1,1). This is equivalent to showing that [.1,1) and ℝ have the same cardinality. The cardinality of [.1,1) is no greater than that of ℝ because there is an injection from [.1,1) to ℝ (the identity function, for example). The cardinality of ℝ is no greater than that of [.1,1) because there is an injection from ℝ to [.1,1) (f defined by f(x)=arctan(x)/π + 1/2 does the trick). Therefore the cardinalities of ℝ and [.1,1) are the same and a bijection exists between them.

This is a very beautiful construction. Here's yet another way of showing it.

Definition: Let ##X## be a countable set. Let ##A,B\subseteq X##, we say that ##A## and ##B## are almost disjoint if ##|A\cap B|## is finite. An almost disjoint family is a collection of subsets of ##X##, thus ##\mathcal{A}\subseteq \mathcal{P}(X)## such that every ##A\in \mathcal{A}## is infinite and such that any two distinct elements in ##\mathcal{A}## are almost disjoint.

First we prove a lemma:

Lemma: Define for a set ##X##, the set ##\mathcal{P}_\text{fin}(X) = \{A\subseteq X~\vert~A~\text{is finite}\}##. If ##X## is countable, then so is ##\mathcal{P}_\text{fin}(X)##.

Let ##\mathcal{A}_k## be the collection of all ##k##-element subsets of ##X##. That is
[tex]\mathcal{A}_k = \{A\subseteq X~\vert~ |A| = k\}[/tex]
There is clearly a surjection from ##X^k## to ##\mathcal{A}_k##. This is given by sending ##(x_1,...,x_k)## to ##\{x_1,...,x_k\}##. So since ##X## is countable, we have that ##X^k## is countable. Hence ##\mathcal{A}_k## is countable. But now we see that
[tex]\mathcal{P}_\text{fin}(X) = \bigcup_k \mathcal{A}_k[/tex]
is a countable union of countable sets, and is thus countable.

So instead of finding an almost disjoint family of ##\mathbb{N}##, we might as well find such a family on ##\mathcal{P}_\text{fin}(X)##.

To do this, take any infinite subset ##X\subseteq \mathbb{N}##. Define
[tex] A_X = \{X\cap \{0\},~X\cap \{0,1\},~X\cap \{0,1,2\},...,X\cap \{0,1,2,...,n\},...\}[/tex]
Then the ##A_X## are clearly an almost disjoint family.
Furthermore, there is a bijection between ##\{X\subseteq \mathbb{N}~\vert~X~\text{is infinite}\}## and ##\mathbb{R}##, so we have found our almost disjoint family.

Another solution that I got, was from jgens who did a very beautiful diagonal argument. It comes down to this:

Definition: A maximal almost disjoint family ##\mathcal{A}## of ##X## is an almost disjoint family that is not properly contained in any other almost disjoint family.

From Zorn's lemma, we can immediately get the existence of a maximal disjoint family. This almost disjoint family cannot be countable. Indeed, if it were countable, then it wouldn't be maximal. Here is a proof of this that uses a very clever diagonal argument:

Assume that ##\mathcal{A} = \{A_n~\vert~n\in \mathbb{N}\}## is a countable almost disjoint family. Let
[tex]B_n = A_n\setminus \bigcup_{m<n} A_m[/tex]
Then ##B_n\neq \emptyset##, because
[tex]B_n = A_n \setminus \bigcup_{m<n} (A_m\cap A_n)[/tex]
and ##A_n## is infinite and ##\bigcup_{m<n}(A_m\cap A_n)## is finite.

Now, pick ##b_n\in B_n##. Then the ##b_n## are all distinct since the ##B_n## are disjoint. Thus ##D=\{b_n~\vert~n\}## is infinite. It is clear that if ##b_n\in A_m##, then ##n\leq m##, thus ##D\cap A_m## is finite. Thus ##\mathcal{A}\cup \{D\}## is a larger almost disjoint family.

The problem with this solution is of course that we have only found an uncountable almost disjoint family. But we do not necessarily have an almost disjoint family that is in bijection with ##\mathbb{R}##.

However, both arguments are very useful in generalizations. A natural generalization of this problem is the following:

Definition: Let ##X## be an infinite set. Let ##A,B\subseteq X##, we say that ##A## and ##B## are almost disjoint if ##|A\cap B|<|X|##. An almost disjoint family is a collection of subsets of ##X##, thus ##\mathcal{A}\subseteq \mathcal{P}(X)## such that every ##|A| = |X|## for every ##A\in \mathcal{A}## and any two distinct elements in ##\mathcal{A}## are almost disjoint.

Both arguments can be generalized to this situation, but they both use other hypotheses. The argument by Hs-Scientist generalizes nicely if the cardinality of ##\{A\subseteq X~\vert~|A|<|X|\}## is equal to ##|X|##. This is a very restrictive condition. But in this case we can show that there is an almost disjoint family of cardinality ##2^{|X|}##.

The jgens argument generalizes much better since it doesn't require such a restrictive condition. On the other hand, we do not get an almost disjoint family of cardinality ##2^{|X|}##. We can only infer that there is an almost disjoint family that has cardinality strictly greater than ##|X|##.

Finally, I would like to mention the following problem: If ##\mathcal{A}## is an almost disjoint family of ##\mathbb{N}##. If ##\mathcal{A}## is not in bijective correspondance with ##\mathbb{R}##, does ##\mathcal{A}## then fail to be maximal?

We have seen that there is a maximal family of cardinality ##\mathbb{R}##, but that doesn't mean that they're all of this cardinality. With other words, can we extend any almost disjoint family to a maximal disjoint family of cardinality ##\mathbb{R}##?

The answer is that this is independent of the ZFC axioms. We require a new axiom. Under the Continuum Hypothesis, the answer to this is trivially yes (since if ##\mathcal{A}## does not have size ##|\mathbb{R}|##, then it is countable).

However, there is another axiom that is sometimes interesting. This is called Martin's axiom. This is an axiom that is studied very deeply in set theory and has many interesting consequences. Under this axiom, the answer is again yes.

For more information, I refer to "Set Theory, an Introduction to Independence Proofs" by Kunen.

Congratulations to HS-Scientist and jgens for their nice and elegant solutions!

 

[fresh_42]

The proof that ##\mathcal{P}(\mathbb{N})## is uncountable is surprisingly short:
http://www.cs.xu.edu/csci250/06s/Theorems/powerSetuncountable.pdf