EDIT: New proof (sorry for bumping, but would be nice to have this answered).
I have an alternative proof of Hall's marriage theorem, and would like to know whether it is correct? If yes, how can it be improved? If not, why?
The proof goes by proving the sufficiency of the condition using contraposition.
Let $S_1,\ldots,S_n \subseteq X, |X|=n,$ be a collection of nonempty subsets, and suppose that there aren't distinct $x_1,\ldots,x_n\in X$, such that $x_i\in S_i, i=1,\ldots,n$. Then, there is an $I\subset \{1,\ldots,n\}$, such that $|I| > |\bigcup_{i\in I}S_i|$.
Proof: Suppose that there are at most $x_1,\ldots,x_m\in X, m < n$, distinct elements, such that $x_i \in S_i, i=1,\ldots,m$ without loss of generality. We clearly have $|I| \leq |\bigcup_{i\in I}S_i|$ for all $I\subseteq M$ where $M=\{1,\ldots, m\}$.
Define $A = \{x_1,\ldots,x_m\}, B= X\setminus A$ and $X_{I} = \bigcup_{i\in I} S_i$. Now pick any $S_k, m < k \leq n$, and note that $S_k\subseteq A$, since otherwise there would be $m+1$ distinct pairs. Now define the sequence of intervals $\{I_j\subseteq M\}$, where $$ I_1 = \{i\in M:S_k\cap S_i\neq \emptyset~\text{and}~S_i\cap B = \emptyset\}, $$ and $$I_j = \{i\in M:S_i\cap X_{I_{j-1}}\neq \emptyset~\text{and}~S_i\cap B = \emptyset\}, j > 1.$$
Then $X_{I_j}\cap B = \emptyset$ and $S_k\subseteq X_{I_1}\subseteq\cdots\subseteq X_{I_j}$ for all $j\geq 1$ by construction. Furthermore, since for each $x\in X_{I_j}$ there is at least one $S_i, i \in M,$ such that $x\in S_i$ by assumption, it follows that $$ \left|X_{I_j}\right|\leq \left|I_{j+1}\right| \leq\left|X_{I_{j+1}}\right|\leq m $$ for all $j\geq 1$. Thus, it follows that there is a $p\geq 1$, such that $\left|X_{I_p}\right|=\left|I_p\right|$.
Finally since $k\notin M$, $$|I_p \cup \{k\}| = |I_p|+1 > |I_p| = |X_{I_p}| = |S_k \cup X_{I_p}|.$$