I stumbled upon this page in Wikipedia about Hall's marriage theorem:
The standard example of an application of the marriage theorem is to imagine two groups; one of n men, and one of n women. For each woman, there is a subset of the men, any one of which she would happily marry; and any man would be happy to marry a woman who wants to marry him. Consider whether it is possible to pair up (in marriage) the men and women so that every person is happy.
If we let $A_i$ be the set of men that the i-th woman would be happy to marry, then the marriage theorem states that each woman can happily marry a man if and only if the collection of sets ${A_i}$ meets the marriage condition.
The collection S satisfies the marriage condition (MC) if and only if for each subcollection $W \subseteq S$, we have
$$
|W| \le \Bigl|\bigcup_{A \in W} A\Bigr|
$$
I am having trouble understanding this part:
In other words, the number of sets in each subcollection W is less
than or equal to the number of distinct elements in the union over the
subcollection W.
Best Answer
Well... I may be a little late to the party here (not that there really is one), but I have just started reading about this theorem for a project. The inequality $$|W|\leq \left|\bigcup_{A\in W}A\right|$$ means that the number of $A$'s in $W$ must be at most the number of elements in all the $A$'s. The marriage condition can be stated as follows:
Consider the example with $n=3$ and $A_1:=\{1,2\},~A_2:=\{2\},~A_3:=\{1\}$. Then $$\bigcup_{k=1}^nA_k=A_1\cup A_2\cup A_3=\{1,2\}$$ So we have $$\left|\bigcup_{k=1}^nA_k\right|=2\not\geq 3=n$$ hence, the marriage condition fails in this case.