Proving the Existence of F from a Family of Finite Subsets of Natural Numbers

[CornMuffin]

Homework Statement

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.

Homework Equations

The Attempt at a Solution

(help me complete/fix this proof, or come up with a different proof)
for part a)
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.

for 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.

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

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 is non empty. This give Tn+1

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

 

[sephy]

For Part A -

I'm pretty sure F does exist: they give you that the intersection of A and B is non-empty, so it must contain at least one element, say $$\alpha$$$$\in$$ A $$\bigcap$$ B. Then define F={$$\alpha$$}. F is definitely in T, and the intersections of A, B and F are non-empty.

For Part B -

I don't think you need to know anything about T being finite (I don't actually think T can be finite, since it's subsets of N and N is infinite).
They are giving you that A and B are finite subsets of N, and that they are the same size (let's say everything in T is size n), and that their intersection is non-empty.
Consider:
A={a₁...a_n}
B={b₁...b_n}
and a_i=b_j, for some elements of A and B respectively.
Define F={a₁,b₂,...b_n}. Then a a_i=b_j $$\in$$ F, and F$$\bigcap$$A$$\bigcap$$B$$\neq$${}


I hope my notation isn't unreadable- I'm new to the forum so I am still working out the character options, etc.

 

[CornMuffin]

For Part A -

I'm pretty sure F does exist: they give you that the intersection of A and B is non-empty, so it must contain at least one element, say $$\alpha$$$$\in$$ A $$\bigcap$$ B. Then define F={$$\alpha$$}. F is definitely in T, and the intersections of A, B and F are non-empty.

For Part B -

I don't think you need to know anything about T being finite (I don't actually think T can be finite, since it's subsets of N and N is infinite).
They are giving you that A and B are finite subsets of N, and that they are the same size (let's say everything in T is size n), and that their intersection is non-empty.
Consider:
A={a₁...a_n}
B={b₁...b_n}
and a_i=b_j, for some elements of A and B respectively.
Define F={a₁,b₂,...b_n}. Then a a_i=b_j $$\in$$ F, and F$$\bigcap$$A$$\bigcap$$B$$\neq$${}


I hope my notation isn't unreadable- I'm new to the forum so I am still working out the character options, etc.

For part a, F has to be finite, but the family can be an infinite set of subsets
let $$A_n\bigcap B_n \eq$$ {a_n} which is similar to our example. Adding up the number of terms as n goes to infinity, we get an infinite amount of terms, which would make F infinite.

For part b, i don't think that shows that F is finite. I might have been wrong, but I figured that since T contains subsets of the same size and the intersection of A and B is nonempty for all A and B in T, that would mean that T is finite which is what I would like to prove because if T was finite, then F would be the intersection and would be finite.