Exercise 13, § 5

Let E be a set with $2m$ elements, let $q$ be an integer $< m$, and let $\mathfrak{F}$ be the set of all subsets $\mathfrak{S}$ of $\mathfrak{P}(E)$ with the following property : if X and Y are two distinct elements of $\mathfrak{S}$ such that $X \subset Y$, then $Y - X$ has at most $2q$ elements.

(a) Let $\mathfrak{M} = (A_i)_{1 \leqslant i \leqslant p}$ be an element of $\mathfrak{F}$ such that $p = \mathrm{Card}\,(\mathfrak{M})$ is as large as possible. Show that $m - q \leqslant \mathrm{Card}\,(A_i) \leqslant m + q$ for $1 \leqslant i \leqslant p$. (Argue by contradiction. Suppose, for example, that there exist indices $i$ such that $\mathrm{Card}\,(A_i) < m - q$, and consider those of the $A_i$ for which $\mathrm{Card}\,(A_i)$ has the least possible value $m - q - s$ (where $s \geqslant 1$). Let $A_1$, $\ldots$, $A_r$, say, be these sets. Let $\mathfrak{G}$ be the set of subsets of E each of which is the union of some $A_i (1 \leqslant i \leqslant r)$ and a subset of $2q + 1$ elements contained in $E - A_i$. Show that $\mathfrak{G}$ contains at least $r + 1$ elements (cf. Exercise 12), and that if $B_1$, $\ldots$, $B_{r+1}$ are $r + 1$ distinct elements of $\mathfrak{G}$, the set whose elements are $B_j (1 \leqslant j \leqslant r + 1)$ and $A_i (r + 1 \leqslant i \leqslant p)$ belongs to $\mathfrak{F}$, contrary to hypothesis.)

(b) Deduce from (a) that the number of elements $p$ of each $\mathfrak{S} \in \mathfrak{F}$ satisfies the inequality

(c) Establish results analogous to those of (a) and (b) when $2m$ or $2q$ is replaced by an uneven number.