Hitting set

A set $H$ is a hitting set for a set family $\mathcal{F}$ if $H\cap A\ne \varnothing$ for every $A\in \mathcal{F}$. Every set is a hitting set for an empty set family; none is a hitting set for a family containing the empty set. Bounded hitting sets permit finite certificates for some infinite set families, as in the bounded-size transversal kernel.

If the members of a possibly infinite set family $\mathcal{F}$ have size at most $r$, there is a finite subset ${\mathcal{F}}_0\subseteq \mathcal{F}$ of size at most $M(r,s)$ with exactly the same hitting sets of size at most $s$. Use mathematical induction on $s$. For nonempty $\mathcal{F}$, choose $A_0\in \mathcal{F}$. When $s=0$ this one member suffices. Otherwise, for each $x\in A_0$, retain an inductive kernel for ${\mathcal{F}}_x=\{A\in \mathcal{F}:x\notin A\}$ at parameter $s-1$, and take their set union together with $A_0$. Its size is at most $1+rM(r,s-1)=M(r,s)$. A hitting set $H$ for this kernel meets $A_0$ at some $x$; $H\setminus \{x\}$ meets the kernel for ${\mathcal{F}}_x$, hence all of ${\mathcal{F}}_x$, while $x$ meets the other members of $\mathcal{F}$. If $A_0$ is empty no hitting set exists, and if $\mathcal{F}$ is empty its kernel is empty. Only finite branching is used, so no finiteness assumption on $\mathcal{F}$ is needed.