- #1

CornMuffin

- 55

- 5

## 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