We call ${\cal A}\subseteq {\cal P}(\omega)$ almost disjoint if ${\cal A}\neq \varnothing$, every member of ${\cal A}$ is infinite, and for $A_1\neq A_2\in {\cal A}$ we have that $A_1\cap A_2$ is finite. Zorn's Lemma implies that every almost disjoint family is contained in a maximal almost disjoint (MAD) family.

If ${\cal A}$ is a maximal almost disjoint family, we say $I\subseteq \omega$ is independent if $I\not \supseteq A$ for every $A\in{\cal A}$.

Question. Given a MAD family ${\cal A}$, is there necessarily a maximal independent subset $I$ for ${\cal A}$, with respect to $\subseteq$?


1 Answer 1


No, a given MAD family does not necessarily admit a maximal independent subset.

The key notion here is that of a completely separable MAD family. This means a MAD family $\mathcal A$ having the property that for every $X \subseteq \omega$, either $X \subseteq \bigcup \mathcal A_0$ for some finite $\mathcal A_0 \subseteq \mathcal A$, or else there is some $A \in \mathcal A$ with $A \subseteq X$.

It is consistent that such families exist. It is still (I think) an open question whether $\mathsf{ZFC}$ proves the existence of a completely separable MAD family. The question of whether this is true was raised by Erdős and Shelah in the early 70's. Balcar and Simon proved that it is consistent for completely separable MAD families to exist under a wide variety of hypotheses ($\mathfrak{a} = \mathfrak{c}$, or $\mathfrak{b} = \mathfrak{d}$, or $\mathfrak{d} \leq \mathfrak{a}$, or $\mathfrak{s} = \aleph_1$). Years later, Shelah proved that the existence of completely separable MAD families follows from either $\mathfrak{s} \leq \mathfrak{a}$, or else $\mathfrak{a} < \mathfrak{s}$ plus a certain PCF hypothesis that might be (but is not known to be) a theorem of $\mathsf{ZFC}$. The failure of this hypothesis implies $\mathfrak{c} > \aleph_\omega$ and (I think) the consistency of large cardinals. More information can be found in this paper of Osvaldo Guzman (see especially the bottom of page 2 and top of page 3).

This is relevant to your question because:

Observation: If $\mathcal A$ is a completely separable MAD family (and $\mathcal A$ is infinite), then there is no maximal independent set for $\mathcal A$.

The reason: If $I \subseteq \omega$ and $I \not\supseteq A$ for every $A \in \mathcal A$, then because $\mathcal A$ is completely separable, there is some finite $\mathcal A_0 \subseteq \mathcal A$ with $I \subseteq \bigcup \mathcal A_0$. But (as $\mathcal A$ is infinite) $\omega \setminus \bigcup \mathcal A_0$ is infinite. But if $n \in \omega \setminus \bigcup \mathcal A_0$, then $I \cup \{n\}$ is still "independent" in the sense that $I \cup \{n\} \not\supseteq A$ for every $A \in \mathcal A$. Thus $I$ is not maximal with respect to this property.

  • $\begingroup$ +1 I suppose it is still possible that a MAD family with no maximal independent set can somehow be constructed in ZFC, without settling the question of completely separable families? There's no reason a MAD family with no maximal independent set would have to be completely separable, is there? By the way, didn't Steve Hechler also do some pioneering work on completely separable families? $\endgroup$
    – bof
    Mar 9, 2021 at 7:56
  • $\begingroup$ Wow - thanks @Will - it's interesting that this digs into an open question! $\endgroup$ Mar 9, 2021 at 8:14
  • $\begingroup$ @bof: You're correct on both counts. I don't see any reason why a MAD family answering Dominic's question needs to be completely separable, and so there might be a relatively easy construction of one in ZFC. And I think Hechler was the first to define completely separable MAD families, even though the question of whether their existence is provable in ZFC is attributed to Erdos & Shelah. $\endgroup$
    – Will Brian
    Mar 9, 2021 at 10:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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