Proving replacement theorem?

Solution 1:

I'm assuming you're working through the proof in Friedberg et al. as its very similar. I'd really encourage you to double check what you've written because there are many typos above and probably isn't coherent enough for someone without a copy of the text.

The proof in the book says to start with m=0. In that case L=$\varnothing$, the empty set.

Okay, and I hope you realize that this also proves the inequality $m \leq n$ for the base case.

Let's assume this theorem is true for some integer m $\ge$ 0.

Let L = ${v_1, v_2, .... v_m+1}$ and define it as a linearly independent subset of V consisting of m+1 vectors.

So we're going to use induction on $m$ to prove the theorem. Also, it should be $L = \{v_1, \ldots, v_{m+1} \}$.

Since any subset of a linearly independent set is linearly independent as well ($S_1 \subseteq S_2 \subseteq V$), then {$v_1, v_2, .... v_m$} is linearly independent also.

That's correct. I'll call this set $L'$.

It then says to use the induction hypothesis to say that m$\le$n. Well, ok, but that seems sort of pulled out of nowhere to me. The next step is to say that there is therefore another subset, {$u_1, u_2, .... un_m$} of G s.t. {$v_1, v_2, .... v_m$} $\cup$ {$u_1, u_2, .... u_{n-m}$} generates V.

It isn't pulled out of nowhere because it follows from the induction hypothesis. As we have assumed it for some $m \geq 0$, we can apply the theorem to $\{v_1, \ldots, v_m\}$ which gives us the inequality $m \leq n$ and the set $H' = \{u_1, \ldots, u_{n-m}\} \subset G$ such that $L' \cup H'$ generates $V$.

That being the case there are scalars $a_1, a_2, .... a_m$ and $b_1, b_2, .... b_{n-m}$ which you can multiply by the vectors $v_i$ and $u_i$. You can then add th two sets of vectors, yielding $$a_1 v_1 + a_2v_2 + ... + a_mv_m + b_1u_1 + b_2u_2 + ... b_{n-m}u_{n-m} = v_{m+1} \tag{*}$$

We can do this as $L' \cup H'$ generates $V$.

At this point I am not sure I understand things. Because we are assuming n-m>0 -- otherwise $v_{m+1}$ is linearly dependent. But then it says not only is n>m but n>m+1, and that is where I am losing the plot to get to the next step.

What follows is this:

Note that $n - m > 0$, lest $v_{m +1}$ is a linear combination of $v_1, \ldots, v_m$ which by Theorem 1.7 (pg 39) contradicts the assumption that $L$ is linearly independent.

Do you understand why it must be $n - m >0$? Well if we had $n - m = 0$ then $H' = \emptyset$ and this would mean that $(\text{*})$ is only composed of vectors of $L'$ and therefore, $L' \cup \{v_{m+1}\} = L$ would be linearly dependent as $v_{m+1} \in \operatorname{span}(L')$, but that would be a contradiction.

Hence $n > m$; that is, $n \geq m +1$.

Why? Because another way of expressing $n > m$, as $n$ and $m$ are integers, is $n \geq m +1$. That's all there is to it.

Moreover, some $b_i$, say $b_1$ is nonzero, for otherwise we obtain the same contradiction. Solving $(\text{*})$ for $u_1$ gives

$$u_1 = (-b_1^{-1}a_1)v_1 + \cdots + (-b_1^{-1}am)v_m + (-b_1)v_{m + 1} + (-b_1^{-1}b_2)u_2 + \cdots + (-b_1^{-1}b_{n-m})u_{n-m} $$

Of course. If $b_i$ were all zero in $(\text{*})$ it would again only be composed of vectors of $L'$ and we know that that can't be the case for the same reason as above.

Let $H = \{u_2, \ldots, u_{n-m}\}$. Then $u_1 \in \operatorname{span}(L \cup H)$ and because $v_1, \ldots, v_m,u_2,\ldots,u_{n-m}$ are clearly in $\operatorname{span}(L \cup H)$, it follows that

$$L' \cup H' = \{v_1, \ldots, v_m, u_1, \ldots, u_{n-m}\} \subseteq \operatorname{span}(L \cup H).$$

This should be clear.

Because $L' \cup H'$ generates $V$, Theorem 1.5 (pg 30) implies that $\operatorname{span}(L \cup H)$ generators $V$.

To see why you can apply Theorem 1.5 you must remember that if $S \subseteq V$ then $\operatorname{span}(S)$ is a subspace of $V$ and therefore, by Theorem 1.5, if $W \subseteq \operatorname{span}(S)$ then $\operatorname{span}(W) \subseteq \operatorname{span}(S)$. So we have that $V = \operatorname{span}(L' \cup H') \subseteq \operatorname{span}(L \cup H)$ and since obviously, $\operatorname{span}(L \cup H) \subseteq V$ we have $\operatorname{span}(L \cup H) = V$.