Set theory problem

Printable View

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