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

In summary: So then if I can prove that T is finite, then I think I would have proved that F exists. In summary, the conversation discusses the existence of a finite subset F in a family T of finite subsets of natural numbers N, such that the intersection of any two subsets in T is non-empty. The first part of the conversation asks if such a subset F must exist, while the second part considers the same question but with the added condition that all subsets in T are the same size. The conversation also includes attempts at a proof for both parts, with the conclusion that F does exist for part a, and a possible proof for part b.
  • #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
 
Physics news on Phys.org
  • #2
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 [tex]\alpha[/tex][tex]\in[/tex] A [tex]\bigcap[/tex] B. Then define F={[tex]\alpha[/tex]}. 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={a1...an}
B={b1...bn}
and ai=bj, for some elements of A and B respectively.
Define F={a1,b2,...bn}. Then a ai=bj [tex]\in[/tex] F, and F[tex]\bigcap[/tex]A[tex]\bigcap[/tex]B[tex]\neq[/tex]{}


I hope my notation isn't unreadable- I'm new to the forum so I am still working out the character options, etc.
 
  • #3
sephy said:
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 [tex]\alpha[/tex][tex]\in[/tex] A [tex]\bigcap[/tex] B. Then define F={[tex]\alpha[/tex]}. 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={a1...an}
B={b1...bn}
and ai=bj, for some elements of A and B respectively.
Define F={a1,b2,...bn}. Then a ai=bj [tex]\in[/tex] F, and F[tex]\bigcap[/tex]A[tex]\bigcap[/tex]B[tex]\neq[/tex]{}


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 [tex]A_n\bigcap B_n \eq [/tex] {an} 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.
 

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

1. How do you define "proving the existence" in this context?

In this context, proving the existence means providing evidence or reasoning that supports the assertion that an element or set F exists within a given family of finite subsets of natural numbers.

2. What is the significance of proving the existence of F from a family of finite subsets of natural numbers?

Proving the existence of F from a family of finite subsets of natural numbers has various applications in mathematics and computer science, such as in number theory, combinatorics, and cryptography. It can also help in understanding the properties and patterns of natural numbers.

3. Can you provide an example of "F" in this context?

Yes, an example of F could be a prime number, such as 5, that exists within a family of finite subsets of natural numbers, such as {1,2,3,4,5}.

4. How do you approach proving the existence of F from a family of finite subsets of natural numbers?

There are various approaches to proving the existence of F from a family of finite subsets of natural numbers, such as using mathematical induction, contradiction, or direct proof. The specific approach used will depend on the specific problem and the available information.

5. Is it always possible to prove the existence of F from a family of finite subsets of natural numbers?

No, it may not always be possible to prove the existence of F from a family of finite subsets of natural numbers. This could be due to the complexity of the problem or the lack of information. In some cases, it may only be possible to prove the existence of F under certain assumptions or conditions.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
664
  • Calculus and Beyond Homework Help
Replies
4
Views
614
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
22
Views
621
  • Calculus and Beyond Homework Help
Replies
2
Views
3K
Replies
10
Views
2K
Replies
11
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
942
Back
Top