# Sizes of bases of vector spaces without the axiom of choice

Assuming the axiom of choice does not hold we have that there is a vector space without a basis. The situation can be, in some sense, worse. It is consistent that there are vector spaces that have two bases with completely different cardinalities.

Is anything known on when a vector space is spanned by sets of different cardinalities, and on the relation between those cardinalities?

Is there a known relation between common choice principles (BPIT, DC, etc.) and possible cardinalities of a vector space? (For example, does BPIT implies that every two bases have the same size?)

Yes, ZF+BPIT implies that vector space dimension is well-defined. [Edit: some Googling shows that James Halpern gave the same answer back in the 1960s.]

Working in ZF+BPIT, fix a field $F$ and an $F$-vector space $V$ and bases $A$ and $B$ of V. That is, each element of $V$ is a unique $F$-linear combination of elements of $A$; likewise for $B$. For each $a\in A$, let $S_a$ be the minimal subset of $B$ such that $a$ is spanned by $S_a$. Each $S_a$ is finite; give it the discrete topology. Let $X=\prod_{a\in A}S_a$, which is nonempty by BPIT (and is compact Hausdorff). By Schroeder-Bernstein, it suffices to show that some $f\in X$ is injective. By compactness, it suffices to show that for every finite subset $K$ of $A$, there is an $f\in X$ that is injective on $K$. Since each $\prod_{a\in A\setminus K}S_a$ is nonempty by BPIT, it suffices to show that there is an injection in every $\prod_{a\in K}S_a$. That is a nice little linear algebra exercise you can solve in ZF using the finite case of Hall's marriage theorem.

• Very interesting! How strong is the assertion that the dimension is well defined? Does it imply BPIT or a weak version of it? Apr 7, 2012 at 10:01
• My guess is that it's a very weak assertion. What does it buy you when the dimension is $\infty$ (that is, when there is no basis)? I conjecture that you could have all your favorite "pathological" sets in a model where vector space dimension is well defined; you'd just need to "protect" the pathologies by ensuring that all vector spaces into which they inject have dimension $\infty$. Apr 9, 2012 at 16:49
• If I was looking for some kind of reversal, I would play with the $F_2$-vector space of all functions from a given set $S$ to $F_2$. There a basis is exactly a minimal family of subsets of $S$ such that every subset of $S$ is a symmetric sum of finitely many sets from the family. In any case, I wouldn't be surprised if the literature has already answered the questions in your comment. I'm just not very familiar with this literature. Apr 9, 2012 at 17:03
• I can think of one pathology where you can't "avoid" a basis: the power set $W$ of an amorphous set $S$ has an $F_2$-basis: the singletons and $S$ itself. Try this: can you prove $dim(W)=|S|+1$ from the amorphousness of $S$? Apr 9, 2012 at 17:28
• David, I completely forgot to send you an email!! :\ Jan 28, 2014 at 2:22

If I'm not mistaken there is another proof that BPI implies that any two bases of a vector space have the same cardinality. As has been noted earlier, if $(u_i)_{i \in I}$ and $(v_j)_{j\in j}$ are two bases of $V$ vector space over $K$ it suffices to show that there's an injection $I\to J$. We're going to use the equivalence "BPI$\iff$ Compactness for propositional logic". For each $i\in I$ there exists a unique minimal finite set $J_i \subset J$ such that $u_i$ is spanned by $J_i$. For $i \in I, j\in J$ we create a propositional variable $P_{i,j}$ supposed to mean $f(i)=j$. Then we create a theory $T$ that contains all the $\neg (P_{i,j} \land P_{i, j'})$ when $j\neq j' \in J$, and $\neg (P_{i,j}\land P_{i',j})$ when $i\neq i' \in I$. This is supposed to mean "$f$ is injective". But obviously this isn't enough (otherwise one could prove that any set injects into another), as we need to express something like "$f(i)$ is defined for any $i\in I$". This is where we use the $J_i$ : we add to the theory the formulas $\displaystyle\bigvee_{j\in J_i} P_{i,j}$ for $i\in I$, which is a well defined formula (up to logical equivalence), as each $J_i$ is finite. Now if $T$ is satisfiable, then we have found our injection : assume $v$ is a model for $T$, then $f:=\{(i,j) \in I\times J\mid v(P_{i,j}) =1\}$ is an injection, whose domain is $I$. Compactness shows it's enough to have $T$ finitely satisfiable, and if $T_0$ is a finite subtheory of $T$, ot is contained in a finite subtheory $T_1$ which expresses (modulo our identification) that a certain finite subset $I_0\subset I$ is injected into $J$ with every $i\in I_0$ being sent into $J_i$. Now unless I'm making a mistake, this is possible, as it only uses the cardinality of bases for finite dimensional spaces, which is true without any sort of choice. So $T$ is satisfiable, we have our injection, and symmetry + Cantor-Bernstein allow us to conclude

EDIT : I might actually be making a mistake, it's possible that a "Hall's mariage theorem" argument can't be avoided

• I don't immediately see the last step, where you inject a finite $I_0$ into $J$ sending each $i\in I_0$ to a member of $J_i$. This looks as though it will involve the marriage theorem (as in David Milovich's answer) and not just the cardinality of bases in the finite-dimensional case. The trouble is that the finite-dimensional subspace spanned by $I_0$ may be smaller than that spanned by the union of the associated $J_i$'s. Am I overlooking an easy argument here? Jan 3, 2017 at 16:08
• You might be right. I'll look into it. But the cardinality of finite bases is useful to show that the hypothesis of Hall's mariage theorem are verified here. But if the theorem is necessary then my proof is useless, as it would essentially be the same as that of David Milovich Jan 3, 2017 at 16:32
• @Andreas: Why do we care that the $I_0$-spanned subspace is smaller than the one given by the associated $J_i$'s, though? Jan 3, 2017 at 18:39
• @AsafKaragila To use the uniqueness of dimension for finite-dimensional spaces, we need a finite-dimensional space and two bases for it. I conjecture that the space that Max had in mind for this purpose is the space generated by $I_0$. But where would another basis for that space come from? I suspect the union of the $J_i$'s is what Max had in mind, but that might be too big. So what other finite-dimensional space with two bases is available? Jan 3, 2017 at 18:46
• @Andreas: I still don't see why. We are looking for an injection, not a bijection. As long as each of the $i$'s get mapped to a different $j$, we're fine. And we can always "close" $T_0$ to $T_1$ by adding the necessary clauses to ensure injectivity. Jan 3, 2017 at 18:55