10
$\begingroup$

Let $X$ be a non-empty set, and let ${\cal S}\subseteq {\cal P}(X)$ be family of non-empty subsets of $X$. We say that ${\cal S}$ is intersecting if any two members of ${\cal S}$ have non-empty intersection.

Zorn's Lemma implies that every intersecting family is contained in a maximal intersecting family with respect to set inclusion $\subseteq$.

If we consider the set of natural numbers $\omega$, the family of all subsets of $\omega$ containing $0$ as an element is a maximal intersecting family, and more generally, so is every ultrafilter on $\omega$.

Question. If $X$ is infinite and ${\cal S}\subseteq{\cal P}(X)$ is a maximal intersecting family, does ${\cal S}$ have cardinality $2^{|X|}$?

$\endgroup$

2 Answers 2

12
$\begingroup$

Let $\mathcal S$ be a maximal intersecting family of subsets of a nonempty set $X$. Note that, for each set $A\subseteq X$, exactly one of the sets $A$ and $X\setminus A$ belongs to $\mathcal S$. It follows that $|\mathcal S|=2^{|X|-1}$ if $X$ is finite, and $|\mathcal S|=2^{|X|}$ if $X$ is infinite.

P.S. Of course the equality $|\mathcal S|=2^{|X|}$ for infinite $X$ depends on the axiom of choice; it will fail, e.g., if $2^{|X|}$ is Dedekind-finite. However, in ZF we can say that $2|\mathcal S|=2^{|X|}$ whether $X$ is finite or infinite.

P.P.S. In ZF, if $|X|\ge\aleph_0$, then $|X|=|X|+1$ and so we have $$2|\mathcal S|=2^{|X|}=2^{|X|+1}=2\cdot2^{|X|}\implies|\mathcal S|=2^{|X|}$$ since we can cancel a factor of $2$ in ZF.

$\endgroup$
2
  • 2
    $\begingroup$ Congratulations for this elegant argument! I have been amazed by many of your posts. I have accepted Joel's answer already and don't want to change this, but your argument would have also deserved it. $\endgroup$ Commented Oct 10, 2023 at 21:48
  • 3
    $\begingroup$ @DominicvanderZypen It is fine to switch the accepted answer to bof's very nice answer, which I think is the right way to look at it. $\endgroup$ Commented Oct 11, 2023 at 5:59
14
$\begingroup$

The answer is yes.

Consider first for simplicity the case where $X$ is countably infinite. If $\mathcal{S}$ is a maximal intersecting family, then I claim that $\mathcal{S}$ must contain a set with infinite complement, since otherwise it would have only cofinite sets and we could add any infinite/coinfinite set, contrary to maximality. But now notice that since every superset of a set in $\mathcal{S}$ must also be in $\mathcal{S}$, this will put continuum many sets into $\mathcal{S}$, as desired.

A similar argument works with higher cardinals. Namely, for any infinite set $X$ of size $\kappa$, if $\mathcal{S}$ is a maximal intersecting set, then $\mathcal{S}$ must contain some set with size $\kappa$ complement, since if not, then every set in $\mathcal{S}$ would have small complement, and so we could extend $\mathcal{S}$ by adding any set of size $\kappa$ not like that. If $Y\in\mathcal{S}$ has complement of size $\kappa$, then all the supersets of $Y$ will also be in $\mathcal{S}$ by maximality, and there are $2^\kappa$ many.

So the answer is fully yes for every infinite cardinality.

$\endgroup$
3
  • 1
    $\begingroup$ Assuming AC of course. But I guess even in ZF we can say that $2|\mathcal S|=2^{|X|}$. $\endgroup$
    – bof
    Commented Oct 11, 2023 at 1:09
  • 1
    $\begingroup$ Yes, though I guess one just needs $|X|=2|X|$ for the conclusion, and this is much less than AC. Even in ZF we get the result for all well-ordered infinite $X$---no need to well-order $\mathcal{S}$ or $P(X)$. Meanwhile, your answer is clearly the right way to do it. $\endgroup$ Commented Oct 11, 2023 at 6:41
  • 2
    $\begingroup$ I think we just need $|X|=|X|+1$ (i.e. $|X|\ge\aleph_0$) since $$2|\mathcal S|=2^{|X|}=2^{|X|+1}=2\cdot2^{|X|}\implies|\mathcal S|=2^{|X|}.$$ $\endgroup$
    – bof
    Commented Oct 11, 2023 at 7:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .