Given $2^{n-1}$ subsets of a set with $n$ elements with the property that any three have nonempty intersection, prove that the intersection of all the sets is nonempty.

I find this question a bit odd since why couldn't they have said we just have $2^{n-1}$ sets with this property? Also by all sets does it just mean sets in the $2^{n-1}$ subsets? I would say let each of the subsets be $A_i$. Then $A_i \cap A_j \cap A_k = A_m$ for some $i,j,k,m$ in $1 \leq i,j,k,m \leq 2^{n-1}$. Then $A_1 \cap A_2 \cap \cdots \cap A_n = (A_1 \cap A_2 \cap A_3)\cap(A_4 \cap A_5 \cap A_6) \cap \cdots \cap (A_{2^{n-1}-2} \cap A_{2^{n-1}-1} \cap A_{2^{n-1}})$. How do I show this is nonempty (given that I am interpreting the question correctly)?

  • $\begingroup$ I think by "all sets," it means "all sets in the set of the $2^{n-1}$ subsets". $\endgroup$ – Noble Mushtak Feb 1 '16 at 23:37
  • 1
    $\begingroup$ It doesn’t say all sets: it says all the sets, where the article the indicates that it refers to the $2^{n-1}$ subsets. $\endgroup$ – Brian M. Scott Feb 1 '16 at 23:37
  • $\begingroup$ How do I show that the set is nonempty? $\endgroup$ – user19405892 Feb 1 '16 at 23:45
  • $\begingroup$ You cannot assume that $A_i\cap A_j \cap A_k=A_m$. You can only say that $A_i\cap A_j \cap A_k \ne \phi$. $\endgroup$ – DanielWainfleet Feb 2 '16 at 1:11
  • $\begingroup$ @user254665 I wasn't assuming that. $\endgroup$ – user19405892 Feb 2 '16 at 1:12

SKETCH: Let $\mathscr{A}$ be the family of subsets of $S$, a set with $n$ elements. $S$ has $2^n$ subsets, so $\mathscr{A}$ contains exactly half of them. If $A\in\mathscr{A}$, then clearly $S\setminus A\notin\mathscr{A}$ (why?), so $\mathscr{A}$ contains exactly one of $A$ and $S\setminus A$ for each $A\subseteq S$.

Suppose that there is no $s\in S$ such that $\{s\}\in\mathscr{A}$, so that $S\setminus\{s\}\in\mathscr{A}$ for each $s\in S$.

  • Show that if $F\subseteq S$, and $|F|\le 3$, then $S\setminus F\in\mathscr{A}$, and therefore $F\notin\mathscr{A}$. Thus, $\mathscr{A}$ contains no subset of $S$ of cardinality $3$ or less.
  • Repeat the idea to show that $\mathscr{A}$ contains no subset of $S$ of cardinality $9$ or less. Then show by induction that $\mathscr{A}$ is empty.

This is impossible, so we conclude that $\{s\}\in\mathscr{A}$ for some $s\in S$.

  • Suppose that $A\subseteq B\subseteq S$, and $A\in\mathscr{A}$; show that $B\in\mathscr{A}$.
  • Conclude that $\mathscr{A}=\{A\subseteq S:s\in A\}$, and $\bigcap\mathscr{A}=\{s\}\ne\varnothing$.

As an aside, the argument shows that $\mathscr{A}$ is a fixed (or principal) ultrafilter on $S$.

  • $\begingroup$ Was my claim that $A_i \cap A_j \cap A_k = A_m$ for some $i,j,k,m$ in $1 \leq i,j,k,m \leq 2^{n-1}$ correct? $\endgroup$ – user19405892 Feb 1 '16 at 23:57
  • $\begingroup$ @user19405892: It turns out to be true, but it isn’t an obvious consequence of the hypotheses. At the moment I see no way to prove it other than to prove the final result in my answer. $\endgroup$ – Brian M. Scott Feb 2 '16 at 0:04
  • $\begingroup$ Also isn't it obvious that if $A \in \mathscr{A}$ then $S \setminus A \not \in \mathscr{A}$ since $S$ contains elements not in $\mathscr{A}$ and as a result $S \setminus A \not \in \mathscr{A}$? $\endgroup$ – user19405892 Feb 2 '16 at 0:10
  • $\begingroup$ @user19405892: (You can get the set difference symbol with \setminus.) The statement that $S$ contains elements not in $\mathscr{A}$ doesn’t make sense: elements of $\mathscr{A}$ are subsets of $S$, not elements. $\endgroup$ – Brian M. Scott Feb 2 '16 at 0:12
  • $\begingroup$ So then if $A$ is some set of subsets of $S$, how can we exclude some subsets of $S$ from $S$? $\endgroup$ – user19405892 Feb 2 '16 at 0:18

Let $X$ be a set with $n$ elements and $\mathcal{S}$ be a set of $2^{n-1}$ subsets of $X$ such that for any $A,B,C \in \mathcal{S}$ we have $A \cap B \cap C \neq \emptyset$.

So $\mathcal{S}$ contains half of the subsets of $X$ and if $A \subseteq X$ then $\mathcal{S}$ cannot contain both $A$ and $X \setminus A$, so exactly one of $A$ and $X \setminus A$ is in $\mathcal{S}$.

If $A,B \in \mathcal{S}$ then $A \cap B \in \mathcal{S}$, since otherwise $X \setminus (A \cap B) \in \mathcal{S}$ and $A \cap B \cap (X \setminus (A \cap B)) = \emptyset$.

Since $\mathcal{S}$ is finite, it follows that $\bigcap_{A \in \mathcal{S}}A \in \mathcal{S}$. Clearly $\emptyset \notin \mathcal{S}$.

  • $\begingroup$ +1 (at first glance, anyway). First $S$ in the last paragraph has not been mathcal'd, by the way. $\endgroup$ – Brian Tung Feb 2 '16 at 0:33
  • $\begingroup$ @ZoeH How come $S$ can't contain neither $A$ nor $X \setminus A$? $\endgroup$ – user19405892 Feb 2 '16 at 0:44
  • $\begingroup$ @user19405892 There are $2^{n-1}$ pairs of complementary subsets of $X$, and $\mathcal{S}$ contains at most one from each pair. Since $\mathcal{S}$ contains $2^{n-1}$ subsets of $X$, it must contain exactly one from each pair. $\endgroup$ – Zoe H Feb 2 '16 at 0:49
  • $\begingroup$ @ZoeH Can you elaborate why "If $A,B \in \mathcal{S}$ then $A \cap B \in \mathcal{S}$, since otherwise $X \setminus (A \cap B) \in \mathcal{S}$ and $A \cap B \cap (X \setminus (A \cap B)) = \emptyset$." Why is it true that if $A \cap B \not \in S$, then $X \setminus (A \cap B) \in S$? $\endgroup$ – user19405892 Feb 2 '16 at 1:26
  • $\begingroup$ @user19405892 $A \cap B$ is a subset of $X$ so either $A \cap B \in \mathcal{S}$ or $X \setminus (A \cap B) \in \mathcal{S}$ for the same reasons as in my last comment. $\endgroup$ – Zoe H Feb 2 '16 at 2:57

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.