17
$\begingroup$

Are there uncountably many $A_\alpha $ of subsets of $\mathbb{N}$ with the following two properties:

  1. Each $A_\alpha$ has positive upper natural density

  2. $A_\alpha \cap A_\beta$ is a finite set for $\alpha \neq \beta$

If the answer is no then the next question:

Are there uncountably many $A_\alpha $ of subsets of $\mathbb{N}$ with the following two properties:

  1. Each $A_\alpha$ has positive upper natural density

  2. $A_\alpha \cap A_\beta$ has zero natural density for $\alpha \neq \beta$

Note: As indicated at this MathSE post, there are uncountably many infinite subsets of $\mathbb{N}$ with pairwise finite intersection. However,
I could not modify the method indicated in the discussion of that post to get an answer to my question.

Improve this question
$\endgroup$
4

1 Answer 1

Reset to default
25
+100
$\begingroup$

Amazingly, the answer to the main question is yes. For each $n$ let $I_n = [2^{2^n}, 2^{2^{n+1}})$. Then let $\mathcal{C}$ be an uncountable family of infinite subsets of $\mathbb{N}$ any two of which have finite intersection. For each $B\in \mathcal{C}$ let $B' = \bigcup \{I_n: n \in B\}$. Then $\{B': B \in \mathcal{C}\}$ is the desired family. The point is that if $B$ is any infinite subset of $\mathbb{N}$ then $B'$ has upper density 1.

Edit: or just take $I_n = [n!, (n+1)!)$, so that $\frac{|I_n|}{(n+1)!} = \frac{n}{n+1}$.

Improve this answer
$\endgroup$
13
  • 14
    $\begingroup$ Sure, an infinite binary tree has countably many vertices. Any two infinite paths down the tree have finite intersection, and there are $2^{\aleph_0}$ of them. $\endgroup$
    – Nik Weaver
    Commented Jul 17, 2022 at 13:09
  • 3
    $\begingroup$ You are both welcome. Ali --- it may be a tricky problem because one would think the answer has to be "no". Finding an example wasn't so hard once I realized that's what I was supposed to be doing ... $\endgroup$
    – Nik Weaver
    Commented Jul 17, 2022 at 13:22
  • 1
    $\begingroup$ @NikWeaver Yes. But this particular phrasing sticks in my mind because right after the 1989 Putnam, a fellow student told me that this is how he had solved Problem B-4, which had stumped me during the exam. $\endgroup$
    – Timothy Chow
    Commented Jul 18, 2022 at 12:36
  • 1
    $\begingroup$ @TimothyChow dear Nik and Timothy what about the following stronger version : we require each $A_\alpha$ has positive full density(rather than merely upper density) $\endgroup$
    – Ali Taghavi
    Commented Jul 21, 2022 at 5:06
  • 9
    $\begingroup$ No way. If each $A_\alpha$ has positive density then for some $n$ uncountable many of then have density at least $1/n$. Any $n+1$ of those would would have to have positive density for some $A_\alpha\cap A_\beta$, so the intersection can't be finite. $\endgroup$
    – Nik Weaver
    Commented Jul 21, 2022 at 7:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .