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 $𝒮$ be the collection of all linearly independent supersets of $A$. First, $𝒮$ is non-empty since $A\in 𝒮$. In addition, if $A_1\subseteq A_2\subseteq \mathrm{\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, $𝒮$ has a maximal element $B$. Let $W=\mathrm{span}(B)$. If $W\ne V$, pick $b\in V-W$. If $0=rb+r_1{b}_1+\mathrm{\cdots }+r_n{b}_n$, where $b_i\in B$, then $-rb=r_1{b}_1+\mathrm{\cdots }+r_n{b}_n$, so that $-rb\in \mathrm{span}(B)=W$. But $b\notin W$, so $b\ne 0$, which implies $r=0$. Consequently $r_1=\mathrm{\cdots }=r_n=0$ since $B$ is linearly independent. As a result, $B\cup \{b\}$ is a linearly independent superset of $B$ in $𝒮$, contradicting the maximality of $B$ in $𝒮$.∎

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 $𝒮$ be the collection of all linearly independent subsets of $A$. $𝒮$ is non-empty as $\mathrm{\varnothing }\in 𝒮$. Let $A_1\subseteq A_2\subseteq \mathrm{\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, $𝒮$ has a maximal element $B$. In other words, $B$ is a linearly independent subset $A$. Let $W=\mathrm{span}(B)$. Suppose $W\ne 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 $𝒮$. Therefore, $B$ spans $V$ and thus a basis for $V$.∎

Corollary 1.

Every vector space has a basis.

Proof.

Either take $\mathrm{\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.