Infinite dimensions and the axiom of choice

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:

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.

Vector Spaces and Antichains of Cardinals in Models of Set Theory

I finally uploaded my M.Sc. thesis titled “Vector Spaces and Antichains of Cardinals in Models of Set Theory”.

There are several changed from the printed and submitted version, but those are minor. The Papers page lists them.

Abstract:

Läuchli constructed a model of $\ZF$ in which there is a vector space which is not of finite dimension, but every proper subspace is of a finite dimension. In Läuchli’s model the axiom of choice fails completely, there is a countable family from which we cannot choose representatives.

In this work we generalize Läuchli’s original proof. In the proof presented here we show that we may choose any cardinal $\mu$ and construct a model of $\ZF$ in which there is a vector space such that every proper subspace has dimension less than $\mu$, but the vector space itself is not spanned by any linearly independent subset. The construction uses a technique called symmetric extensions, which is used to create models in which the axiom of choice fails. In the first chapter we will review this technique, and weak versions of the axiom of choice. We show that in our construction we may preserve relatively large fragments of choice in the universe.

We also generalize a theorem by Monro which states that it is consistent without the axiom of choice that there are infinite sets which have no countably infinite subset, but can be mapped onto very large ordinals. Our proof uses the method of symmetric extensions, in contrast to Monro which took a different approach, and we show that for any two regular cardinals $\lambda\leq\kappa$ we may construct a model of $\ZF$ in which there is a set that can be mapped onto $\kappa$, and $\lambda$ is the least ordinal which cannot be injected into this set.

In the third chapter we present a recent paper of Feldman, Orhon and Blass. In this paper the authors prove that if there is a finite bound on the size of antichains of cardinals then the axiom of choice holds. We review the original results and extend them to hold for a weaker notion of a quasi-ordering of the cardinals. We also answer one of the questions presented in the paper, and add questions of our
own.

I assume that the reader is familiar with the basics of forcing, but the third chapter can be read even by those unfamiliar with forcing.