Asaf Karagila
I don't have much choice...

Infinite dimensions and the axiom of choice

There are no comments on this post.

In a recent math.SE question, Thomas Andrews asked whether or not the existence of an infinite linearly independent set in a vector space which is not finitely generated requires the axiom of choice.

The answer is positive. It does require the axiom of choice. The counterexample is due to Läuchli who constructed a model in which there was a vector space which was not finitely generated, but every proper subspace is finitely generated. Given such vector space it is obvious that no infinite set can be linearly independent.

So, how much choice are we talking about here? Well, let's review the obvious approach:

Let \(V\) be a vector space which is not finitely generated, we will construct by induction an infinite linearly independent set. Let \(v_0\) be any arbitrary non-zero vector in \(V\).

Suppose \(v_k\) were chosen for \(k\lt n\), then pick \(v_n\) to be an arbitrary vector not in the span of \(\{v_0,\ldots,v_{n-1}\}\). We can pick such vector because \(V\) itself is not finitely generated so it cannot be equal to this span.

Clearly the set \(\{v_n\mid n\in\omega\}\) is linearly independent. Suppose that \(\sum_{i=1}^k\alpha_iv_{n_i}\) is zero then for \(n=\max\{n_i\mid i=1,\ldots,k\}\) we have that \(v_n\) was taken from the span of \(\{v_0,\ldots,v_{n-1}\}\) which is a contradiction to the choice of \(v_n\).

Okay, induction. So we're using \(\DC\) to produce this sort of set. And it makes sense too, every choice depends on the previous choices that we've made. If we had chosen a different \(v_0\) the choice of \(v_1\) would change. So it seems that perhaps \(\DC\) is required. Can we somehow get away with just countable choice (\(\AC_\omega\)), which is strictly weaker?

Well, to quote a recently elected U.S. president from his 2008 campaign "Yes we can!".

Theorem. Assume \(\AC_\omega\) holds, then every vector space which is not finitely generated has an infinite set of linearly independent vectors.

The proof itself is quite similar to the proof that there are no Dedekind-finite sets in the presence of \(\AC_\omega\). Which is not surprising because the usual argument for showing that an infinite set has a countably infinite subset is also a \(\DC\)-like argument, but we can get away with actually less.

Proof. Let \(V\) be a vector space which is not finitely generated. By induction we can see that for every non-zero \(n\in\omega\) there exists \(A_n\subseteq V\) which is a set of \(n\) vectors which are linearly independent. Using the axiom of countable choice we can choose for every non-zero \(n\) such \(A_n\).

Being lazy, we can take \(A=\{a_n\mid n\in\omega\}=\bigcup_{n=1}^\infty A_n\), as this is a countable union of finite sets and in the presence of \(\AC_\omega\) this is a countable set as well. Now we proceed with the same recursion as before:

Suppose that for \(k\lt n\), \(v_k\) was chosen from \(A\), let \(v_n\) be \(a_i\) such that \(i\) is the least for which \(a_i\notin\operatorname{span}\{v_0,\ldots,v_{n-1}\}\). Then by a similar argument to the one before, the resulting set is indeed infinite and linearly independent. \(\square\)

Okay, this much is great. But what about the converse? Besides, vector spaces are additional structure. If the axiom stating that every infinite set is Dedekind-infinite is strictly weaker than \(\AC_\omega\), what about the statement "Every vector space which is not finitely generated has a proper subspace which is not finitely generated"? Or perhaps "Every vector space which is not finitely generated has a countably infinite dimensional subspace"?

Well those are two distinct statements, and it's unclear whether or not they are equivalent. Let us abbreviate them as \(\newcommand{\Vinf}{\axiom{Vec_\infty}}\newcommand{\Vom}{\axiom{Vec_\omega}}\Vinf\) and \(\Vom\) respectively. It is obvious that \(\Vom\) implies \(\Vinf\), what about the other way around? So there are three questions here:

  1. Does \(\Vinf\) imply \(\Vom\)?
  2. What choice principles does \(\Vinf\) prove?
  3. What choice principles does \(\Vom\) prove?

It is clear that if we can show that the last two questions have different answers then the first question is answered negatively, and that if \(\Vinf\) can prove \(\AC_\omega\) then all three questions get answered because we know that \(\AC_\omega\implies\Vom\implies\Vinf\).

But what about the other implications? Well. So far I have no answer. But after meddling with this for a day or so, I will sign off with a conjecture:


  1. \(\AC_\omega\implies\Vom\implies\Vinf\) and none of the implications are reversible.
  2. \(\Vom\iff\text{Finite}=\text{Dedekind-finite}.\)
  3. \(\Vinf\iff\text{Every infinite set is the disjoint union of two infinite sets}\).

Of course the first part follows from the second and the third combined, but even if those are inaccurate or incorrect I still feel that the first part is the most fundamental point of this conjecture.

There are no comments on this post.

Want to comment? Send me an email!