Lots of sets, finite intersections

Do there exist uncountably many subsets of the natural numbers such that every pair of the subsets has finite intersection?

No Undecidable in ZFC Yes

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.

3 solutions

Ivan Koswara
Sep 18, 2015

This is a sketch. I assume N = { 0 , 1 , 2 , 3 , } \mathbb{N} = \{0,1,2,3,\ldots\} , although there's no difference.

First, we know that N = N 2 |\mathbb{N}| = |\mathbb{N}^2| , so we might as well pick subsets of N 2 \mathbb{N}^2 and use a bijection from N 2 \mathbb{N}^2 to N \mathbb{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 ) (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 \mathbb{N}^2 .

Now, for each positive real r r , consider the line y = r x y = rx . 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_1 x , y = r 2 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 R such that if we only consider the portions of the lines lying outside x 2 + y 2 = R 2 x^2+y^2 = R^2 , they are separated by at least 4 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.

Moderator note:

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.

Ivan Koswara - 5 years, 8 months ago

I wasn't thinking of having infinite subsets, oops!

Laurel Martin - 3 years, 7 months ago

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.

Félix Pérez Haoñie - 2 years, 8 months ago

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

Ivan Koswara - 2 years, 8 months ago

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.

Kermit Rose - 2 years, 5 months ago

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.

Oli Solomons - 2 years, 4 months ago
Jon Haussmann
Sep 30, 2015

We claim that such subsets exist. Let a = ( a 1 , a 2 , a 3 , ) a = (a_1, a_2, a_3, \dots) be an infinite binary sequence, so a i { 0 , 1 } a_i \in \{0,1\} for all i i . (By Cantor's diagonal argument, the number of infinite binary sequences is uncountable.)

To each such sequence a a , we associate a set of positive integers S a S_a as follows: Let S a S_a be the set of all positive integers of the form p 1 a 1 p 2 a 2 p i a i , p_1^{a_1} p_2^{a_2} \dotsm p_i^{a_i}, where p i p_i is the i th i^{\text{th}} prime.

Let b b be another infinite binary sequence. Then there exists a j j such that a j b j a_j \neq b_j , so the only elements that S a S_a and S b S_b can have in common are the elements of the form p 1 a 1 p 2 a 2 p i a i , p_1^{a_1} p_2^{a_2} \dotsm p_i^{a_i}, where i < j i < j . In particular, S a S_a and S b 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.

Adam Morgan - 4 years, 6 months ago

Log in to reply

There is no problem if a a contains an infinite number of 1's. I am defining S a S_a as the set of all elements of the form p 1 a 1 p 2 a 2 p i a i , p_1^{a_1} p_2^{a_2} \dotsm p_i^{a_i}, where i 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 , ) a = (1, 1, 1, \dots) , then S a = { 2 , 2 3 , 2 3 5 , } . S_a = \{2, \ 2 \cdot 3, \ 2 \cdot 3 \cdot 5, \ \dots\}.

Jon Haussmann - 4 years, 6 months ago
Santi Spadaro
Aug 7, 2018

Here's a construction obtained with the help of some basic analysis. Let Q \mathbb{Q} be the set of all rational numbers. We know that Q \mathbb{Q} is countable, so let f : Q N f: \mathbb{Q} \to \mathbb{N} be a bijection. For every irrational number a, let S a 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 S_a \cap S_b must be finite. Therefore { f ( S a ) : a R Q } \{f(S_a): a \in \mathbb{R} \setminus \mathbb{Q}\} is an uncountable family of sets of natural numbers where every distinct pair of sets has finite intersection.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...