Let $G = (V, E)$ be an undirected graph. For all $k \in \mathbb{N}$ set $M_k(G) = (E, S)$ where $S = \{ A \subseteq E | \exists M, F \subseteq E$ such that $ |M| \leq k, F$ is a forest and $ A = F \cup M \}$. Prove that $M_k(G)$ is a matroid for all $k \geq 0$.
My partial solution:
$M_0(G) = (E, S), F \in S$ if and only if $F$ forest.
$\{\emptyset\}$ is in $S$. No cycles, therefore a forest.
Downward closed: $S$ is downward closed, as every subgraph of a forest is also a forest and therefore also independent (i.e in $S$).
The exchange property: Let $F_1, F_2 \in S$ be forests where $|F_1| = |F_2| + 1$. The number of vertices is given by $|V| = |F_1| + k_1 = |F_2| + k_2$, where $k_i$ is the number of trees in the forest. Therefore, $k_1 = k_2 - 1$, which means that there must exist an edge $F_1 \setminus F_2$ which connects two trees in $F_1$.
Does axiom still hold for $k > 0$? If yes, how can I prove it?
You mean that $\varnothing\in S$, not that $\{\varnothing\}\in S$: $\{\varnothing\}$ isn’t a subset of $E$. In your proof of the exchange property for $M_0(G)$ you can’t assume that the vertices of $F_1$ and $F_2$ are all of $V$. All you can assume is that $|F_1|=|F_2|+1$.
Let the components of $F_2$ be $T_1,\ldots,T_m$, with $n_1,\ldots,n_m$ vertices, respectively. Then $T_k$ has $n_k-1$ edges for $k=1,\ldots,m$, and any forest on the same vertices has at most $n_k-1$ edges. Suppose that each edge of $F_1$ has both of its ends in the same component of $F_2$, and for $k=1,\ldots,m$ let $H_k$ be the set of edges of $F_1$ whose ends are in $T_k$. Then $H_k$ is a forest on the vertices of $T_k$, so $|H_k|\le n_k-1$. But this means that
$$|F_1|=\sum_{k=1}^m|H_k|\le\sum_{k=1}^m(n_k-1)=\sum_{k=1}^m|T_k|=|F_2|\;,$$
which is impossible. Thus, either $F_1$ contains an edge that joins two components of $F_1$, or $F_1$ contains an edge that has only one end in the forest $F_2$. In either case that edge can be added to $F_2$ to produce a larger forest, so $M_0(G)$ satisfies the exchange property.
Now let’s look at $M_k(G)$ for arbitrary $k$. Suppose that $A_1,A_2\in S$ with $|A_1|=|A_2|+1$. For $i=1,2$ let $A_i=F_i\cup M_i$, where $F_i,M_i\subseteq E$, $|M_i|\le k$, and $F_i$ is a forest. We may also assume that $M_i\cap F_i=\varnothing$. (Why?) Finally, we may assume that if we add any edge in $M_i$ to $F_i$, the resulting graph is no longer a forest, i.e., that $F_i$ is a maximal forest in $A_i$. (Why?)
As before, if $F_1$ contains an edge $e$ that joins two components of $F_2$ or that has only one end in $F_2$, we can add that edge to $F_2$ to get a bigger forest, $F_2\cup\{E\}$. Moreover, since $F_2$ is a maximal forest in $A_2$, $e$ cannot already be in $M_2$, so $e\notin A_2$, and $|A_2\cup\{e\}|=|A_2|+1$. Finally, $$A_2\cup\{e\}=M_2\cup(F_2\cup\{e\})\;,$$ where $|M_2|\le k$ and $F_2\cup\{e\}$ is a forest, so $A_2\cup\{e\}\in S$.
The other possibility is that every edge of $F_1$ has both ends in the same component of $F_2$. We saw above that this implies that $|F_1|\le|F_2|$, which means that $|M_1|>|M_2|$. Thus, $|M_2|<k$, and we have room to add an edge to $M_2$ without breaking the size limit. Let $e$ be any edge of $A_1$ that isn’t in $A_2$; we know that there must be one, since $|A_1|>|A_2|$. Then $|M_2\cup\{e\}|=|M_2|+2\le k$, so $|(M_2\cup\{e\})\cup F_2|>|A_2|$ and $(M_2\cup\{e\})\cup F_2\in S$. Thus, $M_k(G)$ satisfies the exchange property.