Set Theory Question

  • #1
291
33
Lately I have been attempting (and failing miserably at) whatever sample Putnam questions I can find on the internet. Here is my latest endeavor. I found this question on the Kansas State University website, so I think I am allowed to post it. I must warn you that I know almost nothing about set theory.

Can a countably infinite set have an uncountable collection of non-empty subsets such that the intersection of any two of them is finite?

I know that the set of all integers is "countably" infinite.
Let I be the set containing all integers. The set I contains an infinite number of subsets each containing any number of the infinite number of elements in the set I, so the number of subsets of I is uncountable. However, any two subsets of I can be shown to have a finite intersection.
For example G={1,2,3,4} , F={3,4,5}
G and F have 2 elements in common; the elements 3 and 4 belong to both sets
The answer is yes.


I don't know if this would be a sufficient answer. It's awfully wordy and does not contain much mathematical rigor.
 

Answers and Replies

  • #2
35,441
11,876
What about A={2,4,6,8,...} and B={3,6,9,12,...} with their intersection {6,12,18,...}?
You need sets with infinite members, otherwise you do not get an uncountable number of subsets.

I like that question. It has a nice answer.
 
Last edited:
  • Like
Likes AlephNumbers
  • #3
Dick
Science Advisor
Homework Helper
26,260
619
Lately I have been attempting (and failing miserably at) whatever sample Putnam questions I can find on the internet. Here is my latest endeavor. I found this question on the Kansas State University website, so I think I am allowed to post it. I must warn you that I know almost nothing about set theory.

Can a countably infinite set have an uncountable collection of non-empty subsets such that the intersection of any two of them is finite?

I know that the set of all integers is "countably" infinite.
Let I be the set containing all integers. The set I contains an infinite number of subsets each containing any number of the infinite number of elements in the set I, so the number of subsets of I is uncountable. However, any two subsets of I can be shown to have a finite intersection.
For example G={1,2,3,4} , F={3,4,5}
G and F have 2 elements in common; the elements 3 and 4 belong to both sets
The answer is yes.


I don't know if this would be a sufficient answer. It's awfully wordy and does not contain much mathematical rigor.

It doesn't contain any rigor. And tackling Putnam questions while saying you know almost nothing about set theory is a bold move. I agree with mfb that it is a nice question and does have an easy answer. Here's a hint. You can split ##I## into three disjoint sets where two contain a countably infinite number of members and one has a finite number. Show that and use it.
 
Last edited:
  • #4
291
33
Hmm. I think I'll put this one on the backburner. Thank you for the input.
 

Related Threads on Set Theory Question

  • Last Post
Replies
1
Views
517
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
1
Views
806
  • Last Post
Replies
3
Views
530
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
2
Views
787
  • Last Post
Replies
1
Views
810
  • Last Post
Replies
1
Views
957
Top