[proofplan] The necessity is immediate from monotonicity of rank: any independent representative set chosen from a subfamily has size equal to the number of sets in that subfamily and lies inside their union. For sufficiency we induct on $k$. If a proper nonempty subfamily is tight, we first choose representatives for it, contract them, and apply induction to the remaining family. If no proper nonempty subfamily is tight, we choose a nonloop representative from $B_k$, contract it, and use the strictness of all proper rank inequalities to preserve the Hall-type condition for the remaining sets. [/proofplan] [step:Show that any independent transversal forces the rank inequalities] Assume that there are distinct elements $b_1, \dots, b_k \in E$ such that $b_i \in B_i$ for each $i \in \{1, \dots, k\}$ and the set \begin{align*} I := \{b_1, \dots, b_k\} \end{align*} is independent in $N$. Since the representatives are distinct, $|I| = k$. Let $S \subseteq \{1, \dots, k\}$ be arbitrary, and define \begin{align*} I_S := \{b_i : i \in S\}. \end{align*} Then $I_S \subseteq \bigcup_{i \in S} B_i$, and $I_S$ is independent because it is a subset of the independent set $I$. By [Rank Monotonicity for Matroids](/theorems/5807), applied to the inclusion $I_S \subseteq \bigcup_{i \in S} B_i$, we obtain \begin{align*} r_N\left(\bigcup_{i \in S} B_i\right) \ge r_N(I_S) = |I_S| = |S|. \end{align*} Since $S$ was arbitrary, the rank inequalities hold for every $S \subseteq \{1, \dots, k\}$. [guided] Assume that an independent transversal has already been chosen. Thus there are distinct elements $b_1, \dots, b_k \in E$ with $b_i \in B_i$ for every $i \in \{1, \dots, k\}$, and the set \begin{align*} I := \{b_1, \dots, b_k\} \end{align*} is independent in $N$. The distinctness condition implies $|I| = k$. Now fix an arbitrary subset $S \subseteq \{1, \dots, k\}$ and define the sub-transversal \begin{align*} I_S := \{b_i : i \in S\}. \end{align*} Each element $b_i$ with $i \in S$ lies in $B_i$, so $I_S \subseteq \bigcup_{i \in S} B_i$. Also, $I_S$ is independent because it is a subset of the independent set $I$. The matroid rank of an independent set equals its cardinality, so \begin{align*} r_N(I_S) = |I_S| = |S|. \end{align*} By [Rank Monotonicity for Matroids](/theorems/5807), applied to the inclusion $I_S \subseteq \bigcup_{i \in S} B_i$, enlarging the set cannot decrease rank. Hence \begin{align*} r_N\left(\bigcup_{i \in S} B_i\right) \ge r_N(I_S) = |S|. \end{align*} Because $S$ was arbitrary, the rank inequality holds for every subfamily. [/guided] [/step] [step:Prepare the induction and the contraction rank formula] We prove the converse by induction on $k$. For $k = 1$, the hypothesis applied to $S = \{1\}$ gives \begin{align*} r_N(B_1) \ge 1. \end{align*} Hence $B_1$ contains an element $b_1$ that is not a loop of $N$, and $\{b_1\}$ is independent. Assume now that $k \ge 2$, and assume the theorem has been proved for all smaller positive integers. We use the standard rank formula for matroid contraction in the proof. If $C \subseteq E$ is independent in $N$, then the contraction $N / C$ is the matroid on $E \setminus C$ whose rank function satisfies, for every $X \subseteq E \setminus C$, \begin{align*} r_{N / C}(X) = r_N(X \cup C) - r_N(C). \end{align*} Since $C$ is independent, $r_N(C) = |C|$. Moreover, for $X \subseteq E \setminus C$, the set $X$ is independent in $N / C$ exactly when $X \cup C$ is independent in $N$. [guided] We prove the sufficiency direction by induction on the number of sets. The case $k = 1$ already contains the basic idea. The condition for $S = \{1\}$ says \begin{align*} r_N(B_1) \ge 1. \end{align*} By the definition of rank, this means that $B_1$ contains an independent subset of size $1$. Equivalently, there is an element $b_1 \in B_1$ that is not a loop, and then $\{b_1\}$ is the required independent transversal. For the induction step, the operation that lets us choose some representatives first and then continue with the remaining sets is contraction. We will only contract independent sets. By the standard rank formula for matroid contraction, if $C \subseteq E$ is independent in $N$, the contracted matroid $N / C$ has ground set $E \setminus C$ and rank function \begin{align*} r_{N / C}(X) = r_N(X \cup C) - r_N(C) \end{align*} for every $X \subseteq E \setminus C$. Since $C$ is independent, $r_N(C) = |C|$. The point of this formula is that an independent set in $N / C$ can be appended to $C$ to obtain an independent set in $N$: for $X \subseteq E \setminus C$, the set $X$ is independent in $N / C$ precisely when $X \cup C$ is independent in $N$. This is exactly the bookkeeping needed for transversals. After we choose representatives for one part of the family, contraction records the remaining freedom while remembering that the already chosen representatives must stay independent. [/guided] [/step] [step:Split off a proper tight subfamily when one exists] Assume that there is a proper nonempty subset $S \subsetneq \{1, \dots, k\}$ such that \begin{align*} r_N\left(\bigcup_{i \in S} B_i\right) = |S|. \end{align*} Define \begin{align*} U_S := \bigcup_{i \in S} B_i. \end{align*} For every $T \subseteq S$, the assumed rank condition gives \begin{align*} r_N\left(\bigcup_{i \in T} B_i\right) \ge |T|. \end{align*} Relabel the finite family $(B_i)_{i \in S}$ as a family of $|S|$ sets; the displayed rank inequalities are unchanged by this relabeling. By the induction hypothesis applied to this relabeled subfamily in the matroid $N$, there are elements $b_i \in B_i$ for $i \in S$ such that \begin{align*} C := \{b_i : i \in S\} \end{align*} is independent in $N$. Since $C \subseteq U_S$ and $|C| = |S| = r_N(U_S)$, the set $C$ is a basis of $U_S$ in $N$, so \begin{align*} r_N(C) = r_N(U_S) = |S|. \end{align*} Let \begin{align*} J := \{1, \dots, k\} \setminus S. \end{align*} We will apply induction to the subfamily $(B_j \setminus C)_{j \in J}$ in the contracted matroid $N / C$, after relabeling this finite family as a family of $|J|$ sets. Let $R \subseteq J$ be arbitrary, and define \begin{align*} U_R := \bigcup_{j \in R} B_j. \end{align*} By the contraction rank formula, \begin{align*} r_{N / C}\left(\bigcup_{j \in R} (B_j \setminus C)\right) = r_N\left(C \cup \bigcup_{j \in R} (B_j \setminus C)\right) - |S|. \end{align*} Since $C \cup (B_j \setminus C) = C \cup B_j$ for each $j \in R$, we have \begin{align*} C \cup \bigcup_{j \in R} (B_j \setminus C) = C \cup U_R. \end{align*} We now compare $C \cup U_R$ with $U_S \cup U_R$. Since $N$ is a matroid on the finite set $E$, [Rank Submodularity for Matroids](/theorems/5808) applies to its rank function. Applying it to the sets $C \cup U_R$ and $U_S$ gives \begin{align*} r_N(C \cup U_R) + r_N(U_S) \ge r_N(U_S \cup U_R) + r_N((C \cup U_R) \cap U_S). \end{align*} Because $C \subseteq (C \cup U_R) \cap U_S$, [Rank Monotonicity for Matroids](/theorems/5807) gives \begin{align*} r_N((C \cup U_R) \cap U_S) \ge r_N(C). \end{align*} Using $r_N(C) = r_N(U_S) = |S|$, we obtain \begin{align*} r_N(C \cup U_R) \ge r_N(U_S \cup U_R). \end{align*} The original rank hypothesis applied to $S \cup R$ gives \begin{align*} r_N(U_S \cup U_R) \ge |S \cup R| = |S| + |R|. \end{align*} Therefore \begin{align*} r_{N / C}\left(\bigcup_{j \in R} (B_j \setminus C)\right) \ge |R|. \end{align*} Since the relabeled family has $|J| < k$ sets and satisfies the required rank inequalities in $N / C$, the induction hypothesis gives elements $b_j \in B_j \setminus C$ for $j \in J$ such that \begin{align*} D := \{b_j : j \in J\} \end{align*} is independent in $N / C$. Hence $C \cup D$ is independent in $N$, and the elements $b_i$ for $i \in \{1, \dots, k\}$ form the required independent transversal. [guided] Suppose a proper nonempty subfamily is tight. Choose $S \subsetneq \{1, \dots, k\}$ with $S \ne \varnothing$ and \begin{align*} r_N\left(\bigcup_{i \in S} B_i\right) = |S|. \end{align*} Define \begin{align*} U_S := \bigcup_{i \in S} B_i. \end{align*} For every $T \subseteq S$, the original hypothesis gives \begin{align*} r_N\left(\bigcup_{i \in T} B_i\right) \ge |T|. \end{align*} After relabeling the finite family $(B_i)_{i \in S}$ as a family of $|S|$ sets, the induction hypothesis gives representatives $b_i \in B_i$ for $i \in S$ such that \begin{align*} C := \{b_i : i \in S\} \end{align*} is independent in $N$. Because $C \subseteq U_S$ and $|C| = |S| = r_N(U_S)$, this independent set has maximal possible size inside $U_S$. Hence $C$ is a basis of $U_S$ and \begin{align*} r_N(C) = r_N(U_S) = |S|. \end{align*} Now define the remaining index set \begin{align*} J := \{1, \dots, k\} \setminus S. \end{align*} We want to solve the remaining representative problem in $N / C$, because independence in the contraction is exactly the condition needed to append the new representatives to the already chosen set $C$. Consider the family $(B_j \setminus C)_{j \in J}$ in $N / C$. Let $R \subseteq J$ be arbitrary, and define \begin{align*} U_R := \bigcup_{j \in R} B_j. \end{align*} The contraction rank formula gives \begin{align*} r_{N / C}\left(\bigcup_{j \in R} (B_j \setminus C)\right) = r_N\left(C \cup \bigcup_{j \in R} (B_j \setminus C)\right) - |S|. \end{align*} Since adjoining $C$ restores any elements of $C$ removed from the sets $B_j$, we have \begin{align*} C \cup \bigcup_{j \in R} (B_j \setminus C) = C \cup U_R. \end{align*} It remains to bound $r_N(C \cup U_R)$ from below. Rank submodularity applied to $C \cup U_R$ and $U_S$ gives \begin{align*} r_N(C \cup U_R) + r_N(U_S) \ge r_N(U_S \cup U_R) + r_N((C \cup U_R) \cap U_S). \end{align*} Because $C \subseteq (C \cup U_R) \cap U_S$, [Rank Monotonicity for Matroids](/theorems/5807) gives \begin{align*} r_N((C \cup U_R) \cap U_S) \ge r_N(C). \end{align*} Using $r_N(C) = r_N(U_S) = |S|$, the last two displays imply \begin{align*} r_N(C \cup U_R) \ge r_N(U_S \cup U_R). \end{align*} The original rank hypothesis applied to $S \cup R$ gives \begin{align*} r_N(U_S \cup U_R) \ge |S \cup R| = |S| + |R|, \end{align*} because $S$ and $R$ are disjoint. Therefore \begin{align*} r_{N / C}\left(\bigcup_{j \in R} (B_j \setminus C)\right) \ge |R|. \end{align*} Thus the remaining family satisfies Rado's rank condition in $N / C$. Since $|J| < k$, induction supplies elements $b_j \in B_j \setminus C$ for $j \in J$ such that \begin{align*} D := \{b_j : j \in J\} \end{align*} is independent in $N / C$. By the defining independence property of contraction, $C \cup D$ is independent in $N$. Combining the representatives indexed by $S$ with those indexed by $J$ gives an independent transversal for the whole family. [/guided] [/step] [step:Handle the case where every proper nonempty subfamily has excess rank] It remains to consider the case where no proper nonempty subset of $\{1, \dots, k\}$ is tight. Thus, for every nonempty proper subset $S \subsetneq \{1, \dots, k\}$, \begin{align*} r_N\left(\bigcup_{i \in S} B_i\right) \ge |S| + 1, \end{align*} because the rank is integer-valued. The hypothesis applied to $S = \{k\}$ gives $r_N(B_k) \ge 1$, so choose an element $b_k \in B_k$ such that $\{b_k\}$ is independent in $N$. Let \begin{align*} C := \{b_k\}. \end{align*} We verify the induction hypothesis for the family $(B_i \setminus C)_{i=1}^{k-1}$ in $N / C$. Let $R \subseteq \{1, \dots, k-1\}$ be arbitrary. If $R = \varnothing$, then \begin{align*} r_{N / C}(\varnothing) = 0 = |R|. \end{align*} If $R \ne \varnothing$, define \begin{align*} U_R := \bigcup_{i \in R} B_i. \end{align*} Since $R$ is a proper nonempty subset of $\{1, \dots, k\}$, the strict-rank case gives \begin{align*} r_N(U_R) \ge |R| + 1. \end{align*} Using the rank formula for matroid contraction and [Rank Monotonicity for Matroids](/theorems/5807), \begin{align*} r_{N / C}\left(\bigcup_{i \in R} (B_i \setminus C)\right) = r_N\left(C \cup \bigcup_{i \in R} (B_i \setminus C)\right) - 1. \end{align*} Since \begin{align*} C \cup \bigcup_{i \in R} (B_i \setminus C) = C \cup U_R \end{align*} and $U_R \subseteq C \cup U_R$, [Rank Monotonicity for Matroids](/theorems/5807) gives \begin{align*} r_N(C \cup U_R) \ge r_N(U_R) \ge |R| + 1. \end{align*} Therefore \begin{align*} r_{N / C}\left(\bigcup_{i \in R} (B_i \setminus C)\right) \ge |R|. \end{align*} By induction applied in $N / C$, there are elements $b_i \in B_i \setminus C$ for $i \in \{1, \dots, k-1\}$ such that \begin{align*} D := \{b_1, \dots, b_{k-1}\} \end{align*} is independent in $N / C$. Hence $D \cup C$ is independent in $N$. Since $b_i \in B_i$ for every $i \in \{1, \dots, k\}$, this gives the required independent transversal. [guided] In this case every proper nonempty subfamily has more rank than it minimally needs. Since rank is integer-valued, “not tight” means the stronger inequality \begin{align*} r_N\left(\bigcup_{i \in S} B_i\right) \ge |S| + 1 \end{align*} for each nonempty proper subset $S \subsetneq \{1, \dots, k\}$. We first choose the representative for the last set. The condition for $S = \{k\}$ says \begin{align*} r_N(B_k) \ge 1, \end{align*} so $B_k$ contains a nonloop element. Choose such an element and call it $b_k$. Define \begin{align*} C := \{b_k\}. \end{align*} Then $C$ is independent, so contraction by $C$ is allowed. Now we must check that the remaining sets still satisfy the rank condition after contraction. The remaining family is \begin{align*} (B_1 \setminus C), \dots, (B_{k-1} \setminus C) \end{align*} inside the contracted matroid $N / C$. Let $R \subseteq \{1, \dots, k-1\}$ be arbitrary. If $R = \varnothing$, the required inequality is \begin{align*} r_{N / C}(\varnothing) \ge 0, \end{align*} which holds because every matroid rank function has rank $0$ on the empty set. Suppose now that $R \ne \varnothing$, and define \begin{align*} U_R := \bigcup_{i \in R} B_i. \end{align*} Since $R$ does not contain $k$, it is a proper nonempty subset of $\{1, \dots, k\}$. Therefore the strict-rank assumption gives \begin{align*} r_N(U_R) \ge |R| + 1. \end{align*} The rank formula for matroid contraction gives \begin{align*} r_{N / C}\left(\bigcup_{i \in R} (B_i \setminus C)\right) = r_N\left(C \cup \bigcup_{i \in R} (B_i \setminus C)\right) - r_N(C). \end{align*} Because $C = \{b_k\}$ is independent, $r_N(C) = 1$. Also \begin{align*} C \cup \bigcup_{i \in R} (B_i \setminus C) = C \cup U_R. \end{align*} The set $U_R$ is contained in $C \cup U_R$, so [Rank Monotonicity for Matroids](/theorems/5807) gives \begin{align*} r_N(C \cup U_R) \ge r_N(U_R). \end{align*} Combining these identities and inequalities, \begin{align*} r_{N / C}\left(\bigcup_{i \in R} (B_i \setminus C)\right) \ge (|R| + 1) - 1 = |R|. \end{align*} Thus every subfamily of the remaining sets satisfies the same Hall-type rank condition in $N / C$. By the induction hypothesis, there are elements $b_i \in B_i \setminus C$ for $i = 1, \dots, k-1$ such that \begin{align*} D := \{b_1, \dots, b_{k-1}\} \end{align*} is independent in $N / C$. The defining property of contraction then says that $D \cup C$ is independent in $N$. Since $C = \{b_k\}$ and each $b_i$ lies in its assigned set $B_i$, the elements $b_1, \dots, b_k$ form an independent transversal. [/guided] [/step] [step:Conclude the induction] The tight-subfamily case and the no-tight-proper-subfamily case cover all possibilities. In both cases the rank hypothesis for the family $B_1, \dots, B_k$ produces elements $b_i \in B_i$ such that $\{b_1, \dots, b_k\}$ is independent in $N$. By induction on the positive integer $k$, the sufficiency direction holds for every finite family $B_1, \dots, B_k$. Together with the necessity proved above, this establishes the equivalence. [guided] The induction has two exhaustive cases. If a proper nonempty subfamily is tight, we solve that subfamily first, contract the independent representatives, and apply induction to the remaining sets. If no proper nonempty subfamily is tight, we choose one nonloop representative from $B_k$, contract it, and the strict rank inequalities preserve the hypothesis for $B_1, \dots, B_{k-1}$. In both cases, the rank hypothesis produces distinct representatives $b_i \in B_i$ whose full set is independent in $N$. Therefore the sufficiency direction follows by induction on the positive integer $k$. The necessity direction was proved directly from rank monotonicity, so the two conditions are equivalent. [/guided] [/step]