# Is my proof that every linearly independent set of E is a subset of a basis of E correct?

Asking this because I'm not sure how "mathematically valid" is the argument that I used in my demonstration. Please note that my question is not about how to prove the theorem, but about whether my demonstration is correct. If the proof is incorrect, is there any way to make it more "valid mathematically"? If it's correct, my question is: what can be done to improve it?

Theorem. Let $E$ be a finite vector space with dimension $N$. Every linearly independent set $X=\{v_1, ..., v_m\}$ of $E$ is a subset of a basis for $E$.

Proof.

Firstly, note that $m<N$. Due to the hypothesis, we know that $\exists v\in E-Span(\{v_1,...,v_m\})$. From here, there are two possibilities:
(A) $Span(\{v_1,...,v_m,v\})=E$
(B) There still exists another $\exists v\in E - Span(\{v_1, ..., v_m, v\})$

In either scenario, $\{v_1,...,v_m, v\}$ is linearly independent. If (A) is true, then we are done. In the case of (B), we repeat the process with $\{v_1,...,v_m,v\}$ instead of $\{v_1,...,v_m\}$ until we get (A).

(Part that I don't know whether it is necessary or not:)

We claim that the process described happens in a finite number of times. In fact, there's no way for it to happen more times than $N$ times. If the process were to be repeated, let's say $N+1$ times, then we would obtain a linearly independent set that has a cardinality greater than $\dim{E}$, which is absurd.

• For it is perfect. If fact, if I had had to proved the theorem I would do this. – Dog_69 May 16 '18 at 15:14
• You said $m<N$ but this was not given. Rather, $m>N$ is impossible and $m=N$ implies $X$ is basis. The other case, $m<N$, your proof is good. I think it is correct to consider the vector space $E\setminus\text{Span}(X)$. You are guaranteed this vector space has a basis, say $Y$, so that $X\cup Y$ is a basis for $E$. Then $X\subseteq X\cup Y$. – M. Nestor May 16 '18 at 15:21

## 1 Answer

It is correct, but you should never use the same symbol for two distinct objects. I'm talking about $v$ here.

There is a problem with your notation: you should have written $E\setminus\operatorname{Span}(\{e_1,\ldots,e_n\})$ instead of $E-\operatorname{Span}(\{e_1,\ldots,e_n\})$ (it is ambiguous).

Finally, it would be more elegant to express your proof as an inductive proof on $N-m$.

• May I ask more details on how to do the induction you described? – BroccoliFinancials May 16 '18 at 15:26
• If $N-m=0$, then $X$ is already a basis. Now, suppose that it is true that, for some $k\in\mathbb{Z}_+$, whenever $N-m=k$, then you can extend $X$ to a basis. Now, if $N-m=k+1$, you apply your method in order to prove that there is a vector $v$ such that $X'=X\cup\{v\}$ is linearly independent. But then $\#X'=\#X+1$ and therefore you can apply the induction hypothesis to $E$ and $X'$. So, you know that you can extend $X'$ to a basis $B$ of $E$ and $B$ will be an extension of $X$ too. – José Carlos Santos May 16 '18 at 15:31