# Proof that two basis of a vector space have the same cardinality in the infinite-dimensional case

I am having a difficulty setting up the proof of the fact that two basis of a vector space have the same cardinality for the infinite-dimentional case. In particular, let $V$ be a vector space over a field $K$ and let $\left\{v_i\right\}_{i \in I}$ be a basis where $I$ is infinite countable. Let $\left\{u_j\right\}_{j \in J}$ be another basis. Then $J$ must be infinite countable as well. Any ideas on how to approach the proof?

In spirit, the proof is very similar to the proof that two finite bases must have the same cardinality: express each vector in one basis in terms of the vectors in the other basis, and leverage that to show the cardinalities must be equal, by using the fact that the "other" basis must span and be lineraly independent.

Suppose that $\{v_i\}_{i\in I}$ and $\{u_j\}_{j\in J}$ are two infinite bases for $V$.

For each $i\in I$, $v_i$ is in the linear span of $\{u_j\}_{j\in J}$. Therefore, there exists a finite subset $J_i\subseteq J$ such that $v_i$ is a linear combination of the vectors $\{u_j\}_{j\in J_i}$ (since a linear combination involves only finitely many vectors with nonzero coefficient).

Therefore, $V=\mathrm{span}(\{v_i\}_{i\in I}) \subseteq \mathrm{span}\{u_j\}_{j\in \cup J_i}$. Since no proper subset of $\{u_j\}_{j\in J}$ can span $V$, it follows that $J = \mathop{\cup}\limits_{i\in I}J_i$.

Now use this to show that $|J|\leq |I|$, and a symmetric argument to show that $|I|\leq |J|$.

Note. The argument I have in mind in the last line involves some (simple) cardinal arithmetic, but it is enough that at least some form of the Axiom of Choice may be needed in its full generality.

• Just to check: Am I correct to say the dependence on the axiom of choice is contained entirely in the last line? It seems to me, though, that if $I$ and $J$ are both well-ordered then AC is not required. – Zhen Lin Jul 20 '11 at 17:25
• @Zhen Lin: There is certainly some cardinal arithmetic going on in the last line, which would indeed invoke (at least in its most straighforward form) AC. Of course, even assuming vector spaces have bases is a nod in AC's direction... – Arturo Magidin Jul 20 '11 at 17:26
• @Arturo: The axiom of countable choice is enough to show that a countable union of countable sets is countable (this can even be diminished to axiom of choice for countable family of countable sets, which is notably weaker!). I suppose you could get away even with axiom of choice for finite sets. – Asaf Karagila Jul 20 '11 at 18:14
• @Manos: Here's what I had in mind: Since $J=\cup J_i$, then $|J|=|\cup J_i| \leq \sum |J_i|$. Since each $J_i$ is finite, $|J_i|\leq\aleph_0$, so $|J|\leq \sum |J_i|\leq \sum \aleph_0$. Since the sum has $|I|$ many summands, $\sum \aleph_0 = |I|\aleph_0 = |I|$ (since $|I|$ is infinite). – Arturo Magidin Jul 21 '11 at 15:27
• Somewhat late, but it turns out that BPI/Ultrafilter Lemma is enough to conclude that if $V$ has a basis, then all bases have the same cardinality. The proof is quite nice, too! – Asaf Karagila May 3 '12 at 21:00

Once you have the necessary facts about infinite sets, the argument is very much like that used in the finite-dimensional case. The two crucial pieces of information are (1) that if $I$ is an infinite set of cardinality $\kappa$, say, then $I$ has $\kappa$ finite subsets, and (2) that if $|J|>\kappa$, and $J$ is expressed as the union of $\kappa$ subsets, then at least one of those subsets must be infinite.

Let $B_1 = \{v_i:i\in I \}$ and $B_2 = \{u_j:j \in J \}$, and suppose that $|J|>|I| = \kappa$. Each $u_j \in B_2$ can be written as a linear combination of some finite subset of $B_1$, say $u_j = \sum\limits_{i \in F_j}k_{ji}v_i$, where $F_j$ is a finite subset of $I$. For each finite $F \subseteq I$ let $J_F = \{j \in J:F_j = F\}$; clearly $J$ is the union of these sets $J_F$. But by (1) above $I$ has only $\kappa$ finite subsets, and $|J|>\kappa$, so by (2) above there must be some finite $F \subseteq I$ such that $J_F$ is infinite.

To simplify the notation, let $F = \{i_1,i_2,\dots,i_n\}$, and for $\mathcal{l}=1,2,\dots,n$ let$v_\mathcal{l} = v_{i_\mathcal{l}}$; then every vector $u_j$ with $j \in J_F$ is a linear combination of the vectors $v_1,v_2,\dots,v_n$. In other words, $\{u_j:j \in J_F\} \subseteq \operatorname{span}\{v_1,v_2,\dots,v_n\}$, and of course $\{u_j:j \in J_F\}$, being a subset of the basis $B_2$, is linearly independent. But $\operatorname{span}\{v_1,v_2,\dots,v_n\}$ is of dimension $n$ over $K$, so any set of more than $n$ vectors in $\operatorname{span}\{v_1,v_2,\dots,v_n\}$ must be linearly dependent, and we have a contradiction. It follows that we must have $|J| \le |I|$. By symmetry (or by the same argument with the rôles of $I$ and $J$ interchanged), $|I| \le |J|$, and hence $|I|=|J|$.

• Thank you very much for your answer. Something that confuses me regarding cardinalities: if $I$ is infinite, there are two cases, right? Either $I$ is countable or uncountable. So when we say in (1) that $|I|=\kappa$, then $\kappa$ can actually have one of two values, the cardinality of the integers or the cardinality of the reals, right? – Manos Jul 21 '11 at 18:45
• No, there are infinitely many different uncountable cardinalities. For example, the set of subsets of the reals has a larger cardinality than the set of reals itself. In fact, if $S$ is any set, $\mathscr{P}(S)$ has larger cardinality than $S$. – Brian M. Scott Jul 21 '11 at 19:25
• @Brian To slightly shorten your proof, why not define from the start that $J_F=\{j\in J : u_j\in \text{span}\{v_i : i \in F\}\}$, and then proceed exactly as above? – Aubrey Feb 2 '15 at 17:10
• @Aubrey: Because the exposition is clearer the way I wrote it. – Brian M. Scott Feb 2 '15 at 19:03
• @Brian M. Scott , What does it mean " $k$ finite subset " , where $k$ is infinite cardinality? – hew Nov 7 '19 at 7:19

Here is an alternative proof, which involves Choice and transfinite induction, but no explicit cardinal arithmetic.

Let $$\mathcal{B}$$ and $$\mathcal{C}$$ be two bases of a vector space $$V$$. We will "transform" $$\mathcal{C}$$ into $$\mathcal{B}$$. Take a well-ordering $$\leq$$ on $$\mathcal{B}$$. Define a function $$f\colon\mathcal{B}\to\mathcal{C}$$ as follows:

• For $$b=\min\mathcal{B}$$, express $$b=\sum_{c\in\mathcal{C}}\lambda_c c$$. Choose $$c$$ such that $$\lambda_c\neq 0$$ and set $$f(b)=c$$. In this manner, $$(\mathcal{C}\setminus\left\{f(b)\right\})\cup\left\{b\right\}$$ is a basis for $$V$$ of same cardinality than $$\mathcal{C}$$.
• Suppose that $$f(b)$$ is defined for all $$b, and that $$\mathcal{C}_{ is a basis for $$V$$. Let us expand $$b_0$$ as an element of this basis: $$b_0=\left(\sum_{c\neq f(b)\text{ for }b Since $$\mathcal{B}$$ is a basis, then at least one of the $$\lambda_c$$ above is nonzero. Choose such $$c$$ and set $$f(b)=c$$.

It should be easy to see that the transfinite process is well-defined. The function $$f$$ is injective by definition, so the set $$\mathcal{C}_{<\mathcal{B}}=\left(\mathcal{C}\setminus f(\mathcal{B})\right)\cup\mathcal{B}$$ has the same cardinality as $$\mathcal{C}$$. It should also be easy to see that it is a basis for $$V$$. But it contains the basis $$\mathcal{B}$$. So $$\mathcal{C}_{<\mathcal{B}}=\mathcal{B}$$, i.e., $$C=f(\mathcal{B})$$. Again, since $$f$$ is injective, this means that $$|\mathcal{C}|=|\mathcal{B}|$$.