[proofplan] We prove a [comparison principle](/theorems/4870): every linearly independent subset of the span of a finite set has cardinality at most that finite set. This handles the finite-dimensional case immediately. For the infinite case, we express each basis element of $B$ using its finite support in the basis $C$, observe that each fixed finite support can occur only finitely many times, and use the fact that an infinite set has only $|C|$ many finite subsets. This gives $|B| \leq |C|$, and the symmetric argument gives $|C| \leq |B|$; Cantor-Bernstein then gives equality. [/proofplan]

[step:Compare linearly independent sets inside the span of a finite set]We first prove the finite comparison lemma needed below. [claim:Finite spanning sets bound linearly independent subsets] Let $T \subset V$ be finite, and let $A \subset \operatorname{span}_k(T)$ be linearly independent over $k$. Then $A$ is finite and \begin{align*} |A| \leq |T|. \end{align*} [/claim] [proof] We argue by induction on the non-negative integer $m = |T|$. If $m = 0$, then $T = \varnothing$ and $\operatorname{span}_k(T) = \{0\}$. Since a linearly independent set cannot contain $0$, we have $A = \varnothing$, so the assertion holds. Assume the assertion holds for all finite subsets of cardinality $m-1$, where $m \geq 1$, and let $|T| = m$. Choose an element $t_0 \in T$ and define $T_0 := T \setminus \{t_0\}$. If $A \subset \operatorname{span}_k(T_0)$, the induction hypothesis gives $|A| \leq |T_0| = m-1 \leq m$. Otherwise choose $a_0 \in A \setminus \operatorname{span}_k(T_0)$. Since $a_0 \in \operatorname{span}_k(T)$, there are $\alpha \in k$ and $u \in \operatorname{span}_k(T_0)$ such that \begin{align*} a_0 = \alpha t_0 + u. \end{align*} The coefficient $\alpha$ is nonzero; if $\alpha = 0$, then $a_0 \in \operatorname{span}_k(T_0)$, contradicting the choice of $a_0$. For each $a \in A \setminus \{a_0\}$, choose $\beta_a \in k$ and $v_a \in \operatorname{span}_k(T_0)$ such that \begin{align*} a = \beta_a t_0 + v_a. \end{align*} Define \begin{align*} a^\sharp := a - \frac{\beta_a}{\alpha}a_0. \end{align*} Then $a^\sharp \in \operatorname{span}_k(T_0)$, because the $t_0$-coefficient cancels. Let \begin{align*} A^\sharp := \{a^\sharp : a \in A \setminus \{a_0\}\}. \end{align*} We show that $A^\sharp$ is linearly independent. Let $a_1,\dots,a_r$ be distinct elements of $A \setminus \{a_0\}$, and suppose $\gamma_1,\dots,\gamma_r \in k$ satisfy \begin{align*} \sum_{i=1}^r \gamma_i a_i^\sharp = 0. \end{align*} Substituting the definition of $a_i^\sharp$ gives \begin{align*} \sum_{i=1}^r \gamma_i a_i - \left(\sum_{i=1}^r \gamma_i\frac{\beta_{a_i}}{\alpha}\right)a_0 = 0. \end{align*} This is a finite linear relation among distinct elements of the linearly independent set $A$, so every coefficient is zero. In particular, $\gamma_i = 0$ for every $i$. Hence $A^\sharp$ is linearly independent. The map $A \setminus \{a_0\} \to A^\sharp$ given by $a \mapsto a^\sharp$ is injective: if $a^\sharp = b^\sharp$ for distinct $a,b \in A \setminus \{a_0\}$, then \begin{align*} a - b - \frac{\beta_a-\beta_b}{\alpha}a_0 = 0, \end{align*} which is a nontrivial finite linear relation among elements of $A$. Therefore \begin{align*} |A \setminus \{a_0\}| = |A^\sharp|. \end{align*} By the induction hypothesis applied to $A^\sharp \subset \operatorname{span}_k(T_0)$, the set $A^\sharp$ is finite and $|A^\sharp| \leq |T_0| = m-1$. Therefore $A$ is finite and \begin{align*} |A| = 1 + |A^\sharp| \leq 1 + (m-1) = m = |T|. \end{align*} This completes the induction. [/proof][/step]

[guided]The point of this lemma is to isolate the only finite-dimensional ingredient we need: a finite spanning set cannot contain too many independent vectors in its span. We prove this by induction on $m = |T|$. When $m = 0$, the span of $T$ is $\{0\}$, and a linearly independent set cannot contain $0$, so $A = \varnothing$. Now suppose $m \geq 1$ and the result is known for sets of size $m-1$. Choose $t_0 \in T$ and put $T_0 := T \setminus \{t_0\}$. If all of $A$ already lies in $\operatorname{span}_k(T_0)$, the induction hypothesis applies directly. The only interesting case is when some $a_0 \in A$ does not lie in $\operatorname{span}_k(T_0)$. Since $a_0$ lies in $\operatorname{span}_k(T)$, we can write \begin{align*} a_0 = \alpha t_0 + u \end{align*} with $\alpha \in k$ and $u \in \operatorname{span}_k(T_0)$. The coefficient $\alpha$ must be nonzero, because otherwise $a_0$ would lie in $\operatorname{span}_k(T_0)$. For each $a \in A \setminus \{a_0\}$, write \begin{align*} a = \beta_a t_0 + v_a \end{align*} with $\beta_a \in k$ and $v_a \in \operatorname{span}_k(T_0)$. We remove the $t_0$-component by defining \begin{align*} a^\sharp := a - \frac{\beta_a}{\alpha}a_0. \end{align*} The coefficient of $t_0$ in this expression is $\beta_a - \frac{\beta_a}{\alpha}\alpha = 0$, so $a^\sharp \in \operatorname{span}_k(T_0)$. Let \begin{align*} A^\sharp := \{a^\sharp : a \in A \setminus \{a_0\}\}. \end{align*} If a finite linear relation \begin{align*} \sum_{i=1}^r \gamma_i a_i^\sharp = 0 \end{align*} holds among distinct elements of $A^\sharp$, then substituting the definition of $a_i^\sharp$ gives \begin{align*} \sum_{i=1}^r \gamma_i a_i - \left(\sum_{i=1}^r \gamma_i\frac{\beta_{a_i}}{\alpha}\right)a_0 = 0. \end{align*} This is a finite linear relation among elements of $A$. Since $A$ is linearly independent, every $\gamma_i$ is zero. Thus $A^\sharp$ is linearly independent. The assignment $a \mapsto a^\sharp$ is also injective. If $a^\sharp = b^\sharp$ for distinct $a,b \in A \setminus \{a_0\}$, then \begin{align*} a - b - \frac{\beta_a-\beta_b}{\alpha}a_0 = 0, \end{align*} which is a nontrivial linear relation among elements of $A$, impossible by [linear independence](/page/Linear%20Independence). Therefore $A \setminus \{a_0\}$ has the same cardinality as $A^\sharp$. Now $A^\sharp$ is a linearly independent subset of $\operatorname{span}_k(T_0)$, and $|T_0| = m-1$. By induction, $A^\sharp$ is finite and $|A^\sharp| \leq m-1$. Hence \begin{align*} |A| = 1 + |A^\sharp| \leq 1 + (m-1) = m = |T|. \end{align*}[/guided]

[step:Handle the case where one basis is finite] Assume first that $C$ is finite. Since $B$ is linearly independent and $C$ spans $V$, we have \begin{align*} B \subset \operatorname{span}_k(C). \end{align*} By the finite comparison lemma, $B$ is finite and $|B| \leq |C|$. Since $B$ is finite, $C$ is linearly independent, and $B$ spans $V$, the same lemma applied with $T = B$ and $A = C$ gives \begin{align*} |C| \leq |B|. \end{align*} Thus $|B| = |C|$ when $C$ is finite. If instead $B$ is finite, then $C \subset \operatorname{span}_k(B)$ because $B$ spans $V$, and $C$ is linearly independent because $C$ is a basis. The finite comparison lemma applied with $T = B$ and $A = C$ gives that $C$ is finite and \begin{align*} |C| \leq |B|. \end{align*} Since $C$ is finite, $B$ is linearly independent, and $C$ spans $V$, the same lemma applied with $T = C$ and $A = B$ gives \begin{align*} |B| \leq |C|. \end{align*} Hence $|B| = |C|$ when $B$ is finite. [/step]

[step:Bound one infinite basis by the finite supports in the other]Assume now that $C$ is infinite. For each $v \in V$, because $C$ is a basis of $V$, there is a unique finite subset $S_C(v) \subset C$ such that \begin{align*} v \in \operatorname{span}_k(S_C(v)) \end{align*} and every element of $S_C(v)$ has nonzero coefficient in the unique expansion of $v$ in the basis $C$. Let $\mathcal{P}_{\mathrm{fin}}(C)$ denote the set of all finite subsets of $C$. Define the support map \begin{align*} \Phi_C: B \to \mathcal{P}_{\mathrm{fin}}(C), \quad b \mapsto S_C(b). \end{align*} For each $T \in \mathcal{P}_{\mathrm{fin}}(C)$, define the fiber \begin{align*} B_T := \{b \in B : \Phi_C(b) = T\}. \end{align*} Then $B_T \subset \operatorname{span}_k(T)$, and $B_T$ is linearly independent because it is a subset of the basis $B$. By the finite comparison lemma, \begin{align*} |B_T| \leq |T|. \end{align*} In particular, each fiber $B_T$ is finite. The fibers $B_T$ are pairwise disjoint and their union is $B$. Since $C$ is infinite, the stated cardinal arithmetic hypothesis gives $|\mathcal{P}_{\mathrm{fin}}(C)| = |C|$. More concretely, the map $c \mapsto \{c\}$ injects $C$ into $\mathcal{P}_{\mathrm{fin}}(C)$, and every finite subset of $C$ is the image of a finite tuple from $C$, so the standard finite-subset counting identity for infinite sets applies. For each $T \in \mathcal{P}_{\mathrm{fin}}(C)$, choose an injection $\iota_T: B_T \to \mathbb{N}$; this is possible because $B_T$ is finite. Define \begin{align*} \Psi: B \to \mathcal{P}_{\mathrm{fin}}(C) \times \mathbb{N}, \quad b \mapsto (\Phi_C(b), \iota_{\Phi_C(b)}(b)). \end{align*} The map $\Psi$ is injective because the first coordinate identifies the fiber and the second coordinate is injective on that fiber. Hence $|B| \leq |\mathcal{P}_{\mathrm{fin}}(C) \times \mathbb{N}|$. Since $|\mathcal{P}_{\mathrm{fin}}(C)| = |C|$ and $C$ is infinite, the stated cardinal arithmetic hypothesis $\kappa \cdot \aleph_0 = \kappa$ gives $|\mathcal{P}_{\mathrm{fin}}(C) \times \mathbb{N}| = |C|$.[/step]

[guided]We now compare an arbitrary basis $B$ to an infinite basis $C$. The main issue is that a vector in $V$ is not usually a scalar multiple of a single element of $C$; it is a finite linear combination of elements of $C$. So we record the finite set of basis elements from $C$ that actually appear. For each $v \in V$, the basis property of $C$ gives a unique finite expansion of $v$ in terms of elements of $C$. Let $S_C(v)$ be the finite subset of $C$ consisting exactly of those basis elements whose coefficients in this expansion are nonzero. Thus $S_C(v) \subset C$ is finite and \begin{align*} v \in \operatorname{span}_k(S_C(v)). \end{align*} Let $\mathcal{P}_{\mathrm{fin}}(C)$ be the set of all finite subsets of $C$, and define \begin{align*} \Phi_C: B \to \mathcal{P}_{\mathrm{fin}}(C), \quad b \mapsto S_C(b). \end{align*} This map sends each basis element $b \in B$ to its finite support with respect to the basis $C$. Fix a finite subset $T \subset C$. The fiber over $T$ is \begin{align*} B_T := \{b \in B : \Phi_C(b) = T\}. \end{align*} Every element of $B_T$ belongs to $\operatorname{span}_k(T)$ by the definition of support. Also, $B_T$ is linearly independent because $B_T \subset B$ and $B$ is a basis. The finite comparison lemma therefore applies and gives \begin{align*} |B_T| \leq |T|. \end{align*} So a fixed finite support $T$ can support only finitely many elements of $B$. Now we count all possible supports. Since $C$ is infinite, the stated cardinal arithmetic hypothesis gives that the set of finite subsets of $C$ has cardinality $|C|$. Indeed, $C$ injects into $\mathcal{P}_{\mathrm{fin}}(C)$ by $c \mapsto \{c\}$, while the reverse inequality is exactly the finite-subset counting identity for infinite sets. Thus there are only $|C|$ possible finite supports. Finally, the set $B$ is the disjoint union of its fibers: \begin{align*} B = \bigcup_{T \in \mathcal{P}_{\mathrm{fin}}(C)} B_T. \end{align*} We now make the counting of this union explicit. For each finite subset $T \in \mathcal{P}_{\mathrm{fin}}(C)$, the fiber $B_T$ is finite, so choose an injection $\iota_T: B_T \to \mathbb{N}$. Define \begin{align*} \Psi: B \to \mathcal{P}_{\mathrm{fin}}(C) \times \mathbb{N}, \quad b \mapsto (\Phi_C(b), \iota_{\Phi_C(b)}(b)). \end{align*} Why is $\Psi$ injective? If two elements of $B$ have different first coordinates, then they lie in different fibers. If they have the same first coordinate $T$, then they both lie in $B_T$, and the second coordinate separates them because $\iota_T$ is injective. Hence \begin{align*} |B| \leq |\mathcal{P}_{\mathrm{fin}}(C) \times \mathbb{N}|. \end{align*} Since $|\mathcal{P}_{\mathrm{fin}}(C)| = |C|$ and $C$ is infinite, the stated cardinal arithmetic identity $\kappa \cdot \aleph_0 = \kappa$ for infinite cardinals gives $|\mathcal{P}_{\mathrm{fin}}(C) \times \mathbb{N}| = |C|$. Therefore $|B| \leq |C|$.[/guided]

[step:Apply the symmetric comparison and Cantor-Bernstein] If both bases are infinite, the previous step gives \begin{align*} |B| \leq |C|. \end{align*} Interchanging the roles of $B$ and $C$ gives \begin{align*} |C| \leq |B|. \end{align*} By the stated Cantor-Bernstein theorem for sets, there exists a bijection $B \to C$, hence $|B| = |C|$. Together with the finite case, this proves that any two bases of $V$ over $k$ have the same cardinality. [/step]