Exercise 17, § 5

Let $i, h, k$ be three integers such that $i \geqslant 1$, $h \geqslant i$, $k \geqslant i$. Show that there exists an integer $m_i(h,\ k)$ with the following properties : for each finite set E with at least $m_i(h,\ k)$ elements, and each partition $(\mathfrak{X},\ \mathfrak{Y})$ of the set $\mathfrak{F}_i(E)$ of subsets of $i$ elements of E, it is impossible that every subset of $h$ elements of E contains a subset $X \in \mathfrak{X}$ and that every subset of $k$ elements of E contains a subset $Y \in \mathfrak{Y}$; in other words, if every subset of $h$ elements of E contains some $X \in \mathfrak{X}$, there exists a subset A of $k$ elements of E such that every subset of $i$ elements of A belongs to $\mathfrak{X}$. (Proof by induction. Show that we may take

and finally $m_i(h, k) = m_{i-1}(m_i(h - 1, k), m_i(h, k - 1)) + 1$. If E is a set with $m_i(h,\ k)$ elements, if $a \in E$ and if $E' = E - \{a\}$, show that if the proposition were false, then every subset of $m_i(h - 1,\ k)$ elements of E′ would contain a subset X′ of $i - 1$ elements such that $X' \cup \{a\} \in \mathfrak{X}$, and that every subset of $m_i(h,\ k - 1)$ elements of E′ would contain a subset Y′ of $i - 1$ elements such that $Y' \cup \{a\} \in \mathfrak{Y}$.)