We prove Hall's marriage theorem by induction on $\size{S}$ , the size of $S$ .

The theorem is trivially true for $|S|=0$ .

Assuming the theorem true for all $\size{S}<n$ , we prove it for $\size{S}=n$ .

First suppose that we have the stronger condition $$ \size{\cup T} \ge \size{T}+1 $$ for all $\emptyset \ne T \subset S$ . Pick any $x\in S_n$ as the representative of $S_n$ ; we must choose an SDR from $$ S' = \left\{\x{S_1},\ldots,\x{S_{n-1}}\right\}. $$ But if $$ \{\x{S_{j_1}},...,\x{S_{j_k}}\} = T'\subseteq S' $$ then, by our assumption, $$ \size{\cup T'} \ge \size{\cup_{i=1}^{k} S_{j_i}}-1 \ge k. $$ By the already-proven case of the theorem for $S'$ we see that we can indeed pick an SDR for $S'$ .

Otherwise, for some $\emptyset\ne T \subset S$ we have the ``exact'' size $$ \size{\cup T}=\size{T}. $$ Inside $T$ itself, for any $T'\subseteq T\subset S$ we have $$ \size{\cup T'}\ge\size{T'}, $$ so by an already-proven case of the theorem we can pick an SDR for $T$ .

It remains to pick an SDR for $S\setminus T$ which avoids all elements of $\cup T$ (these elements are in the SDR for $T$ ). To use the already-proven case of the theorem (again) and do this, we must show that for any $T'\subseteq S\setminus T$ , even after discarding elements of $\cup T$ there remain enough elements in $\cup T'$ : we must prove $$ \size{\cup T' \setminus \cup T} \ge \size{T'}. $$

But \begin{eqnarray} \size{\cup T' \setminus \cup T} &= \size{\bigcup(T\cup T')} - \size{\cup T} \ge\\ &\ge \size{T\cup T'} - \size{T} =\\ &= \size{T} + \size{T'} - \size{T} = \size{T'}, \end{eqnarray}using the disjointness of $T$ and $T'$ . So by an already-proven case of the theorem, $S\setminus T$ does indeed have an SDR which avoids all elements of $\cup T$ .

This completes the proof.