The question is quite simple: if $\mathbb{V}$ is a vector space and $B$ and $B'$ are basis for $\mathbb V$, then do $B$ and $B'$ have the same cardinality?

I've tried to answer the question as follows: suppose that $B'$ is bigger than $B$. Then there is a map $f:B'\to B$ surjective but non-injective. Extending this to a linear map $f':\mathbb V\to\mathbb V$ we have that $\mathbb V/\ker f'\cong \mathrm{Im} f'=\mathbb V$, with $\ker f'$ being non-trivial. But is this really a contradiction? (of course it is in finite dimension, since we know that all basis have the same cardinality in that case, but this is exactly what we are trying to prove here...)


marked as duplicate by Asaf Karagila cardinals Nov 29 '18 at 19:07

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ I think it's true that $B$ and $B'$ have the same cardinality but I don't think what you did gives a contradiction. I'm too lazy to find a reference. I'm sure someone else will find one $\endgroup$ – mathworker21 Nov 29 '18 at 18:39
  • 1
    $\begingroup$ What you give can't possibly be a contradiction as a surjective but non-injective function exists between any two infinite sets. In particular ones of the same cardinality. The argument is much easier though. $\endgroup$ – DRF Nov 29 '18 at 18:43

Your argument doesn't work, since - as mentioned in the comments - given any infinite set $A$ there is a map $f:A\rightarrow A$ which is surjective but not injective (or injective but not surjective, if you prefer).

However, the statement is true, and the proof is simpler:

  • Suppose $B, B'$ are infinite bases of $\mathbb{V}$ with $\vert B\vert<\vert B'\vert$.

  • For each $b\in B$, there is a finite $F_b\subseteq B'$ with $b\in\langle F_b\rangle$.

  • Since the union of $\vert B\vert$-many finite sets has cardinality $\vert B\vert$, the set $$\hat{B}=\bigcup_{b\in B}F_b$$ has cardinality $\vert B\vert$.

  • Since $\vert B\vert<\vert B'\vert$, there must therefore be some $a\in B'\setminus\hat{B}$.

  • But since $B$ spans $\mathbb{V}$, $a$ can be written as a linear combination of elements of $B$, and hence can be written as a linear combination of elements of $\hat{B}$. This contradicts the linear independence of $B'$.

As a quick pedagogical aside, here's an attempted proof which doesn't quite work:

Since $B$ is a basis for $\mathbb{V}$, we have that every element of $B'$ can be represented as a finite linear combination of elements of the field of scalars $F$. Using the fact that the set of finite subsets of an infinite set has the same cardinality as the original set, the cardinality of the set of linear combinations of elements of $B$ is $\vert B\vert\times\vert F\vert$, and so we get $$\vert B'\vert\le\vert B\vert\times\vert F\vert.$$

In case $F$ is "small" - that is, in case $\vert F\vert\le\vert B\vert$ - then we get $\vert B'\vert\le\vert B\vert$ (since multiplication of two infinite cardinalities just results in the larger of the two). But in case $F$ is large, we don't get anything. E.g. this argument doesn't rule out the possibility of a vector space over a field of cardinality $\aleph_{\omega^3+\omega\cdot 842+17}$ with one basis of cardinality $\aleph_{\omega^2+9}$ and another basis of cardinality $\aleph_0$.

Note that we've used the axiom of choice crucially in the above when we calculated the cardinality of $\hat{B}$ (which we needed in order to conclude the existence of $a$). Without the axiom of choice, the argument above breaks down. This is the only essential use of choice - note that the second bulletpoint does not require choice, since there is a unique minimal choice of $F_b$.

The full axiom of choice is not needed, and the general study of how much choice is needed to prove various mathematical results - around vector spaces and other topics - is quite rich; I just want to point out the reliance on something beyond set theory without choice, here.

  • $\begingroup$ +1 Very nice. Was writing it up but got sidetracked by the size of the underlying field. $\endgroup$ – DRF Nov 29 '18 at 19:03
  • $\begingroup$ @DRF Yes, if you just calculate the size of the set of all linear combinations from $B$ you only get the result in case the field of scalars is no larger than the smaller basis. $\endgroup$ – Noah Schweber Nov 29 '18 at 19:06
  • $\begingroup$ Since you bring up choice, this is really a compactness argument, so perhaps unsurprisingly, it only requires the Boolean Prime Ideal theorem, and indeed it is weaker. $\endgroup$ – Asaf Karagila Nov 29 '18 at 19:09
  • $\begingroup$ @AsafKaragila Yes, I didn't mean to imply it needed full choice - edited! $\endgroup$ – Noah Schweber Nov 29 '18 at 19:10
  • $\begingroup$ Just like you shouldn't write in your CV that a paper was submitted, until you actually submitted it, you shouldn't write in your comment that you've edited your answer until you've done that. It's all kinds of confusing! :-) $\endgroup$ – Asaf Karagila Nov 29 '18 at 19:11

Not the answer you're looking for? Browse other questions tagged or ask your own question.