Do there exist uncountably many subsets of the natural numbers such that every pair of the subsets has finite intersection?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Nice construction!
Note that if we restricted ourselves to sets with finitely many elements, then there are only countably many of them (Can you prove this?). Hence, we must allow for sets with infinitely many elements.
Challenge Master: There are only countably many sets of any fixed finite number of elements, and there are countably many different numbers of elements. The countable union of countable sets is countable. This union is exactly the family of sets having finite number of elements.
I wasn't thinking of having infinite subsets, oops!
Log in to reply
Are the subsets exclusive or they can share some elements with other subsets? This isn't clear to me from the problem statement. If the subsets are exclusives, I don't see how a countable set can make uncountable subsets.
Log in to reply
The subsets are not necessarily disjoint. Yes, if they are disjoint then you can't have uncountably many subsets. But the problem doesn't say anything about this. In fact, the problem specifically states "every pair of the subsets has finite intersection". Note how the problem says "finite" and not "empty".
I made the mistake of thinking that "finite intersection" implied that the number of pairs would also be countably infinite. That is why I did not get the correct answer to this question.
In answer to the moderator's challenge:
Take a finite subset of the natural numbers. Transform this into a list of 1s and 0s, where the ith position in the list is a 1 if i is in the subset. (e.g. the subset {1,3,4} becomes (1,0,1,1)) interpret this as a binary number
Therefore there is a way to transform any finite natural number into a finite subset of natural numbers, and also the reverse, so the finite subsets of the natural numbers is countably infinite.
We claim that such subsets exist. Let a = ( a 1 , a 2 , a 3 , … ) be an infinite binary sequence, so a i ∈ { 0 , 1 } for all i . (By Cantor's diagonal argument, the number of infinite binary sequences is uncountable.)
To each such sequence a , we associate a set of positive integers S a as follows: Let S a be the set of all positive integers of the form p 1 a 1 p 2 a 2 ⋯ p i a i , where p i is the i th prime.
Let b be another infinite binary sequence. Then there exists a j such that a j = b j , so the only elements that S a and S b can have in common are the elements of the form p 1 a 1 p 2 a 2 ⋯ p i a i , where i < j . In particular, S a and S b have finite intersection.
This is a neat idea, but the set of all binary sequences contains sequences that have infinitely many ones making the product into a product of infinitely many primes. If you restrict to the set of binary sequences with finitely many ones, you are back to a countable set.
Log in to reply
There is no problem if a contains an infinite number of 1's. I am defining S a as the set of all elements of the form p 1 a 1 p 2 a 2 ⋯ p i a i , where i is a positive integer. Each term is a finite product, and so a well-defined positive integer.
For example, if a = ( 1 , 1 , 1 , … ) , then S a = { 2 , 2 ⋅ 3 , 2 ⋅ 3 ⋅ 5 , … } .
Here's a construction obtained with the help of some basic analysis. Let Q be the set of all rational numbers. We know that Q is countable, so let f : Q → N be a bijection. For every irrational number a, let S a be a sequence of rational numbers converging to a. Since every convergent sequence has a unique limit, for every distinct irrational numbers a and b, the intersection S a ∩ S b must be finite. Therefore { f ( S a ) : a ∈ R ∖ Q } is an uncountable family of sets of natural numbers where every distinct pair of sets has finite intersection.
Problem Loading...
Note Loading...
Set Loading...
This is a sketch. I assume N = { 0 , 1 , 2 , 3 , … } , although there's no difference.
First, we know that ∣ N ∣ = ∣ N 2 ∣ , so we might as well pick subsets of N 2 and use a bijection from N 2 to N to translate it.
Consider the first quadrant of the Euclidean plane. Partition it into unit squares. With each unit square, we can denote a pair of naturals ( x , y ) representing its lower-left corner (the corner closest to the origin). Thus we might as well pick sets of these squares and use the bijection to get subsets of N 2 .
Now, for each positive real r , consider the line y = r x . This passes through some of the squares. (Assume that a line passes through a square that shares any point with it, including corners; this doesn't really matter.) Now we have an uncountable family of sets of squares; it just remains to show that these sets have finite intersections.
Consider two lines y = r 1 x , y = r 2 x . The two lines will eventually be too far apart to share any squares in common; in other words, there exists some R such that if we only consider the portions of the lines lying outside x 2 + y 2 = R 2 , they are separated by at least 4 units everywhere, and will thus never share any square. Thus all squares they share in common lie inside the circle (or on the circle), in which there are only a finite number of them. This proves the claim.