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

1. Sep 27, 2010

CornMuffin

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. Sep 28, 2010

HallsofIvy

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.

3. Sep 28, 2010

CornMuffin

ok, i understand, i will let you know if I need any more help

4. Oct 2, 2010

CornMuffin

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.

5. Oct 4, 2010

CornMuffin

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