# Bases of Vector Space have Equal Cardinality

## Theorem

Let $k$ be a division ring.

Let $V$ be a vector space over $k$.

Let $X$ and $Y$ be bases of $V$.

Then $X$ and $Y$ are equinumerous.

## Proof

We will first prove that there is an injection from $X$ to $Y$.

Let $x \in X$.

By Expression of Vector as Linear Combination from Basis is Unique: General Result, there is a unique finite subset $C_x$ of $R \times Y$ such that:

- $\displaystyle x = \sum_{\left({r, v}\right) \mathop \in C_x} r \cdot v$ and
- $\forall \left({r, v}\right) \in C_x: r \ne 0_R$

Define $\Phi: X \to \mathcal P \left({Y}\right)$ by:

- $\Phi \left({x}\right) := \operatorname{Img} \left({C_x}\right)$

We next show that $\langle \Phi \left({x}\right) \rangle_{x \in X}$ satisfies the **marriage condition**.

That is, for every finite subset $F$ of $X$:

- $\displaystyle \left|{F}\right| \le \left|{\bigcup \Phi \left({F}\right)}\right|$

Since $X$ is a basis, it is linearly independent.

By Subset of Linearly Independent Set is Linearly Independent, $F$ is also linearly independent.

By the definition of $\Phi$, $\displaystyle F \subseteq \operatorname{span} \bigcup \Phi \left({F}\right)$.

By Finite Union of Finite Sets is Finite, $\displaystyle \bigcup \Phi \left({F}\right)$ is finite.

Thus by Size of Linearly Independent Subset is at Most Size of Finite Generator:

- $\displaystyle \left|{F}\right| \le \left|{\bigcup \Phi \left({F}\right)}\right|$

By Hall's Marriage Theorem, there is an injection from $X$ into $Y$.

Precisely the same argument with $X$ and $Y$ interchanged shows that there is an injection from $Y$ into $X$ as well.

Thus by the Cantor-Bernstein-Schröder Theorem, $X$ and $Y$ are equinumerous.

$\blacksquare$

#### Boolean Prime Ideal Theorem

This proof depends on the Boolean Prime Ideal Theorem (BPI), by way of Hall's Marriage Theorem/General Set.

Although not as strong as the Axiom of Choice, the BPI is similarly independent of the Zermelo-Fraenkel axioms.

As such, mathematicians are generally convinced of its truth and believe that it should be generally accepted.

## Also known as

Some authors refer to this as the **dimension theorem for vector spaces**, but it should not be confused with e.g. the Rank Plus Nullity Theorem.