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

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}$$.

• Just to be sure. By "$x\cap y\in S$" you mean $x\cap y=\{z\}$ for some $z\in S$, right? – Maurizio Moreschi Oct 16 '18 at 16:49
• What do you mean by $x \cap y$ prime? Do you mean that it's a subset of the set of primes? – user44191 Oct 16 '18 at 16:50
• Sorry. That was a typo. I should have taken its cardinality. I also renamed the title to make it more appropriate. – Arsh Jhaj Oct 16 '18 at 16:51
• @YaakovBaruch That works for $S=\mathbb{N}$, but for arbitrary infinite $S$ I think it's actually much harder to modify that than it is to work with binary trees. – Noah Schweber Oct 16 '18 at 17:28
• @user44191 In a general commutative ring, a subset (usually an ideal) $P$ can be called prime iff $ab\in P\implies a\in P\vee b\in P$; the prime integers generate exactly the prime ideals in the integers in this sense, but it also makes sense in any commutative (semi)ring. I thought this was what the OP meant and found the question fascinating, asking for intersections to be exactly the ideals generated by primes in $\mathbb{N}$. – Alec Rhea Oct 16 '18 at 19:12

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

• Note that this is choice-free. – YCor Oct 16 '18 at 18:18
• My construction is also choice free. (We can always just choose the lexicographically least extension.) – Noah Schweber Oct 16 '18 at 18:52
• @NoahSchweber I also meant I don't made any choice (not only in the sense of not using the axiom of choice). – YCor Oct 16 '18 at 19:30
• Thanks for the upvotes and for acceptation of the answer, but I should emphasize that I did my answer after Noam's was written. – YCor Oct 20 '18 at 13:17

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.

• Can you arrange that the set of cardinal of intersections is $S$ (and not only a subset of $S$)? – YCor Oct 16 '18 at 17:15
• @YCor I think so: given any $n$ and a tree like the above, we can build a single new set which intersects one of the paths in a set of exactly size $n$ and whose intersection with any other set stays in $S$ (by going "node-by-node" up the tree, so we only have countably many requirements to meet). Now we do that for each $n\in S$, noting that it doesn't get any harder if instead of a tree like the above we have a tree like the above and finitely many additional sets. – Noah Schweber Oct 16 '18 at 17:19

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