26

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?)

Asaf Karagila
  • 38,140

2 Answers2

14

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.

Andrés E. Caicedo
  • 32,193
  • 5
  • 130
  • 233
David Milovich
  • 1,131
  • 1
    Very interesting! How strong is the assertion that the dimension is well defined? Does it imply BPIT or a weak version of it? – Asaf Karagila Apr 07 '12 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$. – David Milovich Apr 09 '12 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. – David Milovich Apr 09 '12 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$? – David Milovich Apr 09 '12 at 17:28
  • I actually think of no basis as "no dimension". Take for example $\ell_p$ spaces in the presence of "All sets of reals have Baire property", this makes $\ell_p$ and $\ell_q$ non-isomorphic as vector spaces. Both have no Hamel basis. Dimension is only defined for vector spaces which already have some basis, and any other basis have the same cardinality. I am not sure that I understand your example about the amorphous set. Do you suggest that there is a well defined notion of dimension or that there is none? – Asaf Karagila Apr 09 '12 at 17:41
  • I'm suggesting $W$ as a test question. Can you cook up a model of ZF with an amorphous set $S$ such that its power set $W$ has an $F_2$-basis not of cardinality $|S|+1$, or does amorphousness of $S$ ZF-imply that all bases of $W$ are too "trivial" for that to happen? – David Milovich Apr 09 '12 at 17:49
  • Ah. I will give it some thought. However I believe that the amorphousness is too restrictive. I have to admit that I could never sit through the entire proof of Lauchli (which appears in Jech's small book as an exercise) about vector space with one basis which is D-finite and another which is not. – Asaf Karagila Apr 09 '12 at 18:03
  • Can we continue this over email? I have some vague ideas I'd enjoy bouncing around with someone. – Asaf Karagila Apr 10 '12 at 20:43
  • Sure---you can find one my email addresses here: http://www.tamiu.edu/~dmilovich/ – David Milovich Apr 12 '12 at 18:24
  • 1
    David, I completely forgot to send you an email!! :\ – Asaf Karagila Jan 28 '14 at 02:22
  • Is DC consistent with ZF+dimension of vector space is well defined? – Sushil Jun 26 '15 at 17:03
  • I think people should start using automated provers to play with concepts more rigorously and faster. https://arxiv.org/pdf/1806.04077.pdf – Brian Cannard Jun 19 '20 at 11:10
1

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

Maxime Ramzi
  • 13,453
  • 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? – Andreas Blass Jan 03 '17 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 – Maxime Ramzi Jan 03 '17 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? – Asaf Karagila Jan 03 '17 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? – Andreas Blass Jan 03 '17 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. – Asaf Karagila Jan 03 '17 at 18:55
  • @AsafKaragila Max already included the injectivity requirement in $T_1$. The problem is to show that $T_1$ is satisfiable. That's where I don't (yet) see how to avoid the marriage theorem. We need that the system of sets $(J_i:i\in I_0)$ has a transversal (= system of distinct representatives), which seems to need the marriage theorem. – Andreas Blass Jan 03 '17 at 19:03
  • @Andreas: Only when I finished writing this comment in a previous version claiming I am dense and still can't see what's missing, I finally saw what's missing. Yeah, it seems like a gap (fixable, but as pointed out, in a way that makes this very similar to what David wrote). – Asaf Karagila Jan 03 '17 at 19:21