# Set theory problem

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

Originally Posted by Bruno J.
Let $\displaystyle N=\{1,2,...,n\}$. Suppose we have a family $\displaystyle F$ of $\displaystyle 2^{n-1}$ subsets of $\displaystyle N$ such that the intersection of any three members of the family is nonempty. Show that there exists $\displaystyle x \in N$ which is common to all the elements of $\displaystyle 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 $\displaystyle A \subset N$, either $\displaystyle A$ or its complement $\displaystyle N-A$ is in $\displaystyle F$.
• Nov 9th 2009, 09:22 PM
Bruno J.
My solution :

Spoiler:

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

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