# Zorn’s lemma and bases for vector spaces

In this entry, we illustrate how Zorn’s lemma can be applied in proving the existence of a basis for a vector space. Let $V$ be a vector space over a field $k$.

###### Proposition 1.

Every linearly independent subset of $V$ can be extended to a basis for $V$.

This has already been proved in this entry (http://planetmath.org/EveryVectorSpaceHasABasis). We reprove it here for completion.

###### Proof.

Let $A$ be a linearly independent subset of $V$. Let $\mathcal{S}$ be the collection of all linearly independent supersets of $A$. First, $\mathcal{S}$ is non-empty since $A\in\mathcal{S}$. In addition, if $A_{1}\subseteq A_{2}\subseteq\cdots$ is a chain of linearly independent supersets of $A$, then their union is again a linearly independent superset of $A$ (for a proof of this, see here (http://planetmath.org/PropertiesOfLinearIndependence)). So by Zorn’s Lemma, $\mathcal{S}$ has a maximal element $B$. Let $W=\operatorname{span}(B)$. If $W\neq V$, pick $b\in V-W$. If $0=rb+r_{1}b_{1}+\cdots+r_{n}b_{n}$, where $b_{i}\in B$, then $-rb=r_{1}b_{1}+\cdots+r_{n}b_{n}$, so that $-rb\in\operatorname{span}(B)=W$. But $b\notin W$, so $b\neq 0$, which implies $r=0$. Consequently $r_{1}=\cdots=r_{n}=0$ since $B$ is linearly independent. As a result, $B\cup\{b\}$ is a linearly independent superset of $B$ in $\mathcal{S}$, contradicting the maximality of $B$ in $\mathcal{S}$. ∎

###### Proposition 2.

Every spanning set of $V$ has a subset that is a basis for $V$.

###### Proof.

Let $A$ be a spanning set of $V$. Let $\mathcal{S}$ be the collection of all linearly independent subsets of $A$. $\mathcal{S}$ is non-empty as $\varnothing\in\mathcal{S}$. Let $A_{1}\subseteq A_{2}\subseteq\cdots$ be a chain of linearly independent subsets of $A$. Then the union of these sets is again a linearly independent subset of $A$. Therefore, by Zorn’s lemma, $\mathcal{S}$ has a maximal element $B$. In other words, $B$ is a linearly independent subset $A$. Let $W=\operatorname{span}(B)$. Suppose $W\neq V$. Since $A$ spans $V$, there is an element $b\in A$ not in $W$ (for otherwise the span of $A$ must lie in $W$, which would imply $W=V$). Then, using the same argument as in the previous proposition, $B\cup\{b\}$ is linearly independent, which contradicts the maximality of $B$ in $\mathcal{S}$. Therefore, $B$ spans $V$ and thus a basis for $V$. ∎

###### Corollary 1.

Every vector space has a basis.

###### Proof.

Either take $\varnothing$ to be the linearly independent subset of $V$ and apply proposition 1, or take $V$ to be the spanning subset of $V$ and apply proposition 2. ∎

Remark. The two propositions above can be combined into one: If $A\subseteq C$ are two subsets of a vector space $V$ such that $A$ is linearly independent and $C$ spans $V$, then there exists a basis $B$ for $V$, with $A\subseteq B\subseteq C$. The proof again relies on Zorn’s Lemma and is left to the reader to try.

Title Zorn’s lemma and bases for vector spaces ZornsLemmaAndBasesForVectorSpaces 2013-03-22 18:06:49 2013-03-22 18:06:49 CWoo (3771) CWoo (3771) 9 CWoo (3771) Result msc 16D40 msc 13C05 msc 15A03