Results 1 to 5 of 5

Thread: Set theory problem

  1. #1
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1

    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$.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    22
    Quote Originally Posted by Bruno J. View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by Drexel28 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Hint :

    Spoiler:
    Show that, given any subset $\displaystyle A \subset N$, either $\displaystyle A$ or its complement $\displaystyle N-A$ is in $\displaystyle F$.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    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.
    Last edited by Bruno J.; Nov 9th 2009 at 09:48 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. a problem about set theory
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Jul 10th 2010, 09:29 AM
  2. Set Theory problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Mar 1st 2010, 11:50 AM
  3. Set theory problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Feb 10th 2009, 01:43 AM
  4. Set Theory problem
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Feb 26th 2008, 04:54 PM
  5. Set Theory Problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Feb 14th 2007, 11:37 AM

Search Tags


/mathhelpforum @mathhelpforum