Set Theory Question

  • #1
AlephNumbers
293
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
36,100
13,024
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,263
620
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
AlephNumbers
293
33
Hmm. I think I'll put this one on the backburner. Thank you for the input.
 

Suggested for: Set Theory Question

  • Last Post
Replies
10
Views
285
  • Last Post
Replies
3
Views
649
  • Last Post
Replies
2
Views
929
  • Last Post
Replies
18
Views
432
  • Last Post
Replies
1
Views
877
Replies
12
Views
652
  • Last Post
Replies
1
Views
702
Replies
7
Views
946
Replies
12
Views
232
Top