= Finite greedy basis extension and choice
For an explicit <basis extension> in $\mathbb R^2$, start with $A=\{u\}$, where $u=(1,1)$. Its <linear span> is the line $y=x$. Adding $w=(1,-1)$ preserves <linear independence>, because $w$ is outside that line, and gives a <basis>. Every <vector> has the finite <linear combination>
$$
(x,y)=\frac{x+y}{2}u+\frac{x-y}{2}w.
$$
The <vector> $2u=(2,2)$ cannot be added while preserving <linear independence>: it is already in the <linear span>. Many choices outside the line work, so maximality does not select a unique <basis>.
\Image[/zorn-finite-dimensional-basis-extension.png]
{title=Extending one independent vector to a basis of the real plane}
{description=Left: u spans only the blue line, and 2u is redundant. Right: adding w outside that line yields a basis spanning the entire plane. This finite-dimensional illustration is not a proof of basis existence in arbitrary dimension.}
For a <finite-dimensional vector space> with a supplied finite <spanning set>, a <greedy algorithm> scans the list, retaining each <vector> precisely when it is outside the <linear span> of those already retained. Starting with a <linearly independent> $A$, the same scan adjoins only the needed <vectors>. Retained <vectors> remain <linearly independent>, and every skipped <vector> is in the final <linear span>, so the result is a <basis> containing $A$. Finite reasoning needs no <axiom of choice>.
For an arbitrary <vector space>, this finite stopping argument is unavailable. Accepting <Zorn's lemma> asserts existence of a <maximal element> once every <chain in a partial order> has an <upper bound>; it supplies no general computational recipe. Over <ZF>, <Zorn's lemma>, the <axiom of choice> and the <well-ordering theorem> are equivalent. Particular infinite <vector spaces> can still have explicit <bases>, such as $1,x,x^2,\ldots$ for the <vector space of univariate polynomials> over a specified <field>; infinity alone does not force a nonconstructive argument.<How to use Zorn’s lemma by Timothy Gowers>[How to use Zorn’s lemma, “Further general remarks”, immediately after Example 1 continued: equivalence with choice and well-ordering]{ref}
Back to article page
