# Short proof of Hall's theorem

Studying the proof of Hall's theorem in my book I started to wonder if there is a shorter way to prove it. Following is an attempt that I think works but (being short) makes me wonder if I made a mistake. Can someone double check?

For a collection of sets $S_1,\ldots,S_m$ we say that they have a collection of distinct represenatives if there exists distinct elements $x_1,\ldots,x_m$ such that $x_i \in S_i$ for $i = 1,\ldots, m.$ We say that our collection of sets satisfies Hall's criterion if $$\left |\bigcup_{i \in I} S_i \right | \geq |I| \quad \mbox{for all } I \subseteq \{1,\ldots,m\}.$$

Claim. If $S_1,\ldots,S_m$ satisfy Hall's criterion then they have a set of distinct representatives.

Proof. We prove the claim by induction on $m.$ For $m=1$ the claim is obvious so suppose the claim holds for all $m < k$ for some $k$ and let $S_1,\ldots,S_m$ be a collection of sets satisfying Hall's criterion. Let $\{x_1,\ldots,x_{m-1}\}$ be the set of distinct representatives for $S_1,\ldots,S_{m-1}$ guaranteed by the indcution hypothesis. If $\{x_1,\ldots,x_{m-1}\} \ne S_m$ then we are done. If $\{x_1,\ldots,x_{m-1}\} = S_m$ that then $\left |\bigcup_{i=1}^{m-1} S_i \right | > m-1$ since otherwise $S_1,\ldots,S_m$ do not satisfy Hall's criterion. But this implies that for some $i$ there exist a $x_i' \in S_i$ such that $x_i' \not \in S_m$ and hence we can take $\{x_1,\ldots,x_{i-1}, x_i',x_{i+1},\ldots,x_{m-1},x_i\}$ as our set of distinct representatives. $\square$

Anyone happens to see a flaw in the above proof?

When you say "If $\{x_1, \ldots, x_{m-1}\} \ne S_m$ we are done", I do not see why that is the case. It could be that $S_m$ is a proper subset of $\{x_1, \ldots, x_{m-1}\}$, in which case your subsequent argument does not work, because you do not know that $x_i \in S_m$.
• I don't see an easy correction. The problem is, suppose you had $S_1 = S_2 = \ldots = S_{m-1} = S$ where $S$ is some set of size $m$, but $S_m$ consists of just a single element from $S$. Then Hall's criterion is clearly satisfied, but you have to choose the representatives from $S_1, \ldots, S_{m-1}$ carefully, avoiding the element in $S_m$. However, when you start the argument with "by induction there are representatives from $S_1, \ldots, S_{m-1}$" you have no control over the representatives you get. – Ted Apr 22 '13 at 16:17
• Wouldn't it work to say given that $S \subseteq \{x_1,\ldots,x_m\}$ take all the sets that intersect with $S$ and apply a similar argument to these sets? – Jernej Apr 22 '13 at 16:21
• I don't understand; can you elaborate further? One thing I thought of, but does not work, is this: Suppose that $S_m = \{x_1, \ldots, x_k\}$ for some $k<m$, and suppose $x_i \in S_i$ for $1 \le i \le k$. Then by Hall's criterion $\{S_1, S_2, \ldots, S_k, S_m\}$ has at least $k+1$ elements together, so there is some element $x$ in one of these $S$'s that is not in $S_m$. The problem is that $x$ could already be used as the representative from another $S_i$ where $i>k$. – Ted Apr 22 '13 at 16:35