Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Set Theory: Need help understanding the question!

  1. Sep 27, 2010 #1
    1. The problem statement, all variables and given/known data
    Let T be a family of finite subsets of the natural numbers N = {1, 2, 3,...} such that if A and B are any members of T, then the intersection of A and B is nonempty.

    (a) Must N contain a finite subset F such that the intersection of A, B and F is nonempty for any sets A and B belonging to T?
    (b) What if we assume in addition that all the sets in T are the same size?

    I need to show that the answer is yes or provide a counter-example.



    2. Relevant equations



    3. The attempt at a solution
    I think I am having trouble with the wording of the problem or something... because if T={{1,2},{2,3},{1,3}} then there is no F that satisfies this. If this statement meant that there exists an F for each A, and B, then F can just be the intersection of A and B... so I am probably missing something here, there's no way this is supposed to be this easy. Can someone help me understand the problem a little better?
     
  2. jcsd
  3. Sep 28, 2010 #2

    HallsofIvy

    User Avatar
    Science Advisor

    Okay, that's a good example. But why wouldn't F= {1, 2, 3} work? The intersection of that with any non-empty subset of T is non-empty. In fact, as long as T contains only a finite number of sets, F equal to the union of all sets in T works. So you need to look at cases where T contains an infinite number of sets.
     
  4. Sep 28, 2010 #3
    ok, i understand, i will let you know if I need any more help
     
  5. Oct 2, 2010 #4
    Well, I got the first part of the question, I created a counter example for part a, but it's not the prettiest counter example :( .
    let T contain the following infinitely many finite subsets of the natural numbers
    {a1,a2}, {a2,a3,b1,b2}, {a2,a3,b2,b3,c1,c2} , ...
    {a1,a3}, {a1,b1,b3}, {a1, b1, c1,c3}, ...
    yeah, messy but an F does not exist.


    However I am having trouble proving the second part.
    b) What if the family of subsets contained subsets of the same size?

    If I can prove that the family of subsets must be finite which is what I suspect, then I proved that F must exist.

    I tried proving this by contradiction but no success.
     
  6. Oct 4, 2010 #5



    This was my attempt at a proof for b:
    Let T contain subsets of length n
    Let T = {Ai : Ai={ai1,ai1,...,ai1}

    if n=1, then T can only contain one subset, so T is finite


    Let Tn be any family of subsets of length n that satisfies the condition. and let Fn be an F that works with Tn
    then, add one more element to each subset in Tn to get subsets of length n+1 and add any subset of length n+1 that satisfies the property that the intersection of any two subsets are non empty.

    then either the intersection of two subsets in Tn+1 is a subset of Fn or it is a subset of the collection of the new elements that were added to each family which is a finite subset.

    then T has finitely many unique subsets

    therefore F exists since F can be the union of all subsets in the family
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook