This question comes from Exercises III.4.5 and III.4.6 of Bourbaki's Set Theory. They are about using Dilworth's Theorem to prove Hall's Marriage Theorem (did it) and a mild extension of it (can't do it).
Dilworth's Theorem: Let $E$ be a finite ordered set and $k$ be the maximal number of elements of an antichain in $E$. Then there exists a partition of $E$ into $k$ totally ordered sets.
Hall's Marriage Theorem: Let $E$ and $F$ be two finite sets and let $x\rightarrow A(x)$ be a mapping of $E$ into $\mathfrak{P}(F)$ such that $\text{Card}(\bigcup_{x\in H}A(x))\geq\text{Card}(H)$ for any subset $H$ of $E$. Then there exists an injection $f$ of $E$ into $F$ such that $f(x)\in A(x)$ for each $x\in E$.
To prove it, one defines an ordering on the disjoint union of $E$ and $F$ such that $x>y$ if and only if $x\in E$ and $y\in F$ and $y\in A(x)$. It is easy to see that $F$ is an antichain and that there is no antichain with more elements than $F$. So there exists a partition of $E\sqcup F$ into $\text{Card}(F)$ totally ordered sets, which are necessarily either one-point subsets of $F$ or pairs $\{x,y\}$ such that $y\in A(x)$. Those pairs define the asserted injection.
Hall's Marriage Theorem (Extended Version): In the setting of above, suppose additionally that $G$ is a subset of $F$ and for each $L\subset G$, $\text{Card}(\{x\in E|A(x)\cap L\neq\emptyset\})\geq\text{Card}(L)$. Then we can choose $f$ as above with the additional property $G\subset f(E)$.
The proof is sketched by Bourbaki as follows: Consider the disjoint union of $G$, $F$, and $E$, which I denote here as $(\{1\}\times G)\cup(\{2\}\times F)\cup(\{3\}\times E)$, and define an ordering on it by setting as only relations
- $(1,z)<(2,y)$ if and only if $z=y$
- $(1,z)<(3,x)$ if and only if $z\in A(x)$
- $(2,y)<(3,x)$ if and only if $y\in A(x)$
Then apply Dilworth's Theorem.
The problem is that I don't quite know how. The greatest number of elements in an antichain is again $\text{Card}(F)$. So we get a partition of $G\sqcup F\sqcup E$ into $\text{Card}(F)$ totally ordered sets. Again, each of those sets contains exactly one element of $F$, at most one of $E$, and at most one of $G$. This way we can define an injection $f$ as before by defining $f(x)$ to be the element of $F$ which lies in the same set of the partition as $x$, but for $G\subset f(E)$ to hold, every set of the partition which contains an element of $G$ would have to contain an element of $E$ as well. But that's obviously not true for all partitions of $G\sqcup F\sqcup E$ into $\text{Card}(F)$ totally ordered sets.
So I think that either one has to find a more sophisticated way of defining $f$ from a given partition or one has to modify the order relation before applying Dilworth's Theorem, somehow using the condition on the subsets of $G$. Does someone see a way to finish the proof?
Best Answer
To finish the proof, you must also define an injection g of G into E, using the condition on the subsets of G and Dilworth's Theorem.
Then for each element a∈G \ f(E), you can redefine f so that a∈ f(E), using the injection g as follows :
Build a set of elements a0, a1, ... of G so that a0 = a and ai = g(f(ai-1)) for i>0.
Let j be the smallest integer so that aj does not belong to G (its existence has to be proved, though).
Redefine f so that f(g(ai)) = ai for each i < j. The new f is still an injection of E into F such that f(x) ∈ A(x) for each x ∈ E, and besides, a∈ f(E).
Repeat this for each element of G \ f(E) and the problem is solved.
Hope I did not go wrong somewhere. Excuse my poor english, I'm French !
Regards
Alexis