Exercise 6, § 4

(a) Let A be a set and let $(\mathrm{X}_i)_{1 \leqslant i \leqslant m}$, $(\mathrm{Y}_j)_{m+1 \leqslant j \leqslant m+n}$ be two finite families of subsets of A. Let $h$ be the least integer such that, for each integer $r \leqslant m - h$ and each subset $\{i_1, \ldots, i_{r+h}\}$ of $r + h$ elements of $[1, m]$, there exists a subset $\{j_1, \ldots, j_r\}$ of $r$ elements of $[m + 1, m + n]$ for which the union of the sets $\mathrm{X}_{i_\alpha}$ $(1 \leqslant \alpha \leqslant r + h)$ meets each of the sets $\mathrm{Y}_{j_\beta}$ $(1 \leqslant \beta \leqslant r)$ (which implies that $m \leqslant n + h$). Show that there exists a finite subset B of A with at most $n + h$ elements such that every $\mathrm{X}_i$ $(1 \leqslant i \leqslant m)$ and every $\mathrm{Y}_j$ $(m + 1 \leqslant j \leqslant m + n)$ meets B. (Consider the order relation on the interval $[1, m + n]$ whose graph is the union of the diagonal and the set of pairs $(i, j)$ such that $1 \leqslant i \leqslant m$ and $m + 1 \leqslant j \leqslant m + n$ and $\mathrm{X}_i \cap \mathrm{Y}_j \neq \emptyset$, and apply Exercise 5 to this ordered set.)

(b) Let E and F be two finite sets and let $x \rightarrow \mathrm{A}(x)$ be a mapping of E into $\mathfrak{P}(\mathrm{F})$. Then there exists an injection $f$ of E into F such that $f(x) \in \mathrm{A}(x)$ for each $x \in \mathrm{E}$ if and only if for each subset H of E we have Card $\left( \bigcup_{x \in \mathrm{H}} \mathrm{A}(x) \right) \geqslant$ Card (H) (the method of proof is analogous to that of (a), with $h = 0$).

(c) With the hypotheses of (b), let G be a subset of F. Then there exists an injection $f$ of E into F such that $f(x) \in \mathrm{A}(x)$ for each $x \in \mathrm{E}$ and such that $f(E)\supset G$ if and only if $f$ satisfies the condition of (b) and for each subset $L$ of $G$ the cardinal of the set of all $x\in E$ such that $A(x)\cap L\neq\varnothing$ is $\geq\operatorname{Card}(L)$. (Let $(a_i)_{1\leq i\leq p}$ be the sequence of distinct elements of $G$, arranged in some order; let $(b_j)_{p+1\leq j\leq p+m}$ be the sequence of distinct elements of $F$, arranged in some order; and let

be the sequence of distinct elements of $E$, arranged in some order. Consider the order relation on the set $[1,p+m+n]$ whose graph is the union of the diagonal and the set of pairs $(i,j)$ such that either

or $1\leq i\leq p$ and $p+m+1\leq j\leq p+m+n$ and $a_i\in A(c_j)$,

or $p+1\leq i\leq p+m$ and $p+m+1\leq j\leq p+m+n$ and $b_i\in A(c_j)$;

then apply Exercise 5.)