[proofplan] The forward implication is a counting argument: intersect a proposed cover by independent sets with an arbitrary subset $A \subset E$, then compare each intersection with the rank of $A$. For the converse, form the union matroid of $k$ copies of $M$ and use the matroid union rank formula. The assumed inequality forces the rank of $E$ in this union matroid to be $|E|$, so $E$ is independent in the union matroid and therefore is a union of $k$ independent sets of the original matroid. [/proofplan] [step:Intersect a cover with an arbitrary subset and count by rank] Assume that there exist independent sets $I_1,\dots,I_k \in \mathcal I$ such that $E = I_1 \cup \cdots \cup I_k$. Let $A \subset E$ be arbitrary. For each index $j \in \{1,\dots,k\}$, define $A_j := A \cap I_j$. Since $\mathcal I$ is hereditary and $I_j \in \mathcal I$, each $A_j$ is independent in $M$. Since $A_j \subset A$, the definition of the rank function gives $|A_j| \leq r(A)$. Moreover, $A = A \cap E = A \cap (I_1 \cup \cdots \cup I_k) = A_1 \cup \cdots \cup A_k$. By subadditivity of cardinality for finite unions, \begin{align*} |A| \leq \sum_{j=1}^k |A_j|. \end{align*} Combining this with $|A_j| \leq r(A)$ for every $j$ gives \begin{align*} |A| \leq \sum_{j=1}^k r(A) = k r(A). \end{align*} Since $A \subset E$ was arbitrary, the stated inequality holds for every subset $A \subset E$. [/step] [step:Apply the matroid union rank formula to $k$ copies of $M$] Conversely, assume that $|A| \leq k r(A)$ for every subset $A \subset E$. By Androma's convention, $\mathbb N = \{1,2,3,\dots\}$, so $k \geq 1$ and the following finite family of $k$ matroids is nonempty. For each $j \in \{1,\dots,k\}$, let $M_j = (E,\mathcal I_j)$ denote a copy of $M$, meaning that $\mathcal I_j = \mathcal I$ as a collection of subsets of $E$. Let $M^{\vee k}$ denote the union matroid of $M_1,\dots,M_k$ on the ground set $E$. By definition of the union matroid, a subset $X \subset E$ is independent in $M^{\vee k}$ if and only if there exist sets $X_1,\dots,X_k \in \mathcal I$ such that $X = X_1 \cup \cdots \cup X_k$. Let $\rho: 2^E \to \mathbb N \cup \{0\}$ be the rank function of $M^{\vee k}$. By the [Matroid Union Theorem](/theorems/5815), applied to the nonempty finite family of matroids $M_1,\dots,M_k$ with common finite ground set $E$, the rank of $E$ in the [union matroid](/theorems/5815) $M^{\vee k}$ is \begin{align*} \rho(E) = \min_{A \subset E}\bigl(|E \setminus A| + k r(A)\bigr). \end{align*} [guided] We want to convert the numerical hypothesis $|A| \leq k r(A)$ into an actual covering of $E$ by $k$ independent sets. The union matroid is designed precisely for this conversion: it packages all subsets expressible as a union of $k$ independent sets into the independent sets of one matroid. For each $j \in \{1,\dots,k\}$, define $M_j = (E,\mathcal I_j)$ to be a copy of $M$, where $\mathcal I_j = \mathcal I$. The [union matroid](/theorems/5815) $M^{\vee k}$ of $M_1,\dots,M_k$ is the matroid on $E$ whose independent subsets are exactly those subsets $X \subset E$ for which there exist $X_1,\dots,X_k \in \mathcal I$ satisfying $X = X_1 \cup \cdots \cup X_k$. Thus, proving that $E$ is independent in $M^{\vee k}$ is exactly the same as proving that $E$ can be written as a union of $k$ independent sets of the original matroid $M$. Let $\rho: 2^E \to \mathbb N \cup \{0\}$ be the rank function of $M^{\vee k}$. We apply the [Matroid Union Theorem](/theorems/5815). Its hypotheses are satisfied because $k \geq 1$, and $M_1,\dots,M_k$ are a nonempty finite family of matroids on the same finite ground set $E$. Since each $M_j$ is a copy of $M$, each copy has the same rank function $r$. Therefore the rank formula gives \begin{align*} \rho(E) = \min_{A \subset E}\bigl(|E \setminus A| + k r(A)\bigr). \end{align*} This formula is the bridge between the pointwise inequalities on subsets $A$ and the global assertion that $E$ is independent in the union matroid. [/guided] [/step] [step:Use the subset inequality to force full rank in the union matroid] Let $A \subset E$ be arbitrary. Since $E$ is finite, $|E| = |E \setminus A| + |A|$. Using the assumed inequality $|A| \leq k r(A)$, we obtain \begin{align*} |E| \leq |E \setminus A| + k r(A). \end{align*} Since this holds for every $A \subset E$, it follows that \begin{align*} |E| \leq \min_{A \subset E}\bigl(|E \setminus A| + k r(A)\bigr). \end{align*} By the rank formula from the preceding step, $|E| \leq \rho(E)$. On the other hand, $\rho(E) \leq |E|$ because the rank of a subset of a finite matroid is at most its cardinality. Hence $\rho(E) = |E|$. [guided] Now we use the hypothesis in exactly the form needed by the union-matroid rank formula. Fix an arbitrary subset $A \subset E$. Because $E$ is finite and $A \subset E$, the disjoint union decomposition $E = (E \setminus A) \cup A$ gives \begin{align*} |E| = |E \setminus A| + |A|. \end{align*} The assumed inequality says $|A| \leq k r(A)$ for this same subset $A$. Substituting that upper bound for $|A|$ gives \begin{align*} |E| \leq |E \setminus A| + k r(A). \end{align*} Since $A \subset E$ was arbitrary, every number in the family $\{|E \setminus A| + k r(A) : A \subset E\}$ is at least $|E|$. Therefore its minimum is also at least $|E|$: \begin{align*} |E| \leq \min_{A \subset E}\bigl(|E \setminus A| + k r(A)\bigr). \end{align*} The [Matroid Union Theorem](/theorems/5815) identified this minimum with $\rho(E)$, where $\rho: 2^E \to \mathbb N \cup \{0\}$ is the rank function of the union matroid $M^{\vee k}$. Hence $|E| \leq \rho(E)$. The reverse inequality $\rho(E) \leq |E|$ is the defining bound for any matroid rank function: the rank of a subset cannot exceed its cardinality. Combining the two inequalities gives \begin{align*} \rho(E) = |E|. \end{align*} This full-rank conclusion is the point where the numerical subset condition becomes a structural statement about the union matroid. [/guided] [/step] [step:Translate full rank back into a cover by independent sets] Since $\rho(E) = |E|$, the rank characterization of independence built into the definition of a matroid rank function implies that the set $E$ is independent in the [union matroid](/theorems/5815) $M^{\vee k}$: a subset $X$ is independent if and only if its rank equals $|X|$. By the definition of independence in $M^{\vee k}$, there exist sets $I_1,\dots,I_k \in \mathcal I$ such that $E = I_1 \cup \cdots \cup I_k$. Thus $E$ is a union of $k$ independent sets of $M$. Combining this implication with the counting implication proved above establishes the equivalence. [/step]