# Set theory problem

• Nov 5th 2009, 05:39 PM
Bruno J.
Set theory problem
Let $N=\{1,2,...,n\}$. Suppose we have a family $F$ of $2^{n-1}$ subsets of $N$ such that the intersection of any three members of the family is nonempty. Show that there exists $x \in N$ which is common to all the elements of $F$.
• Nov 5th 2009, 06:21 PM
Drexel28
Quote:

Originally Posted by Bruno J.
Let $N=\{1,2,...,n\}$. Suppose we have a family $F$ of $2^{n-1}$ subsets of $N$ such that the intersection of any three members of the family is nonempty. Show that there exists $x \in N$ which is common to all the elements of $F$.

Pigeonhole principle?
• Nov 5th 2009, 06:50 PM
Bruno J.
Quote:

Originally Posted by Drexel28
Pigeonhole principle?

The solution I found does not rely on the pigeonhole principle. Maybe it's possible to use it, but I don't think it would be the most straightforward.
• Nov 8th 2009, 02:11 PM
Bruno J.
Hint :

Spoiler:
Show that, given any subset $A \subset N$, either $A$ or its complement $N-A$ is in $F$.
• Nov 9th 2009, 09:22 PM
Bruno J.
My solution :

Spoiler:

Let $P(N)$ be the power set of $N$.
We show that given $A \in P(N)$, either $A \in F$ or $N-A \in F$. Indeed, both $A$ and $N-A$ cannot be in $F$ because their intersection is empty. Thus the map $g : F \rightarrow (P(N)-F)$ which maps $S \mapsto (N-S)$ is well-defined, and a bijection because $F$ contains $2^{n-1}$ elements. Since the domain and the image of this map partition $P(N)$, one of $A$ or $N-A$ must lie in $F$.

Now suppose $F$ is not closed under intersection. Then there exists $A,B \in F$ such that $(A \cap B) \notin F$. By the above, we must have that $N-(A \cap B)$ is in $F$. But $(N-(A \cap B))\cap A \cap B = \emptyset$, which contradicts the hypothesis that any three elements of $F$ have a nonempty intersection. Therefore $F$ is closed under intersection, and $\left(\cap_{A \in F}A\right)\in F$; since $F$ does not contain $\{\emptyset\}$ we are done.