6
$\begingroup$

I wonder if the proof of the following statement requires the axiom of choice:

(Characterization of basis in terms of universal property) Let $V$ be a vector space, and let $S$ be a non-empty subset of $U$. Show that $S$ is a basis for $V$ if and only if for every vector space $W$ and every function $f : S → W$ , there exists a unique linear transformation $\tilde{f} : V → W$ such that $\tilde{f}(x) = f(x)$ for all $x \in S$.

The proof of the 'if' direction given in this answer certainly uses the axiom of choice, specifically this part:

On the other hand, suppose $E$ is linearly independent but not spanning. $\require{color} \colorbox{yellow}{Extend $E$ to a basis $E'$}$, with $x\in E'\setminus E$. Any $f:E\to Y$ extends to distinct functions $f_0,f_1:E'\to Y$ defined by $f_0(e)=f_1(e)=f(e)$ for $e\in E$, $f_0(e)=f_1(e)=0$ for $e\in E'\setminus (E\cup\{x\})$, and $f_0(x)=0$, $f_1(x)=1$. Any linear extension of either $f_1$ or of $f_2$ will be a linear extension of $f$. By the forward direction you know that each $f_1$ and $f_2$ have linear extensions. Since $f_1\ne f_2$, these will be distinct linear extensions of $f$.

I don't see any way to circumvent it. However, there is an obvious argument using Yoneda lemma that seemingly does not use the axiom of choice:

Let $F,G: \operatorname{Set}\rightleftarrows \operatorname{Vec}_k$ be the free-forgetful adjunction.The universal property implies that $\operatorname{Set}(S,G(W))\cong \operatorname{Vec}_k(V,W)$ for every vector space $W$ naturally in $W$ (naturally follows from uniqueness of $\tilde{f}$). On the other hand, $\operatorname{Set}(S,G(W))\cong \operatorname{Vec}_k(F(S),W)$. Thus, the representable functors $\operatorname{Vec}_k(V,-)$ and $\operatorname{Vec}_k(F(S),-)$ are naturally isomorphic and hence $V\cong F(S)$ by a corollary of Yoneda lemma and it follows that $S$ is a basis of $V$.

I would like to know whether the proof of the statement requires axiom of choice and if yes, when does the above argument uses the axiom of choice, and if no, how to modify the first proof to get around it.

$\endgroup$
6
  • $\begingroup$ I think your question hinges on whether $V\cong F(S)$ implies that $S$ is a basis of $V$. $\endgroup$ Feb 7 at 7:55
  • $\begingroup$ I would even say, it hinges on whether $S$ is a basis of $F(S)$. But I think that is pretty clear by construction. $\endgroup$ Feb 7 at 8:06
  • 1
    $\begingroup$ You are correct that the Yoneda argument is totally constructive. To show more explicitly (without category theory) that $S$ is spanning, consider the inclusion map $S \to span(S)$ and extend this to a map $f : V \to span(S)$; then $f : V \to V$ is linear and $f|_S$ is the inclusion, so $f$ is the identity and $span(S) = V$. $\endgroup$ Feb 7 at 8:17
  • 1
    $\begingroup$ @MarcvanLeewen I am simply using the fact that $span(S) \subseteq V$, so therefore any function $V \to span(S)$ is automatically also a function $V \to V$. I am not presupposing that $span(S) = V$. There is nothing wrong with rephrasing what I have done as composition with the inclusion map, as you did in your answer, but it is not necessary for the argument to be correct. Technically, you did the same thing I did when you said that $p : V \to W$ should extend the identity on $S$ - it should extend the inclusion $S \to span(S)$, which you identified with the identity $S \to S$. $\endgroup$ Feb 7 at 9:30
  • 1
    $\begingroup$ @MarkSaving Yes you are right about me using inclusion implicitly too, it is hard to always be completely correct in formulation, although I do try. (And by the way I now realise your comment predates my answer, though I did not read it while I was writing.) But I think in this context of direct comparison between morphisms (like your extended $f$ and the identity) it is good to consider the codomain to be part of what a map is, especially since it is vital for the existence of $f$ that is is constructed as a map to $\operatorname{Span}(S)$, not to $V$. I'll correct my answer; thank you. $\endgroup$ Feb 7 at 9:38

2 Answers 2

6
$\begingroup$

If $S$ is not a basis, it is either not linearly independent or not spanning.

In the first case, pick some finite counterexample with $n$ vectors, and map them to the standard basis of $F^n$, where $F$ is your field, and everything else goes to $0$. Easily, there is no linear extension of this map, not even to $\operatorname{span}(S)$.

If $S$ is not spanning, simply consider the function into $V/\operatorname{span}(S)$, mapping any element of $S$ to $0$. Since we're not spanning, we can map everything into $0$, or just take the obvious quotient map.

$\endgroup$
5
  • 1
    $\begingroup$ Sorry, prepositions are very confusing precoffee. Also postcofffee, if I'm being honest. $\endgroup$
    – Asaf Karagila
    Feb 7 at 8:32
  • 2
    $\begingroup$ I think there is something to learn here: the initial proof used the axiom of choice to say that if we have a subspace $W\subset V$ then it has a supplementary $U$ so we can define a linear map on $V$ by giving it a behaviour on $W$ and on $U$. But if you only need the much weaker fact that you can have a map trivial on $W$ and non-trivial somewhere else, then the quotient map $V\to V/W$ will do that canonically. $\endgroup$ Feb 7 at 8:37
  • 1
    $\begingroup$ Yes, that is a common thing when studying vector spaces without AC. But you also see this kind of thinking elsewhere, often, so I guess the real lessons here are lateral thinking, and better utilizing of the "every" quantifier. $\endgroup$
    – Asaf Karagila
    Feb 7 at 8:41
  • $\begingroup$ Just to be sure I understand the argument in the second part: you say that if $S$ is not spanning there exists $v\in V\setminus\operatorname{span}(S)$, and therefore a nonzero element $v+\operatorname{span}(S)$ in the quotient, and since the images of $v$ under the two maps to the quotient are zero respectively that nonzero class, that gives a contradiction. $\endgroup$ Feb 7 at 8:56
  • $\begingroup$ @Marc: Correct. Since you can extend the $0$ map in two different ways, it's not unique. $\endgroup$
    – Asaf Karagila
    Feb 7 at 9:08
3
$\begingroup$

The following seems to be a way to complete the "if" direction without extending bases. Suppose $S$ is a set with the given property in terms of linear maps. Let $W=\operatorname{Span(S)}$, a subspace of $V$, then let $p:V\to W$ be the unique map (whose existence is granted by the hypothesis) that extends the inclusion on $S\hookrightarrow W$, and let $\iota:W\hookrightarrow V$ be the inclusion map. Then $\mathbf1_V=\iota\circ p$ since both are linear maps $V\to V$ that coincide on $S$ (I'm using the uniqueness part of the hypothesis here). But then for every $v\in V$ one has $v=\iota(p(v))$ showing that $v\in W$, so that $V=W$.

$\endgroup$
5
  • 1
    $\begingroup$ This is full-on choice. The kernel of this "unique map" is a complement subspace. Their existence is equivalent to AC. $\endgroup$
    – Asaf Karagila
    Feb 7 at 8:42
  • $\begingroup$ @AsafKaragila can you explain that more clearly? I use the unique map $p$, provided by the supposed universal property applied to the embedding $S\hookrightarrow W$; that does not appeal to choice in any way. I am not implying every subspace has a complement, but a subspace spanned by a set with the mentioned property apparently does. $\endgroup$ Feb 7 at 8:53
  • $\begingroup$ What is definition of $p$, then? What happens to all the vectors outside of $W$? Where do they go? (I didn't downvote, by the way.) $\endgroup$
    – Asaf Karagila
    Feb 7 at 9:08
  • $\begingroup$ I am assuming, for the "if" direction: "for every vector space $W$ and every function $f:S\to W$ there exists a unique linear transformation $\tilde f:V\to W$ such that $\tilde f(x)=f(x)$ for all $x\in S$" (quoted from OP). Apply this with $W=\operatorname{span}(S)$ (a valid vector space) and $f:S\to W$ mapping every $s\in S$ to itself as element (obviously) of $W$ an call $p$ the resulting linear map $\tilde f$. So what happens to all the vectors outside of $W$ is for the hypothesis to decide; obviously I am arguing that the only way it can be true is if there are no such vectors. $\endgroup$ Feb 7 at 9:20
  • $\begingroup$ Ah, I see! Thanks for clarifying. It's still quite early in the day for me to do mental gymnastics! :-) (I am going to leave the comments for the time being, just to make sure that the issue is clear to those that follow my footsteps.) $\endgroup$
    – Asaf Karagila
    Feb 7 at 9:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.