Results 1 to 5 of 5

Math Help - 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 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.
    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
    21
    Quote Originally Posted by Bruno J. View Post
    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?
    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 A \subset N, either A or its complement N-A is in 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 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.
    Last edited by Bruno J.; November 9th 2009 at 10: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: July 10th 2010, 10:29 AM
  2. Set Theory problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 1st 2010, 12:50 PM
  3. Set theory problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 10th 2009, 02:43 AM
  4. Set Theory problem
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: February 26th 2008, 05:54 PM
  5. Set Theory Problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 14th 2007, 12:37 PM

Search Tags


/mathhelpforum @mathhelpforum