# Prove that the intersection of all the sets is nonempty.

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)?

• I think by "all sets," it means "all sets in the set of the $2^{n-1}$ subsets". – Noble Mushtak Feb 1 '16 at 23:37
• 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. – Brian M. Scott Feb 1 '16 at 23:37
• How do I show that the set is nonempty? – user19405892 Feb 1 '16 at 23:45
• 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$. – DanielWainfleet Feb 2 '16 at 1:11
• @user254665 I wasn't assuming that. – 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$.

• 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? – user19405892 Feb 1 '16 at 23:57
• @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. – Brian M. Scott Feb 2 '16 at 0:04
• 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}$? – user19405892 Feb 2 '16 at 0:10
• @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. – Brian M. Scott Feb 2 '16 at 0:12
• So then if $A$ is some set of subsets of $S$, how can we exclude some subsets of $S$ from $S$? – 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}$.

• +1 (at first glance, anyway). First $S$ in the last paragraph has not been mathcal'd, by the way. – Brian Tung Feb 2 '16 at 0:33
• @ZoeH How come $S$ can't contain neither $A$ nor $X \setminus A$? – user19405892 Feb 2 '16 at 0:44
• @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. – Zoe H Feb 2 '16 at 0:49
• @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$? – user19405892 Feb 2 '16 at 1:26
• @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. – Zoe H Feb 2 '16 at 2:57