Exercise 11.8

Proof. We show this by contradiction. Suppose that $A$ is independent and $v\in V$ does not belong to the span of $A$. Also let $B=A\cup \left\{v\right\}$ and suppose that $B$ is not independent. Then

for some nonzero coefficients ${\beta }_i$, where each $b_i$ is in $B$. Now, it must be that one of the $b_i$ vectors is $v$ and the rest in $A$ since otherwise they would all be in $A$ and then $A$ would not be independent. Hence this can be expressed as

for nonzero coefficients ${\alpha }_i$ and $\gamma$ and vectors $a_i\in A$. However clearly then we would have

so that $v$ is a linear combination of vectors in $A$ and hence is in the span of $A$. This is a contradiction so it must be that in fact $B=A\cup \left\{v\right\}$ is independent as desired. □

Proof. Let $A$ be the collection of all independent sets in $V$. We know that $⊊$ is a strict partial order on $A$. Now let $B$ be any subset of $A$ that is simply ordered by $⊊$. We claim that $\bigcup <!--\; FUNCTION\; APPLICATION\; -->B$ is an upper bound of $B$ that is in $A$. So first consider any $B\in B$ and any $b\in B$ so that clearly then $b\in \bigcup <!--\; FUNCTION\; APPLICATION\; -->B$. Hence $B\subset \bigcup <!--\; FUNCTION\; APPLICATION\; -->B$ since $b$ was arbitrary. Since $B\in B$ was arbitrary, this shows that $\bigcup <!--\; FUNCTION\; APPLICATION\; -->B$ is an upper bound of $B$ by $⊊$.

Next, we show that $\bigcup <!--\; FUNCTION\; APPLICATION\; -->B$ is also in $A$. To this end consider any finite set $B$ of elements of $\bigcup <!--\; FUNCTION\; APPLICATION\; -->B$ so that $B$ is a set of vectors in $V$. Now, for each $b\in B$ we have that $b\in \bigcup <!--\; FUNCTION\; APPLICATION\; -->B$ so that we can choose any set $B_b\in B$ where $b\in B_b$. Note that this does not require the axiom of choice since $B$ is finite. Then, since each $B_b$ is in $B$, which is simply ordered by $⊊$ and $\left\{B_b\mid b\in B\right\}$ is finite, it follows that it has a largest element $C$ so that $B_b\subset C$ for any $b\in B$. Hence $B\subset C$ since each $b\in B_b$ and $B_b\subset C$. Also $C\in A$ since $C\in B$ and $B\subset A$ so that $C$ is independent. Hence the only linear combination of the vectors in $B$ that is the zero vector must have all zero coefficients since they are all in the independent set $C$. Since $B$ was an arbitrary set of vectors in $\bigcup <!--\; FUNCTION\; APPLICATION\; -->B$, this shows that $\bigcup <!--\; FUNCTION\; APPLICATION\; -->B$ is independent and therefore in $A$.

Since $B$ was arbitrary simply ordered subset of $A$, it follows that every such subset has an upper bound in $A$. Thus by Zorn’s Lemma $A$ has a maximal element as desired. □

Proof. Again let $A$ be the collection of all independent sets in $V$, which we know has a maximal element $A$ from part (b). We claim that $A$ is a basis for $V$. Suppose to the contrary that it is not so that, since we know that $A$ is independent (since it is in $A$), there must be a vector $v\in V$ that is not in the span of $A$. Then by part (a) we have that $A\cup \left\{v\right\}$ is also independent and so in $A$. We also have that $v\notin A$ since otherwise, it would clearly be in the span of $A$. Hence $A⊊A\cup \left\{v\right\}$. However, this contradicts the fact that $A$ is a maximal element of $A$, so it must be that in fact, $A$ is a basis for $V$ as desired. □