Exercise 5, § 4

Let E be an ordered set for which there exists an integer $k$ such that $k$ is the greatest number of elements in a free subset X of E ($§ 1$, Exercise 5). Show that E can be partitioned into $k$ totally ordered subsets (with respect to the induced ordering). The proof is in two steps :

(a) If E is finite and has $n$ elements, use induction on $n$; let $a$ be a minimal element of E and let $\mathrm{E}' = \mathrm{E} - \{a\}$. If there exists a partition of $\mathrm{E}'$ into $k$ totally ordered sets $\mathrm{C}_i$ $(1 \leqslant i \leqslant k)$, let $\mathrm{U}_i$ be the set of all $x \in \mathrm{C}_i$ which are $\geqslant a$. Show that there is at least one index $i$ for which a free subset of $\mathrm{E}' - \mathrm{U}_i$ has at most $k - 1$ elements. The proof of this is by reductio ad absurdum. For each $i$, let $\mathrm{S}_i$ be a free subset of $\mathrm{E}' - \mathrm{U}_i$ which has $k$ elements, let S be the union of the sets $\mathrm{S}_i$, and let $s_j$ be the least element of $\mathrm{S} \cap \mathrm{C}_j$ for each index $j \leqslant k$; show that the $k + 1$ elements $a, s_1, \ldots, s_k$ form a free subset of E.

(b) If E is arbitrary, the proof is by induction on $k$, as follows. A subset C of E is said to be strongly related in E if for each finite subset F of E there exists a partition of F into at most $k$ totally ordered sets such that $\mathrm{C} \cap \mathrm{F}$ is contained in one of them. Show that there exists a maximal strongly related subset $\mathrm{C}_0$, and that every free subset of $\mathrm{E} - \mathrm{C}_0$ has at most $k - 1$ elements. (Argue by contradiction, and suppose that there is a free subset $\{a_1, \ldots, a_k\}$ of $k$ elements in $\mathrm{E} - \mathrm{C}_0$. Consider each set $\mathrm{C}_0 \cup \{a_i\}$ $(1 \leqslant i \leqslant k)$, and express the fact that it is not strongly related, thus introducing a finite subset $\mathrm{F}_i$ of E for each index $i$. Then consider the union F of the sets $\mathrm{F}_i$ and use the fact that $\mathrm{C}_0$ is strongly related to obtain a contradiction.)