[proofplan] We translate independence of $X$ in the transversal matroid into the existence of distinct admissible indices assigned to the elements of $X$. For each element $x \in X$, the admissible indices form a subset $B_x \subseteq \{1,\dots,m\}$. For the converse direction, the displayed condition with $Y=X$ first forces $|X| \le m$, so $X$ is finite and the finite Hall marriage theorem applies to the family $(B_x)_{x \in X}$. The Hall condition is exactly the displayed inequality, after rewriting the union of the $B_y$ for $y \in Y$ as the set of indices whose $A_i$ meets $Y$. [/proofplan] [step:Translate independence into a system of distinct admissible indices] For each $x \in X$, define the admissible-index set $B_x := \{i \in \{1,\dots,m\}: x \in A_i\}$. A [system of distinct representatives](/theorems/2579) for the family $(B_x)_{x \in X}$ is an injective map $\varphi: X \to \{1,\dots,m\}$ such that $\varphi(x) \in B_x$ for every $x \in X$. By the definition of $B_x$, the condition $\varphi(x) \in B_x$ is equivalent to $x \in A_{\varphi(x)}$. Therefore such a system of distinct representatives is exactly the same data as an injective assignment witnessing that $X$ is independent in the transversal matroid $M[A_1,\dots,A_m]$. [guided] We first convert the matroid language into the language used by Hall's theorem. For an element $x \in X$, define \begin{align*} B_x := \{i \in \{1,\dots,m\}: x \in A_i\}. \end{align*} Thus $B_x$ is the set of all indices that are allowed to represent $x$. A system of distinct representatives for the family $(B_x)_{x \in X}$ is an injective map $\varphi: X \to \{1,\dots,m\}$ with $\varphi(x) \in B_x$ for every $x \in X$. The injectivity means that two different elements of $X$ are not assigned the same index. The membership condition $\varphi(x) \in B_x$ means, by the definition of $B_x$, that $x \in A_{\varphi(x)}$. This is precisely the definition of independence in the transversal matroid presented by $(A_i)_{i=1}^m$: the elements of $X$ can be matched injectively to admissible members of the presentation. Hence $X$ is independent in $M[A_1,\dots,A_m]$ if and only if the family $(B_x)_{x \in X}$ has a system of distinct representatives. [/guided] [/step] [step:Rewrite Hall's condition in terms of the presentation sets] Let $Y \subseteq X$. The union of the admissible-index sets over $Y$ is $\bigcup_{y \in Y} B_y = \{i \in \{1,\dots,m\}: A_i \cap Y \ne \varnothing\}$. Indeed, an index $i$ lies in $\bigcup_{y \in Y} B_y$ if and only if there exists $y \in Y$ with $i \in B_y$, which is equivalent to the existence of $y \in Y$ with $y \in A_i$, and this is equivalent to $A_i \cap Y \ne \varnothing$. [/step] [step:Use the finite Hall theorem after forcing $X$ to be finite] If $X$ is independent, then by the first step there is an injective map $\varphi: X \to \{1,\dots,m\}$ such that $\varphi(x) \in B_x$ for every $x \in X$. For each $Y \subseteq X$, the restriction $\varphi|_Y: Y \to \{1,\dots,m\}$ is injective and satisfies $\varphi(Y) \subseteq \bigcup_{y \in Y} B_y$. Hence \begin{align*} |Y| = |\varphi(Y)| \le \left|\bigcup_{y \in Y} B_y\right|. \end{align*} Using the identity from the previous step gives the displayed inequality. Conversely, assume the displayed inequality holds for every $Y \subseteq X$. Taking $Y=X$ gives \begin{align*} |X| \le \left|\{i \in \{1,\dots,m\}: A_i \cap X \ne \varnothing\}\right| \le m, \end{align*} so $X$ is finite because the presentation index set $\{1,\dots,m\}$ is finite. The finite Hall marriage theorem applies to the finite family $(B_x)_{x \in X}$ and gives a system of distinct representatives if and only if, for every subset $Y \subseteq X$, \begin{align*} \left|\bigcup_{y \in Y} B_y\right| \ge |Y|. \end{align*} By the identity from the previous step, this condition is exactly the displayed inequality. Therefore the family $(B_x)_{x \in X}$ has a system of distinct representatives, and by the first step this is equivalent to $X$ being independent in $M[A_1,\dots,A_m]$. This proves the theorem. [/step]