Does an intersecting $r$-family in $\mathbb{N}$ have a finite underlying base set?

Question

Proof or counterexample: if $\mathcal F\subseteq \mathbb{N}^{(r)}$ is intersecting then $\exists A\subseteq \mathbb{N}: A$ is finite and $\{F\cap A:F\in\mathcal F\}$ is intersecting.

I know this result is false for $\mathcal F\subseteq \mathcal P( \mathbb{N})$ because you can find a bijection $f:\mathbb{N}^2\rightarrow \mathbb{N}$ and define $(F_i)_{i\in\mathbb{N}}$ by $F_i:=\{ f(i,j), f(j,i) :j\in\mathbb{N} \}$ so that $F_i\cap F_j=\{f(i,j),f(j,i)\}$ (or even make $f$ symmetric in its arguments to get a unique value in each singleton).

As I couldn't find a simpler construction, I suspect the result is true in the case of $r$-sets. I want to do something like taking an $A\in\mathcal F$ and considering sets $B,C$ such that $B\cap C$ is disjoint from $A$ (if none exist, we are done). Then include $B$ and find $D\cap E$ disjoint from $A\cup B$, and so on and it feels, based on instinct only, like after $r$ (or possibly $2^r$) iterations, we should be done.

Is the result true, and how can I prove it?

Answer 1

It is easy to prove by induction the following stronger statement.

If $\cal F$ and $\cal G$ are two families of sets of size at most $r$ and $s$, respectively, that cross-intersect, i.e., for all pair of sets $F\in \mathcal F, G\in\cal G$ we have $F\cap G\ne\emptyset$, then $\exists A\subseteq \mathbb{N}: A$ is finite and $\mathcal F_A=\{F\cap A \mid F\in\mathcal F\}$ and $\mathcal G_A=\{G\cap A \mid G\in\mathcal G\}$ are also cross-intersecting.

We prove by induction on $r+s$.
The claim is obviously true for $r=1$ or $s=1$ with $|A|=1$.
Pick an arbitrary $G_0\in \cal G$, and define for each non-empty $I\subset G_0$ the families $\mathcal F_I=\{F\setminus I\mid F\in\mathcal F, F\cap G_0=I\}$ and $\mathcal G_I=\{G\mid G\in\mathcal G, G\cap I=\emptyset\}$.
Since the size of sets in $\mathcal F_I$ is at most $r-1$, we can apply induction for the cross-intersecting $\mathcal F_I$ and $\mathcal G_I$ to obtain a set $A_I$ for them that satisfies the requirements.
Finally, take $A=G_0\cup \bigcup_{I\subset G_0} A_I$.

Note that this gives only $|A|<2^{r+s}$, or for your original problem $|A|<4^r$, but with a more careful analysis one can probably also get a polynomial bound.

Answer 2

The question has already been answered by @domotorp. The purpose of this additional answer is to provide some historical references.

A restatement of the result proved in the accepted answer is given by Andrzej Ehrenfeucht and Jan Mycielski, On families of intersecting sets, J. Combin. Theory (Ser. A) 17 (1974) 259–260 (pdf), whom I quote:

We shall prove first the following lemma which can be extracted from a proof of M. Całczyńska-Karlowicz [1] (see also [2] for a refinement of this lemma).

LEMMA. If $\mathcal A$ and $\mathcal B$ are families of sets such that for all $A\in\mathcal A$ and $B\in\mathcal B$ we have $|A|\leqslant a$, $|B|\leqslant b$ and $A\cap B\neq\varnothing$, then there exists a finite set $S$ such that $A\cap B\cap S\ne\varnothing$ for all $A\in\mathcal A$ and $B\in\mathcal B$.

Proof. [. . . .]

This simple proof is essentially due to Dana Scott and Ralph McKenzie (independently).

Reference [1] is to M. Całczyńska-Karlowicz, Theorem on families of finite sets, Bull. Acad. Polon. Sci. Ser. Math. Astr. Phys. 12 (1964), 87–89, to which I do not have access.

Reference [2] is to Andrzej Ehrenfeucht and Jan Mycielski, Interpolation of functions over a measure space and conjectures about memory, J. Approx. Theory 9 (1973) 218–236 (pdf) from which I quote:

Proving a conjecture of Kuratowski, Całczyńska-Karlowicz [2] found the following lemma.

(6) For every positive integer $k$ there exists a positive integer $\kappa$ such that if $\mathbf A$ and $\mathbf B$ are two collections of $k$-element sets, such that $A\cap B\ne\varnothing$ for every $A\in\mathbf A$ and $B\in\mathbf B$, then there exists a set $M$ with $\kappa$ elements at most such that $M\cap A\cap B\ne\varnothing$ for every $A\in\mathbf A$ and $B\in\mathbf B$.

Theorem 24 proved below is a refinement of (6).

Let $\kappa(k)$ be the smallest $\kappa$ satisfying (6) [. . .]

[. . . .]

THEOREM 24. $\ 2k+\binom{2k}k\leqslant\kappa(k+1)\leqslant(2k+1)4^k$.

Proof. The first inequality is due to Frances Yao. [. . .]