Cardinality of families of subsets of $\mathbb{N}$ whose intersections are finite

Question

Does there exist an uncountable $P \subset \mathcal{P}(\mathbb{N}) $ with the property that for any distinct $x,y \in P$, $|x \cap y|$ is prime?

A more general, but likely harder, question: is it possible to characterize the set $\mathcal{A}$ of all subsets $S \subset \mathbb{N}$ with the following property: there is some uncountable $P \subset \mathcal{P}(\mathbb{N})$ such that for all distinct $x,y \in P$, $|x \cap y| \in S$.

It's easy to show no $S$ finite belongs to $\mathcal{A}$. It's also not hard to show every $\text{mod} \ m$ equivalence class, belongs to $\mathcal{A}$.

One reasonable sounding idea is that this is related to the asymptotic density of $S$ in $\mathbb{N}$.

Answer 1

I guess this is a variant of Noah's construction:

Let $S$ be an infinite subset of $\mathbf{N}=\{0,1,2,\dots\}$. Define a leafless rooted tree $V_S$, starting from a root at level 0, such that given a vertex $v$ of level $n\ge 0$, $v$ has exactly 1 successor if $n\notin S$ and exactly 2 successors if $n\in S$.

Let $\mathcal{W}\subset\mathcal{P}(V_S)$ be the set geodesic rays not containing the root, based at a vertex of level 1; since $S$ is infinite, $\mathcal{W}$ has cardinal $2^{\aleph_0}$. Then for any distinct $U,V\in\mathcal{W}$, $U\cap V$ is either empty, or is the geodesic segment from the some vertex of level 1 to the branching point $v$ at which $U,V$ fork; this has cardinal $n$, the level of $v$; also in case $0\notin S$, $U\cap V$ cannot be empty. Conversely every such geodesic segment has the form $U\cap V$ for suitable $U,V$, and so is the empty set if $0\in S$. So the set of $|U\cap V|$ when $U,V$ range over distinct elements of $\mathcal{W}$, is exactly $S$.

Answer 2

I claim that any infinite set has this property.

Specifically, I'll construct recursively a map $F$ from finite binary strings to finite binary strings with the following properties:

• $\sigma\preccurlyeq\tau$ iff $F(\sigma)\preccurlyeq F(\tau)$.

• For each $\sigma$, if $f, g$ are two infinite binary strings whose maximal common initial segment is $\sigma$, then $Set(f)\cap Set(g)=\{n<\vert F(\sigma)\vert: F(\sigma)(n)=1\}$.

  • Here "$F(h)$" is shorthand for the infinite binary sequence $\bigcup_{\sigma\prec h}f(\sigma)$, and "$Set(h)$" is the set whose characteristic function is $h$.

• For each $\sigma$, $\vert F(\sigma)^{-1}(\{1\})\vert\in S$.

Letting $\mathfrak{S}_F=F(f): f\in 2^\mathbb{N}$, we get an uncountable - in fact, size continuum - family of sets whose pairwise intersections always have cardinality lying in $S$.

---

So now all we need to do is build $F$. But this is a standard finite extension argument, using the fact that $S$ is infinite to say that we always have "enough freedom" to extend the function as desired.

Specifically, the crucial lemma is the following:

• Suppose I have a finite set of finite binary strings $\{\tau_i: 1\le i\le n\}$. Then I can find sets $\{\alpha_i: 1\le i\le n\},\{\beta_i: 1\le i\le n\}$ such that:

  • For each $i$, $\alpha_i,\beta_i$ are incomparable proper extensions of $\tau_i$ and $\{n: \alpha_i(n)=\beta_i(n)=1\}$ has cardinality in $S$.

  • We get no new intersections in incomparable strings: for $i\not=j$ and $\eta,\theta\in\{\alpha,\beta\}$, we have $\{n: \alpha_i(n)=\beta_j(n)=1\}=\{n:\tau_i(n)=\tau_j(n)=1\}$.

We then apply this, over and over, to build $F$: e.g. think of $F(010)$ as being build via a $\sigma$-move off the empty string, and then a $\tau$-move off the resulting string, and then a $\sigma$-move off that string.

Note that this is really just an elaboration of the classical argument: the usual construction of a size-continuum almost disjoint family is just the set of sets of finite binary strings, which in the notation above is $\mathfrak{S}_{id}$. Taking $F=id$ works since we only have to keep getting incomparable extensions. Once we add the "$S$-requirement," though, we need to mix in some additional work, but this requirement can be satisfied by imposing very mild restraints. This type of argument can also be used to construct a perfect set of linearly (or otherwise) independent reals without choice, and - in computability theory - to show that there is a perfect set of Turing-incomparable reals.

---

And I think this can be easily tweaked to get the set of cardinalities of intersections to be exactly $S$; see my comment below.

Answer 3

The following argument uses less set-theory than the earlier ones!

For each positive real number $\alpha$ we can write the binary expansion $\alpha=\sum_{i=0}^{\infty} a_i 2^{N-i}$ with $a_0=1$ and $a_i\in\{0,1\}$ for $i\geq 1$. To avoid ambiguity (from an endless sequence of 1's) we also assume that for all $j$ there is a $k>j$ so that $a_k=0$.

We take $S(\alpha)=\{ \alpha_n : n>0 \}$ where $\alpha_n=\sum_{i=0}^n a_i 2^{N-i}$. Then $S(\alpha)\subset\mathbb{Q}$, so we have an uncountable collection of subsets of $\mathbb{Q}$ which is in bijection with $\mathbb{N}$. Moreover, $S(\alpha)\cap S(\beta)$ is finite when $\alpha\neq\beta$. (It consists of those truncated binary expansions of $\alpha$ and $\beta$ which are equal.)

Now take the subset of reals which consists of those $\alpha$ for which $a_i=1$ unless $i$ is prime. It is not too difficult to see that these $\alpha$ are also uncountable. For example you can map reals to such numbers by "filling in 1's" in the binary expansion as required so that the old $a_i$'s become the new $a_{\pi(i)}$ where $\pi(n)$ is the $n$-th prime.

Moreover, it follows that $S(\alpha)\cap S(\beta)$ is a prime for every such $\alpha$ and $\beta$.