If every finite subfamily of $\mathcal{F}$ has a transversal of size $n$, does $\mathcal{F}$ have the following intersection property?

Question

Let's fix a family of sets $\mathcal{F}$. A transversal of $\mathcal{F}$ is a set $T$ that intersects every set in $\mathcal{F}$.

Suppose that there exists $n\in\mathbb{N}$ such that every finite subfamily $\mathcal{F'}\subseteq \mathcal{F}$ has a transversal of size $n$. This is for example the conclusion of the Alon Kleitman Matousek $(p,q)$-theorem. Note that in particular it follows that any such $\mathcal{F'}$ partitions into $n$ subfamilies, each with the finite intersection property.

Does it follows that $\mathcal{F}$ partitions into $n$ subfamilies, each having the finite intersection property?

This seems to be provable using model theoretic compactness. Namely if $\cup\mathcal{F}$ is a structure where all the sets in $\mathcal{F}$ are definable we consider an $n$-type describing a transversal of $\mathcal{F}$ of size $n$. Since it is finitely satisfiable there is one such transversal in an elementary extension and the result easily follows.

This approach seems like overkill, is there an easier way to prove this? Perhaps through some combinatoric argument or argument using choice?

Answer 1

The famous De Bruijn–Erdős theorem of graph theory states that a graph $G=(V,E)$ is $n$-colorable (for a given positive integer $n$) if every finite subgraph of $G$ is $n$-colorable. The generalization to hypergraphs is also well known and has similar proofs: if $H=(V,E)$ is a hypergraph whose edges are finite sets, and if every finite subhypergraph of $H$ is $n$-colorable (for a given positive integer $n$), then $H$ is $n$-colorable. (For a hypergraph, $n$-colorable means that the vertices can be colored with $n$ colors so that no edge is monochromatic, i.e., each edge contains vertices of at least two different colors.)

What you are asking about is in effect the De Bruijn–Erdős theorem for hypergraphs; in your case the hypergraph has as its vertex set the family $\mathcal F$, and its edges are the finite subcollections of $\mathcal F$ with empty intersection.

The De Bruijn–Erdős theorem (for graphs or hypergraphs) can be proved in various styles, using e.g. an ultrafilter or the Tychonoff product theorem (as in Eric Wofsey's answer) or the Rado selection principle or the compactness theorem for first order logic.

P.S. In my answer to this question I sketched two proofs of the De Bruijn–Erdős theorem for graphs: one using Tychonoff's theorem, the other using Zorn's lemma. Either proof can easily be modified to prove the theorem for hypergraphs. The proof with Zorn's lemma seems really straightforward and simple, and the argument could be applied directly to your question about partitioning a family of sets into subfamilies with the finite intersection property. Maybe that's the sort of "combinatoric argument" you're looking for. It is a self-contained proof, using no model theory or topology, only Zorn's lemma.

Theorem. Let $\mathcal F$ be a family of sets and let $n$ be a positive integer. If every finite subfamily of $\mathcal F$ can be partitioned into $n$ subfamilies with the finite intersection property, then $\mathcal F$ can be partitioned into $n$ families with the finite intersection property.

Proof sketch. We consider functions $\varphi\subseteq\mathcal F\times[n]$ where $[n]=\{1,\dots,n\}$. Call such a function $\varphi$ good if, for each $i\in[n]$, $\{X\in\operatorname{dom}\varphi:\varphi(X)=i\}$ has the finite intersection property. We are given that every finite subfamily of $\mathcal F$ is the domain of a good function; we have to show that $\mathcal F$ itself is the domain of a good function.

Call a function $\varphi\subseteq\mathcal F\times[n]$ extendible if, for every finite subfamily $\mathcal E\subseteq\mathcal F$, there is a good function $\psi\subseteq\mathcal F\times[n]$ such that $\varphi\subseteq\psi$ and $\mathcal E\subseteq\operatorname{dom}\psi$. Let $P$ be the set of all extendible functions $\varphi\subseteq\mathcal F\times[n]$. We are going to apply Zorn's lemma to the poset $(P,\subseteq)$.

Claim. $P$ is nonempty because $\emptyset\in P$.

This is where we use the assumption about partitions of finite subfamilies of $\mathcal F$.

Claim. The union of a chain in $P$ has an upper bound in $P$, namely, its union.

To see this observe that, if $\mathcal E$ is a finite subfamily of $\mathcal F$, and if a function $\varphi$ can not be extended to a good function whose domain includes $\mathcal E$, then the same goes for some finite restriction of $\varphi$. Details left to the reader.

By Zorn's lemma, there is a maximal extendible function, call it $\varphi$. We have to show that $\operatorname{dom}\varphi=\mathcal F$.

Assume for a contradiction that $X\in\mathcal F\setminus\operatorname{dom}\varphi$. There are finitely many good functions $\psi\supseteq\varphi$ with $\operatorname{dom}\psi=(\operatorname{dom}\varphi)\cup\{X\}$; call them $\psi_1,\dots,\psi_m$, where $1\le m\le n$. By the maximality of $\varphi$, the function $\psi_i$ is not extendible, so there is a finite subfamily $\mathcal E_i\subseteq\mathcal F$ such that $\psi_i$ can not be extended to a good function whose domain includes $\mathcal E_i$. But then it follows that $\varphi$ can not be extended to a good function whose domain includes the finite subfamily $\{X\}\cup\mathcal E_1\cup\cdots\cup\mathcal E_m$ of $\mathcal F$, and this contradicts the extendibility of $\varphi$.

Answer 2

Well, I don't know if you consider this easier, but here's a pretty natural argument. A partition of $\mathcal{F}$ into $n$ subfamilies can be considered as a point of the space $n^{\mathcal{F}}$. For any finite $\mathcal{F}'\subseteq\mathcal{F}$, the condition that each subfamily has the finite intersection property when restricted to $\mathcal{F}'$ defines a closed subset of $n^{\mathcal{F}}$, which is nonempty by hypothesis. So, by compactness of $n^{\mathcal{F}}$, the intersection of these closed subsets is nonempty, and a point of the intersection is exactly a partition where each subfamily has the finite intersection property.

(Or, essentially equivalently, you can see this as an instance of compactness for propositional logic. For each $X\in\mathcal{F}$ and each $k\in n$, have a propositional variable that says $X$ is in the $k$th subfamily. Consider axioms that say each $X$ is in exactly one of the subfamilies, and that no finite collection with empty intersection can all be in the same subfamily. These axioms are finitely satisfiable by hypothesis, and hence satisfiable.)