Hall’s marriage theorem, proof of
The theorem is trivially true for .
Assuming the theorem true for all , we prove it for .
First suppose that we have the stronger condition
for all . Pick any as the representative of ; we must choose an SDR from
then, by our assumption,
By the already-proven case of the theorem for we see that we can indeed pick an SDR for .
Otherwise, for some we have the “exact” size
Inside itself, for any we have
so by an already-proven case of the theorem we can pick an SDR for .
It remains to pick an SDR for which avoids all elements of (these elements are in the SDR for ). To use the already-proven case of the theorem (again) and do this, we must show that for any , even after discarding elements of there remain enough elements in : we must prove
using the disjointness of and . So by an already-proven case of the theorem, does indeed have an SDR which avoids all elements of .
This the proof.
|Title||Hall’s marriage theorem, proof of|
|Date of creation||2013-03-22 12:45:12|
|Last modified on||2013-03-22 12:45:12|
|Last modified by||mps (409)|