# Set Theory: Need help understanding the question

• CornMuffin
In summary: T.In summary, the problem asks if there exists a finite subset F of natural numbers N such that for any two sets A and B in a family T of finite subsets of N, the intersection of A, B, and F is non-empty. A counter-example for part a is T = {{1,2},{2,3},{1,3}}, where no such F exists. For part b, it is proven that if T contains subsets of the same size, T must be finite, and thus F exists.
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.

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

CornMuffin said:

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

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

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

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

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.

CornMuffin said:
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.

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

## 1. What is Set Theory?

Set Theory is a branch of mathematics that deals with the study of sets, which are collections of objects. It is used to understand the relationships between different sets and their elements.

## 2. What are the basic concepts in Set Theory?

The basic concepts in Set Theory include sets, elements, subsets, union, intersection, and complement. Sets are collections of objects, elements are the individual objects within a set, subsets are sets contained within a larger set, union combines two or more sets, and intersection finds the common elements between two sets. Complement is the set of elements that are not included in a given set.

## 3. How is Set Theory applied in other fields of study?

Set Theory has applications in various fields such as computer science, philosophy, linguistics, and statistics. It is used to model real-world situations and to analyze complex systems. For example, in computer science, Set Theory is used to study databases and networks, while in linguistics, it is used to understand the structure of language.

## 4. What are the different types of sets in Set Theory?

The different types of sets in Set Theory include finite and infinite sets, empty sets, singleton sets, and universal sets. Finite sets contain a limited number of elements, while infinite sets have an infinite number of elements. Empty sets have no elements, singleton sets have only one element, and universal sets contain all possible elements in a given context.

## 5. How can I improve my understanding of Set Theory?

To improve your understanding of Set Theory, it is important to practice solving problems and working with different types of sets and operations. You can also read books on Set Theory, attend lectures or workshops, and discuss the subject with other students or experts in the field. Additionally, using visual aids such as diagrams and charts can also help in understanding complex concepts in Set Theory.

• Calculus and Beyond Homework Help
Replies
1
Views
734
• Calculus and Beyond Homework Help
Replies
7
Views
1K
• Calculus and Beyond Homework Help
Replies
6
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
• Calculus and Beyond Homework Help
Replies
1
Views
1K
• Calculus and Beyond Homework Help
Replies
3
Views
1K
• Calculus and Beyond Homework Help
Replies
2
Views
434
• Calculus and Beyond Homework Help
Replies
11
Views
1K
• Calculus and Beyond Homework Help
Replies
1
Views
982
• Calculus and Beyond Homework Help
Replies
15
Views
1K