[proofplan] The necessity is immediate from restricting any independent system of representatives to a subfamily. For sufficiency, we replace each set $A_i$ by a separate labelled fibre, so that choosing one element from each $A_i$ becomes choosing one element from each fibre. We put two matroids on the labelled ground set: one records the condition “at most one element from each fibre,” and the other records distinctness and independence after projection to $E$. Edmonds' matroid intersection theorem then reduces existence of a common independent set of size $m$ to rank inequalities, and the fibre structure compresses those inequalities exactly to Rado's displayed condition. [/proofplan] [step:Derive the rank inequalities from an independent system of representatives] Assume first that there is an injective choice function \begin{align*} x:\{1,\dots,m\}\to E \end{align*} such that $x_i \in A_i$ for every $i$ and $\{x_1,\dots,x_m\}\in\mathcal I$. Let $J\subset \{1,\dots,m\}$ be arbitrary. Since $x$ is injective, the set \begin{align*} X_J:=\{x_i:i\in J\} \end{align*} has cardinality $|J|$. Since $X_J\subset \{x_1,\dots,x_m\}$ and $\mathcal I$ is hereditary, $X_J\in\mathcal I$. Also $X_J\subset \bigcup_{i\in J}A_i$. By the definition of the matroid rank function as the maximum cardinality of an independent subset contained in a given set, \begin{align*} r\left(\bigcup_{i\in J}A_i\right)\ge |X_J|=|J|. \end{align*} Since $J$ was arbitrary, the stated inequalities are necessary. [/step] [step:Build two matroids on the labelled copy of the family] Assume now that \begin{align*} r\left(\bigcup_{i\in J} A_i\right) \ge |J| \end{align*} for every $J\subset \{1,\dots,m\}$. In particular, taking $J=\{i\}$ gives $r(A_i)\ge 1$, so each $A_i$ is nonempty. For each $i\in\{1,\dots,m\}$, define the labelled fibre \begin{align*} F_i:=\{i\}\times A_i. \end{align*} Define the finite labelled ground set \begin{align*} F:=\bigcup_{i=1}^m F_i. \end{align*} The union is disjoint because the first coordinate records the index. Define the projection map \begin{align*} \pi:F\to E \end{align*} by sending each labelled element $(i,e)\in F$ to $\pi(i,e):=e$. Define a family $\mathcal I_1\subset 2^F$ by \begin{align*} \mathcal I_1:=\{S\subset F: |S\cap F_i|\le 1 \text{ for every } i\in\{1,\dots,m\}\}. \end{align*} This is the partition matroid on the fibres $F_i$: heredity is immediate from inclusion, and the matroid exchange axiom follows because if $S,T\in\mathcal I_1$ with $|S|<|T|$, then some fibre $F_i$ meets $T$ but not $S$, so any element of $T\cap F_i$ can be added to $S$ while preserving the condition $|S\cap F_j|\le 1$ for every $j$. Let $N_1=(F,\mathcal I_1)$, and let $r_1$ denote its rank function. Define a second family $\mathcal I_2\subset 2^F$ by \begin{align*} \mathcal I_2:=\{S\subset F:\pi|_S \text{ is injective and } \pi(S)\in\mathcal I\}. \end{align*} This is also a matroid. Heredity follows because restrictions of injective maps are injective and subsets of independent sets in $M$ are independent. For exchange, let $S,T\in\mathcal I_2$ with $|S|<|T|$. Then $\pi(S)$ and $\pi(T)$ are independent in $M$, and \begin{align*} |\pi(S)|=|S|<|T|=|\pi(T)|. \end{align*} By the matroid exchange axiom in $M$, there exists $e\in \pi(T)\setminus \pi(S)$ such that $\pi(S)\cup\{e\}\in\mathcal I$. Choose $t\in T$ with $\pi(t)=e$. Since $e\notin\pi(S)$, the map $\pi|_{S\cup\{t\}}$ is injective, and $\pi(S\cup\{t\})=\pi(S)\cup\{e\}$ is independent in $M$. Hence $S\cup\{t\}\in\mathcal I_2$. Let $N_2=(F,\mathcal I_2)$, and let $r_2$ denote its rank function. [/step] [step:Identify representatives with common independent sets of size $m$] A subset $S\subset F$ is common independent in $N_1$ and $N_2$ if and only if it chooses at most one labelled element from each fibre, its projection has no repeated element of $E$, and its projected set is independent in $M$. If an injective independent representative system $x_i\in A_i$ is given, then \begin{align*} S_x:=\{(i,x_i):i\in\{1,\dots,m\}\} \end{align*} belongs to $\mathcal I_1\cap\mathcal I_2$ and has cardinality $m$. Conversely, suppose $S\in\mathcal I_1\cap\mathcal I_2$ and $|S|=m$. Since $S$ contains at most one element from each of the $m$ nonempty fibres $F_i$, it must contain exactly one element from every fibre. For each $i$, let $x_i\in A_i$ be the unique element satisfying $(i,x_i)\in S$. Since $S\in\mathcal I_2$, the projection $\pi|_S$ is injective and $\pi(S)=\{x_1,\dots,x_m\}\in\mathcal I$. Thus common independent sets of size $m$ are exactly independent systems of distinct representatives. [/step] [step:Compute the two rank functions on labelled subsets] For every subset $C\subset F$, the rank of $C$ in $N_1$ is \begin{align*} r_1(C)=|\{i\in\{1,\dots,m\}:C\cap F_i\ne\varnothing\}|. \end{align*} Indeed, an independent subset of $C$ in $N_1$ contains at most one element from each fibre meeting $C$, and this upper bound is attained by choosing one element from each nonempty intersection $C\cap F_i$. For every subset $C\subset F$, the rank of $C$ in $N_2$ is \begin{align*} r_2(C)=r(\pi(C)). \end{align*} If $S\subset C$ is independent in $N_2$, then $\pi(S)\subset \pi(C)$ is independent in $M$ and $|S|=|\pi(S)|$, so $|S|\le r(\pi(C))$. Conversely, choose an independent subset $T\subset \pi(C)$ with $|T|=r(\pi(C))$. For each $e\in T$, choose one element $c_e\in C$ such that $\pi(c_e)=e$, and define \begin{align*} S_T:=\{c_e:e\in T\}. \end{align*} Then $\pi|_{S_T}$ is injective, $\pi(S_T)=T\in\mathcal I$, and $S_T\subset C$, so $S_T\in\mathcal I_2$ and $r_2(C)\ge |T|=r(\pi(C))$. The two inequalities give the formula. [/step] [step:Reduce Edmonds' inequalities to the Rado inequalities] We use [Edmonds Matroid Intersection Theorem](/theorems/5814), applied to the two matroids $N_1$ and $N_2$ on the same finite ground set $F$. It states that the maximum cardinality of a subset of $F$ independent in both $N_1$ and $N_2$ is \begin{align*} \min_{B\subset F}\bigl(r_1(B)+r_2(F\setminus B)\bigr). \end{align*} Therefore it is enough to prove that \begin{align*} r_1(B)+r_2(F\setminus B)\ge m \end{align*} for every $B\subset F$. Fix $B\subset F$. Define the set of indices whose whole fibre survives in the complement by \begin{align*} J(B):=\{i\in\{1,\dots,m\}:F_i\subset F\setminus B\}. \end{align*} Equivalently, $i\in J(B)$ if and only if $B\cap F_i=\varnothing$. Since every $A_i$ is nonempty, the rank formula for $N_1$ gives \begin{align*} r_1(B)=m-|J(B)|. \end{align*} Also, \begin{align*} \bigcup_{i\in J(B)}F_i\subset F\setminus B. \end{align*} Applying $\pi$ gives \begin{align*} \bigcup_{i\in J(B)}A_i\subset \pi(F\setminus B). \end{align*} The rank function $r$ of a matroid is monotone under inclusion, so the formula for $r_2$ gives \begin{align*} r_2(F\setminus B)=r(\pi(F\setminus B))\ge r\left(\bigcup_{i\in J(B)}A_i\right). \end{align*} By the assumed Rado inequality applied to $J(B)$, \begin{align*} r\left(\bigcup_{i\in J(B)}A_i\right)\ge |J(B)|. \end{align*} Combining these estimates, \begin{align*} r_1(B)+r_2(F\setminus B)\ge m-|J(B)|+|J(B)|=m. \end{align*} [guided] We prove the rank inequality required by Edmonds' matroid intersection theorem for an arbitrary subset $B\subset F$: \begin{align*} r_1(B)+r_2(F\setminus B)\ge m. \end{align*} Recall the objects in this step. For each $i\in\{1,\dots,m\}$, the labelled fibre is $F_i:=\{i\}\times A_i$, the labelled ground set is the disjoint union $F:=\bigcup_{i=1}^m F_i$, and the projection map is \begin{align*} \pi:F\to E \end{align*} with $\pi(i,e):=e$ for every $(i,e)\in F$. The matroid $N_1=(F,\mathcal I_1)$ is the partition matroid whose independent sets meet each fibre $F_i$ in at most one element, and $r_1$ is its rank function. The matroid $N_2=(F,\mathcal I_2)$ has independent sets $S\subset F$ such that $\pi|_S:S\to E$ is injective and $\pi(S)\in\mathcal I$, and $r_2$ is its rank function. The difficulty is that $B$ may cut through the fibres in an arbitrary way. The partition rank only records which fibres $B$ meets, so define \begin{align*} J(B):=\{i\in\{1,\dots,m\}:F_i\subset F\setminus B\}. \end{align*} Equivalently, $i\in J(B)$ if and only if $B\cap F_i=\varnothing$. Since the assumed Rado inequality applied to the singleton $\{i\}$ gives $r(A_i)\ge 1$, no $A_i$ is empty; hence no fibre $F_i$ is empty. Therefore $B$ meets exactly the fibres indexed by $\{1,\dots,m\}\setminus J(B)$. In the partition matroid $N_1$, an independent subset of $B$ contains at most one element from each fibre that $B$ meets, and this bound is attained by choosing one element from every nonempty intersection $B\cap F_i$. Hence \begin{align*} r_1(B)=m-|J(B)|. \end{align*} Next we estimate $r_2(F\setminus B)$. First we justify the rank formula for $N_2$ on the particular set $F\setminus B$. If $S\subset F\setminus B$ is independent in $N_2$, then $\pi|_S$ is injective and $\pi(S)$ is independent in $M$, so \begin{align*} |S|=|\pi(S)|\le r(\pi(F\setminus B)). \end{align*} Conversely, choose an independent subset $T\subset \pi(F\setminus B)$ with $|T|=r(\pi(F\setminus B))$, which exists by the definition of matroid rank on the finite set $\pi(F\setminus B)$. For each $e\in T$, choose an element $c_e\in F\setminus B$ such that $\pi(c_e)=e$, and define \begin{align*} S_T:=\{c_e:e\in T\}. \end{align*} The chosen elements are distinct because the elements of $T$ are distinct and $\pi(c_e)=e$. Thus $\pi|_{S_T}$ is injective, $\pi(S_T)=T\in\mathcal I$, and $S_T\subset F\setminus B$, so $S_T$ is independent in $N_2$. Therefore \begin{align*} r_2(F\setminus B)=r(\pi(F\setminus B)). \end{align*} Now use the fibres missing from $B$. If $i\in J(B)$, then $F_i\subset F\setminus B$. Taking the union over all such indices gives \begin{align*} \bigcup_{i\in J(B)}F_i\subset F\setminus B. \end{align*} Applying the projection map $\pi:F\to E$ to this inclusion gives \begin{align*} \bigcup_{i\in J(B)}A_i\subset \pi(F\setminus B). \end{align*} Matroid rank is monotone under inclusion, so the preceding rank formula for $N_2$ yields \begin{align*} r_2(F\setminus B)=r(\pi(F\setminus B))\ge r\left(\bigcup_{i\in J(B)}A_i\right). \end{align*} This is where the Rado hypothesis is used. Since $J(B)\subset\{1,\dots,m\}$, the assumed inequality gives \begin{align*} r\left(\bigcup_{i\in J(B)}A_i\right)\ge |J(B)|. \end{align*} Combining the estimate for $r_1(B)$ with the estimate for $r_2(F\setminus B)$ gives \begin{align*} r_1(B)+r_2(F\setminus B)\ge m-|J(B)|+|J(B)|=m. \end{align*} Thus the Edmonds inequality for the arbitrary subset $B\subset F$ follows from the Rado inequality for the index set $J(B)$. [/guided] [/step] [step:Apply matroid intersection and recover the desired representatives] Since \begin{align*} r_1(B)+r_2(F\setminus B)\ge m \end{align*} for every $B\subset F$, Edmonds' matroid intersection theorem gives a common independent subset $S\subset F$ with $|S|\ge m$. Because $S\in\mathcal I_1$, it contains at most one element from each of the $m$ fibres, so $|S|\le m$. Hence $|S|=m$. By the identification above, this common independent set determines elements $x_i\in A_i$ for $i\in\{1,\dots,m\}$ such that the map $i\mapsto x_i$ is injective and $\{x_1,\dots,x_m\}\in\mathcal I$. This proves the sufficiency of the Rado inequalities, and together with the necessity proved earlier completes the proof. [/step]