# Mathematics Prelims

## June 10, 2009

### Every Vector Space Has a Basis

Filed under: Algebra,Linear Algebra — cjohnson @ 8:12 pm
Tags: , , , ,

I just realized a few hours ago that the algebra prelim is six weeks from today, and went into “that’s way closer than I realized”-freakout mode.  Given that, I’d like to start posting on algebra.  In particular, for the next little bit I want to post on linear algebra since that’s what I’ve been studying the most recently.  A nice place to start might be showing that every vector space has a basis, since this is a fact that I remember being used throughout my linear algebra classes but don’t seem to remember ever being shown (presumably to avoid talking about the axiom of choice and Zorn’s lemma).  This proof is adopted from the one that appears in an appendix to Larry Grove’s Algebra.

Recall that Zorn’s lemma says that in a partially ordered set in which every chain has an upper bound, there exists a maximal element.  We will use this to show that there must be a maximal linearly independent subset in a vector space, and argue that this set is a basis.

Let $V$ be any vector space and define the set $L$ as the collection of all linearly independent subsets of $V$.

$\displaystyle L := \{ S \subset V : S \text{ is a linearly independent set } \}$

Note that as $L$ is a collection of sets, it is partially ordered by $\subseteq$.  Now let $C$ be any chain in $L$.  Each element of this chain, being a linearly independent set of vectors in $V$, forms the basis for some subspace of $V$.  Furthermore, if $C_1$ and $C_2$ are in the chain with $C_1 \subseteq C_2$, the subspace of $V$ generated by $C_1$ is contained in the subspace generated by $C_2$.

Define a set $U$ as follows:

$\displaystyle U := \bigcup_{S \in C} S$

Defining $U$ in this way, we have a collection of vectors in $V$ in which every subset is linearly independent, and so $U \in L$.  This means that $C$ has an upper bound.  Since our choice of the chain $C$ was arbitrary, this means every chain in $L$ has an upper bound.  By Zorn’s lemma this means $L$ has a maximal set.  Let $M$ be such a maximal set (recall Zorn’s lemma says that $L$ will have at least one maximal set, and not that the maximal set is unique).

Since $M \in L$, $M$ is a linearly independent set of vectors in $V$.  This means that the span of $M$ is some subspace of $V$.  Suppose this subspace is proper.  Then there exists some vector, call it $v$, which can not be represented as a linear combination of the elements in $M$.  This implies that $M \cup \{v\}$ is a linearly independent set.  However, as $M \subsetneq (M \cup \{v\})$ this contradicts the maximality of $M$.  We must conclude that $V$ equals the span of $M$, and so $M$ forms a basis for $V$.