# Is my proof that every Linearly Independent set in a vector space can be extended to a basis correct?

I've little experience with Zorn's lemma, and my class hasn't covered the material yet. However, the teacher has stated that the claim holds for infinite dimensional vector spaces, and he implies he wants us to use this fact on our homework. I was not satisfied with this. I felt we should justify this claim before using it.

$$\textbf{Proof:}$$

Let $$V$$ be a vector space over a field $$F$$. Let $$S\in V$$ be a linearly independent set. Consider the set $$\mathcal{S}=\{S'\subseteq V|S\subseteq S'\text{ and }S'\text{ is linearly independent.}\}.$$ This set is partially ordered by subset inclusion. Consider a chain in $$\mathcal{S}$$ $$S_1\subset S_2\subset...\subset S_i\subset...$$ which may or may not terminate. It follows that $$\{S_i\}$$ is bounded above by $$\bigcup S_i$$. We will show that $$\bigcup S_i$$ is a linearly independent set. If $$\bigcup S_i$$ were linearly dependent, then there exists $$v_1,...,v_n\in\bigcup S_i$$ such that $$a_1v_1+...+a_nv_n=0$$ has a non-trivial solution, that is $$v_1,...,v_n$$ are linearly dependent. Note that since $$v_j\in \bigcup S_i$$ it follows that there $$S_{i_j}$$ such that $$v_j\in S_{i_j}$$. Then $$v_1,...,v_n\in S_m$$ where $$m=\max(i_1,...,i_n)$$. This contradicts that $$S_m$$ is linearly independent, hence $$\bigcup S_i$$ is linearly independent, and belongs to $$\mathcal{S}$$. This shows that every totally ordered chain in $$\mathcal{S}$$ has an upper bound in $$\mathcal{S}$$, therefore by Zorn's Lemma $$\mathcal{S}$$ has a maximal element.

Let $$S^m\in\mathcal{S}$$ be maximal. Clearly $$S\subseteq S^m$$. If we can show $$S^m$$ is a spanning set, then since it is linearly independent ($$S^m\in\mathcal{S}$$) it will be a basis containing $$S$$ completing the proof.

Suppose that $$v\in V$$ such that $$v\not\in\text{Span}(S^m)$$. This happens if and only there exists no set of vectors $$v_1,...,v_n\in S^m$$ and scalars $$a_1,...,a_n,a\in F$$ not all $$0$$ such that $$a_1v_1+...+a_nv_n=-av.$$ This implies that for all $$v_1,...,v_n\in S^m$$ the equation $$a_1v_1+...+a_nv_n+av=0$$ has only the trivial solution, which happens if and only if $$S^m\cup\{v\}$$ is a linearly independent set. This is impossible, for $$S^m$$ is maximal, therefore by contradiction $$S^m$$ spans $$V$$.$$\blacksquare$$

• In order to apply Zorn's Lemma, you would need to find an upper bound of each chain in $\mathcal{S}$ where the upper bound is also in $\mathcal{S}$ - but certainly $V \notin \mathcal{S}$. – Daniel Schepler Oct 26 '18 at 21:58
• Yes, given a chain, you have to show there is an upper bound to the chain, not assume it. The. You can conclude there is a maximal element. – Thomas Andrews Oct 26 '18 at 21:59
• @Daniel. Thank you. I will try and find an upper bound in $\mathcal{S}$. Or at least arrive at a contradiction if there is not one. – Melody Oct 26 '18 at 22:00

The proof is good, apart from some minor details.

A chain in $$\mathcal{S}$$ is not necessarily of the form $$S_1\subset S_2\subset\dotsb$$. It is a subset $$\mathcal{T}$$ of $$\mathcal{S}$$ such that, for all $$T_1,T_2\in\mathcal{T}$$ either $$T_1\subset T_2$$ or $$T_2\subset T_1$$ ($$\subset$$ denoting nonstrict inclusion).

Two lemmas will be used.

Lemma 1. A subset $$S$$ of $$V$$ is linearly independent if and only if every finite subset of $$S$$ is linearly independent.

Proof. Essentially, this is the definition. □

Lemma 2. if $$S$$ is a linearly independent set in $$V$$ and $$v\notin\operatorname{span}(S)$$, then $$S\cup\{v\}$$ is linearly independent.

Proof. if a finite subset of $$S$$ is not linearly independent it must include $$v$$; so it is of the form $$\{v_1,\dots,v_n,v\}$$ and there are $$a_1,\dots,a_n,a$$ not all zero with $$a_1v_1+\dots+a_nv_n+av=0$$ Now $$a\ne0$$, because $$S$$ is linearly independent, so $$v=(-a^{-1})a_1v_1+\dots+(-a^{-1})a_nv_n$$ contradicting that $$v\notin\operatorname{span}(S)$$. □

Consider a chain $$\mathcal{T}$$ and let $$T=\bigcup\mathcal{T}$$. Then $$T$$ is linearly independent. Indeed, if $$v_1,\dots,v_n\in T$$, there is a member $$T_0$$ of $$\mathcal{T}$$ such that $$v_1,\dots,v_n\in T_0$$ (easy induction, fill in the details). In particular $$\{v_1,\dots,v_n\}$$ is linearly independent. Lemma 1 allows to conclude that $$T$$ is linearly independent.

Therefore, Zorn's lemma guarantees the existence of a maximal element $$\bar{T}\in\mathcal{S}$$.

The fact that $$\bar{T}$$ is a spanning set follows Lemma 2.

• I like your answer a lot. Thank you very much. You gave me just enough at the beginning to patch up my proof realizing my mistake with the definition of chain. I complete the proof differently than you did. I really like your proof. It's much more concise and streamlined. Gonna include the one I finished in my paper, as I want it to be as much my work as possible, but I really like yours. – Melody Oct 26 '18 at 23:32

There are a few small issues.

• To bound the chain, you cannot use $$V$$ since it is not a linearly independent set. What you need to use is $$\bigcup_j S_j$$, and you need to show that this union is linearly independent.

• The last part of your proof is the usual fact that a maximaly linearly independent set spans. The argument is fine, but I think you can take $$a=1$$.

• Umm, yes, you need to fix a base $S$. It’s right there in the question. – Thomas Andrews Oct 26 '18 at 22:00
• I didn't say that $S\subset S^m$. I said that $S\subseteq S^m$. This follows from $S^m\in\mathcal{S}$ and the definition of $\mathcal{S}$. The set you posted does work. I added it to the proof. I wish I was given the chance to come up with my own set though, as I did want the experience of trying to figure it out, but oh well. It works. My class, and our textbook defined linear independence in terms of any non-zero scalars. Which is why I took an arbitrary $a$. It is equivalent to setting $a=1$ by division, I just wanted it in the form of definition. Thank you for your help. – Melody Oct 26 '18 at 22:14
• No, it was not about the subset symbol. For many of us, a subset is a subset, you only specify "proper" if you need to. I deleted that part. – Martin Argerami Oct 26 '18 at 23:55