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

  • $\begingroup$ Just to be sure. By "$x\cap y\in S$" you mean $x\cap y=\{z\}$ for some $z\in S$, right? $\endgroup$ – Maurizio Moreschi Oct 16 '18 at 16:49
  • $\begingroup$ What do you mean by $x \cap y$ prime? Do you mean that it's a subset of the set of primes? $\endgroup$ – user44191 Oct 16 '18 at 16:50
  • 2
    $\begingroup$ Sorry. That was a typo. I should have taken its cardinality. I also renamed the title to make it more appropriate. $\endgroup$ – Arsh Jhaj Oct 16 '18 at 16:51
  • 3
    $\begingroup$ @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. $\endgroup$ – Noah Schweber Oct 16 '18 at 17:28
  • 1
    $\begingroup$ @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}$. $\endgroup$ – 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$.

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

  • $\begingroup$ Can you arrange that the set of cardinal of intersections is $S$ (and not only a subset of $S$)? $\endgroup$ – YCor Oct 16 '18 at 17:15
  • 1
    $\begingroup$ @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. $\endgroup$ – 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$.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.