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

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}$.

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$.