1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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