Bases of Vector Space have Equal Cardinality

From ProofWiki
Jump to: navigation, search

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.


Also see