In this article the author proves that every AD family that is countable can be extended to an AD family by at least one set. (Lemma 2.1)

On the next page he observes that using Zorn's lemma we can extend any AD family to a MAD family. And then, in Corollary 2.3, he proves that there is an uncountable almost disjoint family of subsets of $\omega$ by choosing a partition $(A_n)_{n \in \omega}$ of $\omega$ into pairwise disjoint, in finite sets.

Is it possible to have such a partition? What would be an explicit definition of $\omega$ into $\omega$ disjoint infinite sets?


Enumerate the primes $p_0 , p_1 , \ldots$. For each $i \in \omega$ let $A_i = \{ p_i^k : k \geq 1 \}$, $A_\omega = \omega \setminus \bigcup_i A_i$.

Or take your favourite bijection $f : \omega \to \omega \times \omega$ and define $A_i = f^{-1} [ \{ i \} \times \omega ]$.

  • $\begingroup$ Great, I had to be offline until now and while offline I thought exactly of this same example with the primes : D The only thing I hadn't figured out is that I could define an $A_\omega$ to deal with the remaining numbers. $\endgroup$ – Rudy the Reindeer Apr 18 '13 at 14:37
  • 1
    $\begingroup$ @MattN. When all else fails, shove everything left into its own set! You could also define $A_i$ to be all numbers $n>1$ such that $p_i$ is the largest prime factor of $n$, and then shove $0$ and $1$ into some random set. Primes are good. ;) $\endgroup$ – user642796 Apr 18 '13 at 15:37

Let $f\colon\omega\to\omega\times\omega$ be a bijection, then $A_n=f^{-1}(\{n\}\times\omega)$ is a partition of $\omega$ into $\omega$ disjoint sets.

If you want an almost-disjoint partition of size $\frak c$, for every $r\in\Bbb R$ fix a sequence of rationals $r_n$ converging to $r$; let $q_n$ be an enumeration of the rationals, and take $A_r=\{k\in\omega\mid\exists n.q_k=r_n\}$ be an almost-disjoint family.

The use of Zorn's lemma is essential, by the way. In some models without the axiom of choice (e.g. Solovay's model, or models of $\sf ZF+AD$) there is no maximal antichain in $\cal P(\omega)/\sf fin$ - which would be exactly a MAD family.

  • $\begingroup$ This idea with sequences converging to irrationals me gusta. Thank you for sharing it. $\endgroup$ – Rudy the Reindeer Apr 18 '13 at 15:47
  • $\begingroup$ Matt, why irrationals? Every real number! $\endgroup$ – Asaf Karagila Apr 18 '13 at 15:53
  • $\begingroup$ Sometimes my brain does funny things. That's why. Now I'm trying to work out whether it's broken if it's only irrationals. And I think the answer is yes. One can easily avoid $1/2$ in all sequences. $\endgroup$ – Rudy the Reindeer Apr 18 '13 at 16:02
  • 1
    $\begingroup$ @Matt: It's not broken; but you can extend that family by adding infinitely many more sets! Why lose on the rationals? That would be irrational! :-) $\endgroup$ – Asaf Karagila Apr 18 '13 at 16:03
  • $\begingroup$ No, if you pick $(r_n)$ all in $\mathbb Q \setminus \{1/2\}$ then $k$ with $q_k = 1/2$ will not be in any $A_r$. Hence it's not a partition. One can fix it though in the same way Arthur did in his prime answer: stuff all the remaining numbers, in this case $k$, into the same set. $\endgroup$ – Rudy the Reindeer Apr 18 '13 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.