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

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


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.


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

Tags:

Set Theory

Co.Combinatorics

Infinite Combinatorics

Related

Matrix determinant inequality proof without using information theory Explicit proof that $c_0$-module $\ell_\infty$ is not projective Product of arithmetic progressions Making the Fourier transform quantitative partial alternating sum involving binomial coefficients Lower density of numbers not summable by consecutive integers Does $\mathrm{SL}_{n}(\mathbb{Z}/p^{2})$ have the same number of conjugacy classes as $\mathrm{SL}_{n}(\mathbb{F}_{p}[t]/t^{2})$? A link between hooks and contents: Part II Is there a good name for the operation that turns $A\operatorname{-mod}$ and $B\operatorname{-mod}$ into $A\otimes B\operatorname{-mod}$? A link between hooks, contents and parts of a partition Counting configurations on a 2xn board under restrictions Minimal, uniquely ergodic but not Lebesgue-ergodic?

Recent Posts