Section 1.6: Theorem 1.9

This is the proof for theorem 1.9 from the book that doesn’t assume we know the replacement theorem (1.10) yet.

Proof: Let \(V\) be a vector space generated by a finite set \(S\). If \(S = \emptyset\) or \(S = \{0\}\), then \(V = \{0\}\) and \(\emptyset\) is a subset of \(S\) that is a basis for \(V\). Otherwise \(S\) has at least one non-zero vector \(u_1\). Let \(\beta = \{u_1\}\). We know \(\beta\) is linearly independent. Now, keep adding vectors from \(S\) to \(\beta\) while keeping \(\beta\) linearly independent. Since \(S\) is a finite set, then this process must end with a linearly independent set of vectors \(\{u_1, u_2, ..., u_k\}\). We have two cases

1. \(\beta = S\). This means that \(S\) is linearly independent. We know \(S\) is a generating set for \(V\) and so it is a basis for \(V\) and we are done.
2. \(\beta\) is a proper subset of \(S\) that is linearly independent by construction. Then to prove that \(\beta\) is a basis, we only need to show that \(\beta\) generates \(V\) or \(Span(\beta) = V\). Theorem 1.5 states that
   
   "The span of any subset \(S\) of \(V\) is a subspace of \(V\) that contains \(S\). (\(S \subseteq span(S)\)). Moreover, any subspace of \(V\) that contains \(S\) must also contain the span of \(S\)."
   
   Since \(\beta\) is a subset of \(V\), then \(Span(\beta)\) is a subspace and if we showed that \(Span(\beta)\) contains \(S\), then \(Span(\beta)\) must also contain \(Span(S)\) and we know that \(S\) generates \(V\). Therefore, it is sufficient here to show that \(S \subseteq Span(\beta)\). To do this, let \(v \in S\), we need to show that \(v \in Span(\beta)\). If \(v \in \beta\), then \(v \in Span(\beta)\) and we are done since. Otherwise, \(v \not\in \beta\). Therefore, \(\{v \cup \beta\}\) must be a linearly dependent set because of the way we constructed \(\beta\) (adding \(v\) would have turned the set into a linearly dependent set). From this, we know that \(v\) can be written as a linear combination of the elements of \(\beta\) which means that \(v \in span(\beta)\). Therefore, \(S \subseteq span(\beta)\) and so \(\beta\) generates \(V\) as we wanted to show. \(\blacksquare\)

References:

• Linear Algebra 5th Edition