[proofplan]
We verify the independent-set axioms for a matroid. The empty set is independent because the rank bounds force $r(\varnothing)=0$. Heredity follows by bounding the rank increase from a subset to an independent superset one element at a time. For exchange, if no element of the larger independent set outside the smaller one can be added to the smaller set, submodularity forces the union to have the same rank as the smaller set, contradicting the independence of the larger set.
[/proofplan]
[step:Show that the empty set is independent]
By the first two rank axioms applied to $A=\varnothing$, we have $0 \le r(\varnothing)$ and $r(\varnothing) \le |\varnothing|=0$. Hence $r(\varnothing)=0=|\varnothing|$, so $\varnothing \in \mathcal{I}$.
[/step]
[step:Bound the rank increase caused by adjoining finitely many elements]
Let $A \subset E$ and let $F \subset E \setminus A$ be finite. We prove $r(A \cup F) \le r(A)+|F|$.
Since $E$ is finite, write $F=\{e_1,\dots,e_m\}$, where $m=|F|$. Define subsets $A_k \subset E$ for $0 \le k \le m$ by $A_k := A \cup \{e_1,\dots,e_k\}$.
For each $1 \le k \le m$, submodularity applied to $A_{k-1}$ and $\{e_k\}$ gives
\begin{align*}
r(A_k)+r(A_{k-1}\cap \{e_k\}) \le r(A_{k-1})+r(\{e_k\}).
\end{align*}
Because $e_k \notin A_{k-1}$, we have $A_{k-1}\cap \{e_k\}=\varnothing$. Also $r(\{e_k\})\le |\{e_k\}|=1$. Since $r(\varnothing)\ge 0$, it follows that
\begin{align*}
r(A_k) \le r(A_{k-1})+1.
\end{align*}
Iterating this inequality from $k=1$ to $k=m$ gives
\begin{align*}
r(A \cup F)=r(A_m)\le r(A_0)+m=r(A)+|F|.
\end{align*}
[guided]
The point of this step is to extract from submodularity the familiar fact that adding one element can increase rank by at most one, and then iterate it.
Let $A \subset E$ and let $F \subset E \setminus A$ be finite. Since $E$ is finite, we may enumerate $F$ as $F=\{e_1,\dots,e_m\}$, where $m=|F|$. Define
\begin{align*}
A_k := A \cup \{e_1,\dots,e_k\}
\end{align*}
for each integer $k$ with $0 \le k \le m$. Thus $A_0=A$ and $A_m=A \cup F$.
Fix $k$ with $1 \le k \le m$. We apply the submodularity axiom to the two subsets $A_{k-1}$ and $\{e_k\}$. This gives
\begin{align*}
r(A_{k-1}\cup \{e_k\})+r(A_{k-1}\cap \{e_k\}) \le r(A_{k-1})+r(\{e_k\}).
\end{align*}
By definition, $A_{k-1}\cup \{e_k\}=A_k$. Also, because the elements $e_1,\dots,e_m$ are distinct and $F \subset E \setminus A$, the element $e_k$ is not in $A_{k-1}$. Therefore $A_{k-1}\cap \{e_k\}=\varnothing$. Substituting these facts gives
\begin{align*}
r(A_k)+r(\varnothing) \le r(A_{k-1})+r(\{e_k\}).
\end{align*}
The first rank axiom gives $r(\varnothing)\ge 0$, and the second rank axiom gives $r(\{e_k\})\le |\{e_k\}|=1$. Hence
\begin{align*}
r(A_k) \le r(A_{k-1})+1.
\end{align*}
Now we sum this one-element estimate along the chain
\begin{align*}
A=A_0 \subset A_1 \subset \cdots \subset A_m=A \cup F.
\end{align*}
After $m$ additions, the total possible rank increase is at most $m=|F|$, so
\begin{align*}
r(A \cup F)=r(A_m)\le r(A_0)+m=r(A)+|F|.
\end{align*}
[/guided]
[/step]
[step:Prove heredity for subsets of independent sets]
Let $I \in \mathcal{I}$, and let $J \subset I$. We apply the previous step with $A=J$ and $F=I \setminus J$. Since $I=J \cup (I \setminus J)$ and $|I \setminus J|=|I|-|J|$, we obtain
\begin{align*}
r(I) \le r(J)+|I|-|J|.
\end{align*}
Because $I \in \mathcal{I}$, we have $r(I)=|I|$. Therefore
\begin{align*}
|I| \le r(J)+|I|-|J|.
\end{align*}
Subtracting $|I|-|J|$ gives $|J|\le r(J)$. The second rank axiom gives $r(J)\le |J|$, so $r(J)=|J|$. Hence $J \in \mathcal{I}$.
[/step]
[step:Use submodularity to force no rank growth if exchange fails]
Let $I,J \in \mathcal{I}$ with $|I|<|J|$. Suppose, for contradiction, that for every $e \in J \setminus I$ we have $I \cup \{e\}\notin \mathcal{I}$. Since $I \in \mathcal{I}$, $r(I)=|I|$. For each $e \in J \setminus I$, monotonicity gives
\begin{align*}
r(I)\le r(I \cup \{e\}).
\end{align*}
The one-element bound from the previous step gives
\begin{align*}
r(I \cup \{e\})\le r(I)+1.
\end{align*}
Because $I \cup \{e\}\notin \mathcal{I}$ and $|I \cup \{e\}|=|I|+1$, the value $r(I \cup \{e\})$ cannot equal $|I|+1$. Since $r$ takes values in $\mathbb N \cup \{0\}$, the inequalities $r(I)\le r(I \cup \{e\})\le r(I)+1$ and $r(I)=|I|$ leave only the integer value $r(I)$. Hence
\begin{align*}
r(I \cup \{e\})=r(I)
\end{align*}
for every $e \in J \setminus I$.
Write $J \setminus I=\{e_1,\dots,e_m\}$, where $m=|J \setminus I|$, and define $I_k := I \cup \{e_1,\dots,e_k\}$ for $0 \le k \le m$. We prove by induction that $r(I_k)=r(I)$ for every $k$. The case $k=0$ is immediate. If $r(I_{k-1})=r(I)$, then submodularity applied to $I_{k-1}$ and $I \cup \{e_k\}$ gives
\begin{align*}
r(I_k)+r(I_{k-1}\cap (I \cup \{e_k\})) \le r(I_{k-1})+r(I \cup \{e_k\}).
\end{align*}
Since $e_k\notin I_{k-1}$, we have $I_{k-1}\cap (I \cup \{e_k\})=I$. Hence
\begin{align*}
r(I_k)+r(I) \le r(I_{k-1})+r(I \cup \{e_k\})=r(I)+r(I).
\end{align*}
Thus $r(I_k)\le r(I)$. Monotonicity gives $r(I)\le r(I_k)$ because $I\subset I_k$, so $r(I_k)=r(I)$. By induction,
\begin{align*}
r(I \cup J)=r(I_m)=r(I).
\end{align*}
[/step]
[step:Derive the exchange axiom and conclude that $\mathcal{I}$ is a matroid]
Since $J \subset I \cup J$, monotonicity gives
\begin{align*}
r(J)\le r(I \cup J).
\end{align*}
Using $J \in \mathcal{I}$, the previous step, and $I \in \mathcal{I}$, we obtain
\begin{align*}
|J|=r(J)\le r(I \cup J)=r(I)=|I|.
\end{align*}
This contradicts the hypothesis $|I|<|J|$. Therefore there exists an element $e \in J \setminus I$ such that $I \cup \{e\}\in \mathcal{I}$.
We have proved that $\varnothing \in \mathcal{I}$, that $\mathcal{I}$ is closed under taking subsets, and that $\mathcal{I}$ satisfies the exchange axiom. Hence $\mathcal{I}$ is the collection of independent sets of a matroid on $E$.
[/step]
