In discussing this answer, I noted that while the statement:

Any vector space has a basis

is equivalent to the axiom of choice, I wondered if the statement that:

Any vector space either has a finite basis or an infinite set of linear independent vectors

was weaker than the axiom of choice. It feels weaker - it feels like you can inductively define a countably infinite set of linearly independent vectors without full choice, but I'm not sure if that is possible with ZF alone, or requires all of the Axiom of Choice, or is weaker but requires some form of choice.

  • $\begingroup$ I would be interested in hearing an answer, since I "have a feeling" that any weak form of choice should be enough to prove the statement you're after, but I am not sure about ZF alone. I somehow remember hearing once that if I have a set $X$ and a function $f: X \rightarrow X$, then one needs choice to prove that there exists a sequence $(x, f(x), f^{2}(x), \ldots)$... Since then I thought that maybe choice also plays a "technical" role in establishing even simple statements in ZFC, a role that could also be played by many of its weak forms. I'd be glad to hear expert opinion. $\endgroup$ Feb 11, 2013 at 19:54
  • 2
    $\begingroup$ @PiotrPstragowski Are you sure about the $(x,f(x),\ldots)$ statement? I would have thought that chosing a single $x$ is allowed and that then the sequence can be defined by recursion?! $\endgroup$ Feb 11, 2013 at 19:57
  • 1
    $\begingroup$ @PiotrPstragowski: That's not right. If the function is given then the set is definable by recursion. The existence of the function is often the problem. $\endgroup$
    – Asaf Karagila
    Feb 11, 2013 at 20:03
  • 1
    $\begingroup$ @PiotrPstragowski I think you are confusing the case of functions with "entire relations," as used by Dependent Choice: en.wikipedia.org/wiki/Axiom_of_dependent_choice $\endgroup$ Feb 11, 2013 at 20:09
  • 1
    $\begingroup$ @PiotrPstragowski: Yes. No one said that the sequence is one-to-one. Definable by recursion I mean exactly that the map $n\mapsto f^n(x)$ can be computed by recursion. And ZF proves that in this case we can really have this sequence. But if the sequence is one-to-one then there is $f$ which generates this same sequence and is injective but not surjective. Such $f$ might be hard to come by without the axiom of choice. $\endgroup$
    – Asaf Karagila
    Feb 11, 2013 at 20:15

1 Answer 1


Yes. The axiom of choice is needed in order to show that every vector space which is not finitely generated contains an infinite linearly independent subset.

The original consistency proof due to Lauchli (1962) was to construct a model in which there is a vector space that is not spanned by any finite set, but every proper subspace is finite.

Namely every collection of linearly independent vectors is finite.

If you have the axiom of dependent choice then you can actually perform the induction which you suggest and have a countably infinite set of independent vectors. But this is quite far from the full axiom of choice.

If one tries real hard, one can get away with just countable choice (which is strictly weaker than dependent choice). The argument is as follows:

Let $\cal A_n$ be the collection of all sets of linearly independent of size $n$, since the space is not finitely generated $\cal A_n$ is non-empty for all $n\neq 0$. Let $A_n\in\cal A_n$ be some chosen set. Again using countable choice let $A$ be the union of the $A_n$'s, and $A$ is countable so we can write it as $\{a_n\mid n\in\omega\}$.

Pick $v_0=a_0$, and proceed by induction to define $v_{n+1}$ to be $a_k$ whose index is the least $k$ such that $a_k$ not in the span of $\{v_0,\ldots, v_n\}$. This $a_k$ exists because $A_{n+1}$ spans a vector space of dimension $n+1$ so it cannot be a subset of $\operatorname{span}\{v_0,\ldots,v_n\}$.

The set $\{v_n\mid n\in\omega\}$ is linearly independent, which follows from the choice of the $v_n$'s.

Interestingly, Lauchli's example was of a space that every endomorphism is a scalar multiplication and as the above indicates this construction also contradicted $\mathsf{DC}$. In my masters thesis I showed that you can have $\mathsf{DC}_\kappa$ and still have a vector space which has no endomorphisms except scalar multiplication - even if it has relatively large subspaces.

  • $\begingroup$ So you are saying it requires full choice, or just saying that it is not provable with ZF alone? $\endgroup$ Feb 11, 2013 at 19:59
  • 1
    $\begingroup$ @Thomas: It's not provable, and it requires Dependent Choice (although it might be doable with countable choice, I'm not sure). $\endgroup$
    – Asaf Karagila
    Feb 11, 2013 at 20:04
  • $\begingroup$ Excellent, thanks! $\endgroup$ Feb 11, 2013 at 20:05
  • $\begingroup$ @Thomas: Yes, countable choice is enough (although I don't recall seeing this in the literature it might have been proved before, probably by one of the many people that worked on vector spaces and choice). $\endgroup$
    – Asaf Karagila
    Feb 17, 2013 at 20:57
  • 1
    $\begingroup$ "sets of linearly independent of size $n$" $\:\mapsto\:$ "tuples of $n$ linearly independent vectors" $\hspace{1.46 in}$ $\endgroup$
    – user57159
    Sep 24, 2013 at 5:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .