Invariance of dimension

Theorem

Invariance of dimension

T-046Home MU-202Threads structure

Statement

Let \(V\) be a vector space over a field \(F\), and let \(B\) and \(C\) be two bases of \(V\): each is a linearly independent subset of \(V\) whose span is all of \(V\) (every vector of \(V\) is a finite \(F\)-linear combination of basis vectors). Then \(|B| = |C|\) as cardinal numbers; that is, there exists a bijection \(B \to C\). In particular, if some basis of \(V\) is finite with \(n\) elements, then every basis of \(V\) is finite with exactly \(n\) elements, and the common cardinality \(\dim_F V := |B|\) is a well-defined invariant of \(V\). The finite case is a theorem of pure linear algebra (no choice needed); the infinite case as proved below uses the Axiom of Choice for its cardinal arithmetic.

Why it matters

Without this theorem the single most important invariant in linear algebra — dimension — would not exist. We constantly say "\(\dim V = n\)" and then reason from that number: coordinates relative to a basis, the size of matrices representing linear maps, the rank–nullity theorem, the classification of finite-dimensional spaces. Every one of those arguments silently assumes that the number of vectors in a basis does not depend on which basis you happened to pick. This theorem is the licence for that assumption.

It also delivers the complete classification of vector spaces: over a fixed field \(F\), two vector spaces are isomorphic if and only if they have bases of the same cardinality. A vector space is determined, up to isomorphism, by a single cardinal number. Very few algebraic categories admit so clean a classification — the theorem is the reason linear algebra is "easy" compared with, say, module theory or group theory, where the analogous statement fails outright.

Hypotheses

The scalars form a field \(F\).Division by a nonzero scalar is used in the exchange step of the proof. Over a general ring the theorem can fail: for \(R = \operatorname{End}_F(V)\) with \(V\) of countably infinite dimension, the free left \(R\)-module \(R\) itself has a basis \(\{\mathrm{id}\}\) of size \(1\) and also a basis \(\{f, g\}\) of size \(2\) (see "Fails without"). Such rings are said to lack the invariant basis number property.

Both \(B\) and \(C\) are bases — linearly independent and spanning.Drop spanning: \(\{(1,0)\}\) and \(\{(1,0),(0,1)\}\) are both linearly independent in \(\mathbb{R}^2\) with different sizes. Drop independence: \(\{(1,0),(0,1)\}\) and \(\{(1,0),(0,1),(1,1)\}\) both span \(\mathbb{R}^2\) with different sizes. Only the combination pins the cardinality down.

Linear combinations are finite.The definition of span allows only finite sums. If "infinite formal sums" were allowed (as in Hilbert-space theory), the correct notion is a Schauder or orthonormal basis, and the counting arguments below do not apply as stated; e.g. \(\ell^2\) has a countable orthonormal basis but every Hamel basis of \(\ell^2\) is uncountable.

Axiom of Choice (infinite case only).The step \(\aleph_0 \cdot \kappa = \kappa\) for infinite \(\kappa\), and the comparability of arbitrary cardinals, use AC. In ZF alone it is consistent that a vector space possesses two bases of different cardinalities (Läuchli-type models), so the infinite case is genuinely choice-dependent. The finite case is a ZF theorem.

Proof

Throughout, \(V\) is a vector space over the field \(F\) and \(B, C\) are bases of \(V\). We first prove the Steinitz Exchange Lemma in full, then deduce the finite case, then the infinite case.

Lemma (Steinitz Exchange). If \(L = \{v_1, \dots, v_m\}\) is linearly independent in \(V\) and \(S = \{w_1, \dots, w_n\}\) spans \(V\), then \(m \le n\).

We prove this by finite induction on \(k\), establishing the claim: for every \(k\) with \(0 \le k \le m\), we have \(k \le n\) and, after reindexing \(S\), the set \(\{v_1, \dots, v_k, w_{k+1}, \dots, w_n\}\) spans \(V\). Taking \(k = m\) yields the lemma. B

Base case \(k = 0\): the set \(\{w_1, \dots, w_n\}\) spans \(V\), and \(0 \le n\).

This is exactly the hypothesis that \(S\) spans \(V\); nothing to prove. A

Inductive step. Suppose \(k \lt m\), \(k \le n\), and \(\{v_1, \dots, v_k, w_{k+1}, \dots, w_n\}\) spans \(V\). Since \(v_{k+1} \in V\), there exist scalars \(a_1, \dots, a_k, b_{k+1}, \dots, b_n \in F\) with \[ v_{k+1} \;=\; \sum_{i=1}^{k} a_i v_i \;+\; \sum_{j=k+1}^{n} b_j w_j. \]

Definition of spanning set: every vector of \(V\) is a finite linear combination of the spanning vectors. A

Not all \(b_j\) can vanish; in particular \(k \lt n\), so \(k + 1 \le n\).

If every \(b_j = 0\) (which is automatic when \(k = n\), since then the second sum is empty), then \(v_{k+1} = \sum_{i=1}^{k} a_i v_i\), i.e. \(v_{k+1} - \sum a_i v_i = 0\) is a nontrivial dependence relation among \(v_1, \dots, v_{k+1}\) (the coefficient of \(v_{k+1}\) is \(1 \neq 0\)). This contradicts the linear independence of \(L\). Hence some \(b_j \neq 0\), which forces the second sum to be nonempty, i.e. \(k \lt n\). This is the step where independence of \(L\) does its work. B

Reindex so that \(b_{k+1} \neq 0\). Then \[ w_{k+1} \;=\; b_{k+1}^{-1}\left( v_{k+1} - \sum_{i=1}^{k} a_i v_i - \sum_{j=k+2}^{n} b_j w_j \right). \]

Here we invert the nonzero scalar \(b_{k+1}\): this is precisely where the field axioms are used, and it is the step that fails over a general ring. Reindexing is a permutation of the finite set \(\{k+1, \dots, n\}\) and is harmless. C

The set \(\{v_1, \dots, v_{k+1}, w_{k+2}, \dots, w_n\}\) spans \(V\), completing the induction.

By Step 5, \(w_{k+1} \in \operatorname{span}\{v_1, \dots, v_{k+1}, w_{k+2}, \dots, w_n\}\). Hence this span contains all of \(\{v_1, \dots, v_k, w_{k+1}, \dots, w_n\}\), which spans \(V\) by the inductive hypothesis; a span containing a spanning set is all of \(V\) (spans are subspaces, and a subspace containing a spanning set equals \(V\)). Together with \(k+1 \le n\) from Step 4, the claim holds for \(k+1\). By induction the claim holds for \(k = m\), so \(m \le n\). This proves the Exchange Lemma. B

Finite case. Suppose \(B\) is finite, \(|B| = n\). Then \(C\) is finite and \(|C| = n\).

Every finite subset of \(C\) is linearly independent (subsets of independent sets are independent), and \(B\) is a finite spanning set, so by the Exchange Lemma every finite subset of \(C\) has at most \(n\) elements. Hence \(C\) itself is finite with \(|C| \le n\). Now reverse the roles: \(B\) is independent and \(C\) spans, so \(|B| \le |C|\), i.e. \(n \le |C|\). Therefore \(|C| = n\). Note this also shows: if any one basis is finite, every basis is finite — so either all bases of \(V\) are finite (and equinumerous, by this step) or all are infinite. B

Infinite case: setup. Assume from now on that \(B\) and \(C\) are both infinite. For each \(b \in B\) there is a unique finite set \(\operatorname{supp}(b) \subseteq C\) and unique nonzero scalars \(\lambda_c \in F \setminus \{0\}\) \((c \in \operatorname{supp}(b))\) with \[ b \;=\; \sum_{c \,\in\, \operatorname{supp}(b)} \lambda_c\, c. \]

Existence: \(C\) spans \(V\), so \(b\) is a finite combination of elements of \(C\); discard terms with zero coefficient. Uniqueness: if two such expressions existed, subtracting them would give a nontrivial finite linear dependence among elements of \(C\), contradicting the linear independence of \(C\). A

Claim. \[ C \;=\; \bigcup_{b \in B} \operatorname{supp}(b). \]

Write \(C' := \bigcup_{b \in B} \operatorname{supp}(b) \subseteq C\). Every \(b \in B\) lies in \(\operatorname{span}(C')\) by Step 8, so \(V = \operatorname{span}(B) \subseteq \operatorname{span}(C')\), i.e. \(C'\) spans \(V\). Suppose for contradiction some \(c_0 \in C \setminus C'\). Then \(c_0 \in V = \operatorname{span}(C')\), so \(c_0\) is a finite linear combination of elements of \(C' \subseteq C \setminus \{c_0\}\). Moving \(c_0\) to one side gives a nontrivial linear dependence among finitely many elements of \(C\) (the coefficient of \(c_0\) is \(1 \neq 0\)), contradicting the independence of \(C\). Hence \(C = C'\). This is the key structural idea of the infinite case: the whole of \(C\) is swept out by the finitely many "coordinates" of the elements of \(B\). B

\[ |C| \;=\; \Bigl| \bigcup_{b \in B} \operatorname{supp}(b) \Bigr| \;\le\; \sum_{b \in B} |\operatorname{supp}(b)| \;\le\; \aleph_0 \cdot |B| \;=\; |B|. \]

First inequality: a union is dominated by the disjoint sum (cardinal arithmetic; choosing, for each element of the union, one \(b\) whose support contains it uses AC when \(B\) is infinite). Second inequality: each \(\operatorname{supp}(b)\) is finite, hence of cardinality at most \(\aleph_0\), and a sum of \(|B|\) many cardinals each \(\le \aleph_0\) is \(\le \aleph_0 \cdot |B|\). Final equality: for any infinite cardinal \(\kappa\), \(\aleph_0 \cdot \kappa = \kappa\) — a standard theorem of cardinal arithmetic under AC (it follows from \(\kappa \cdot \kappa = \kappa\) for infinite well-ordered cardinals, Hessenberg's theorem, plus AC to well-order \(B\)). C

By symmetry, \(|B| \le |C|\).

Steps 8–10 used only that \(B\) and \(C\) are bases with \(B\) infinite; exchanging the roles of \(B\) and \(C\) (both are infinite by Step 7's dichotomy) gives the reverse inequality verbatim. A

\(|C| \le |B|\) and \(|B| \le |C|\) together give \(|B| = |C|\): there is a bijection \(B \to C\). \(\blacksquare\)

Cardinal inequalities \(\kappa \le \mu\) mean the existence of injections; injections both ways yield a bijection by the Cantor–Schröder–Bernstein theorem, which is a theorem of ZF (no further choice needed at this step). Combined with the finite case (Step 7), the theorem holds for all vector spaces. A

Result

\[ B, C \text{ bases of the } F\text{-vector space } V \;\;\Longrightarrow\;\; |B| = |C| \;=:\; \dim_F V. \]

Reading. However you choose to coordinatise a vector space, you will always need exactly the same number of coordinates. The size of a basis is a property of the space, not of the basis — so "dimension" is a well-defined quantity, finite or infinite.

Scope. Applies to every vector space over every field \(F\), of any dimension, finite or infinite (the infinite case as proved uses AC). It applies to bases in the algebraic (Hamel) sense: finite linear combinations only. It does not automatically extend to free modules over arbitrary rings (invariant basis number can fail), nor to topological notions of basis such as Schauder or orthonormal bases, which are governed by different theorems.

Corollaries & converses

\(\dim_F V\) is well defined: the map \(V \mapsto \dim_F V\) is a genuine invariant, constant across all bases.
In a space with a finite basis of \(n\) elements: every linearly independent set has at most \(n\) elements, and every spanning set has at least \(n\) elements (both are direct applications of the Exchange Lemma against a basis).
If \(\dim_F V = n\) is finite, a linearly independent set with exactly \(n\) elements is automatically a basis, and a spanning set with exactly \(n\) elements is automatically a basis (see Problem 4).
Classification: \(V \cong W\) as \(F\)-vector spaces if and only if \(\dim_F V = \dim_F W\), since an isomorphism carries a basis to a basis (Worked Example 1) and, conversely, a bijection between bases extends uniquely to an isomorphism.
\(\mathbb{R}^n \cong \mathbb{R}^m\) (as vector spaces) if and only if \(n = m\).
Converse fails: a subset of \(V\) with cardinality \(\dim_F V\) need not be a basis — \(\{(1,0),(2,0)\}\) has \(2 = \dim \mathbb{R}^2\) elements but is dependent and non-spanning. Cardinality alone certifies nothing; you need independence or spanning in addition (and then, in finite dimension, you get the other for free).

Fails without

Scalars not a field (no invariant basis number). Let \(V\) be an \(F\)-vector space with countable basis \(e_0, e_1, e_2, \dots\) and let \(R = \operatorname{End}_F(V)\), a noncommutative ring. View \(R\) as a free left module over itself. Then \(\{\mathrm{id}_V\}\) is a basis of size \(1\); but defining \(f, g \in R\) by \(f(e_{2n}) = e_n\), \(f(e_{2n+1}) = 0\) and \(g(e_{2n+1}) = e_n\), \(g(e_{2n}) = 0\), the pair \(\{f, g\}\) is also a basis of the same module (Problem 5 verifies this in full). One free module, bases of sizes \(1\) and \(2\): the exchange argument dies at Step 5, where it must divide by a scalar.
"Basis" weakened to "spanning set". In \(\mathbb{R}^2\), the sets \(\{(1,0),(0,1)\}\) and \(\{(1,0),(0,1),(1,1)\}\) both span, with \(2 \neq 3\) elements. Weakened to "independent set": \(\{(1,0)\}\) and \(\{(1,0),(0,1)\}\) are both independent, with \(1 \neq 2\) elements. Equicardinality is a property of maximal independent = minimal spanning sets only.
Finite combinations replaced by convergent series. In the Hilbert space \(\ell^2\), the standard unit vectors \((e_n)_{n \in \mathbb{N}}\) form a countable orthonormal (Schauder-type) basis, yet every Hamel basis of \(\ell^2\) is uncountable (a Baire-category argument shows an infinite-dimensional Banach space cannot have countable Hamel dimension). Conflating the two notions of basis produces contradictory "dimensions" for the same space.
Axiom of Choice dropped. In ZF alone the infinite case is unprovable: there are models of ZF containing a vector space with two bases of different cardinalities, and models where cardinal comparability fails so the Schröder–Bernstein endgame cannot even be set up in the usual way. (In ZF one still has the finite case, which is choice-free.)

Common errors

Circular dimension. Invoking "\(\dim V = n\)" inside a proof of this theorem (e.g. "the basis has \(\dim V\) elements, done"). Dimension is only defined once this theorem is proved; any argument using \(\dim\) here is circular.
Exchange lemma with the roles reversed. The lemma bounds the independent set by the spanning set: independent \(\le\) spanning. Students routinely write it the wrong way round and "prove" that spanning sets are small.
Assuming both sets are bases in the lemma. Steinitz needs only: one set independent, the other spanning. Requiring both to be bases makes the finite-case deduction in Step 7 impossible to run (you need it for arbitrary finite subsets of \(C\)).
"Some \(b_j \neq 0\)" waved through. Step 4 is where linear independence is actually used, and it also silently proves \(k \lt n\). Omitting it leaves the proof with a possible division by zero and an unjustified reindexing.
Infinite case by "just count". Writing \(|B| = |C|\) "because both are infinite" is false reasoning: infinite cardinals come in many sizes (\(\mathbb{Q}\)-dimension of \(\mathbb{R}\) is \(2^{\aleph_0}\), not \(\aleph_0\)). The support argument of Steps 8–10 is genuinely needed.
Believing the converse. "It has \(n = \dim V\) vectors, so it's a basis." False without independence or spanning: \(\{(1,0),(2,0)\}\) in \(\mathbb{R}^2\).

Discussion

The theorem is the reason the word "dimension" means anything. Historically, the finite exchange argument goes back to Hermann Grassmann's Ausdehnungslehre (1844, largely unread in its time) and was isolated in the clean form used above by Ernst Steinitz in his 1913 work on field theory; Georg Hamel had already (1905) used Zorn-free well-ordering arguments to produce a basis of \(\mathbb{R}\) over \(\mathbb{Q}\) — the first "Hamel basis" — making the infinite case urgent. The modern proof of the infinite case, with its support-counting argument, is essentially an exercise in cardinal arithmetic layered on top of one honest linear-algebra idea: a basis is simultaneously a maximal independent set and a minimal spanning set, and the exchange property forces all such extremal sets to the same size.

That last remark is the door to a substantial generalisation. The Exchange Lemma is the defining axiom of a matroid: any finite structure with an "independence" notion satisfying the exchange property has all its maximal independent sets equinumerous — this common size is the rank of the matroid. Invariance of dimension is thus the vector-space instance of a purely combinatorial phenomenon that also covers spanning trees of a graph (all spanning trees of a connected graph have the same number of edges) and transcendence bases of a field extension (all transcendence bases have the same cardinality, giving transcendence degree). Steinitz proved the latter too, by the same exchange technique.

In ring theory the theorem's failure is itself a subject. A ring \(R\) has invariant basis number (IBN) if \(R^m \cong R^n\) as \(R\)-modules forces \(m = n\). Fields have IBN (this theorem); so do all nonzero commutative rings and all Noetherian rings — but \(\operatorname{End}_F(V)\) for infinite-dimensional \(V\) does not, as the "Fails without" example shows. The Leavitt algebras \(L(1,n)\) are universal examples of IBN failure and now feed into operator algebras via graph \(C^*\)-algebras. So the humble question "do all bases have the same size?" turns out to draw a genuine dividing line across algebra.

Foundationally, the infinite case sits at a precisely calibrated strength. The existence of a basis for every vector space is equivalent to the Axiom of Choice over ZF (Blass, 1984). Invariance of cardinality for bases that happen to exist is weaker but still not a ZF theorem: Läuchli constructed ZF-models with a vector space having bases of different cardinalities. The two uses of choice in Step 10 — selecting a "witnessing" \(b\) for each \(c \in C\), and the identity \(\aleph_0 \cdot \kappa = \kappa\) — can be reorganised but not eliminated. By contrast the finite case is a theorem of very weak arithmetic; nothing beyond finite induction is used. A well-run course should be honest that "dimension" for infinite-dimensional spaces is a choice-flavoured notion.

Common misconceptions. (i) "Invariance of dimension" here is an algebraic statement about bases; it is not Brouwer's topological invariance-of-dimension theorem (\(\mathbb{R}^n\) not homeomorphic to \(\mathbb{R}^m\) for \(n \neq m\)), which is far deeper and needs algebraic topology — the linear theorem only rules out linear isomorphisms. (ii) The theorem does not say a basis exists (that is a separate theorem, via Zorn's Lemma); it says all bases that exist are equinumerous. (iii) "Infinite-dimensional" is not one size: \(\dim_{\mathbb{Q}} \mathbb{R} = 2^{\aleph_0}\) while \(\dim_{\mathbb{Q}}\) of the polynomial ring \(\mathbb{Q}[x]\) is \(\aleph_0\), and the theorem is exactly what makes such statements meaningful.

Worked examples

Example 1. \(\mathbb{R}^n \cong \mathbb{R}^m\) as vector spaces implies \(n = m\). Suppose \(T \colon \mathbb{R}^n \to \mathbb{R}^m\) is a linear isomorphism.

The image \(T(E) = \{T e_1, \dots, T e_n\}\) of the standard basis \(E = \{e_1, \dots, e_n\}\) of \(\mathbb{R}^n\) is linearly independent in \(\mathbb{R}^m\).

If \(\sum_i c_i \, T e_i = 0\) then \(T\left(\sum_i c_i e_i\right) = 0\) by linearity, so \(\sum_i c_i e_i \in \ker T = \{0\}\) since \(T\) is injective; independence of \(E\) forces all \(c_i = 0\). A

\(T(E)\) spans \(\mathbb{R}^m\).

Given \(w \in \mathbb{R}^m\), surjectivity gives \(v \in \mathbb{R}^n\) with \(T v = w\); writing \(v = \sum_i c_i e_i\) and applying \(T\) gives \(w = \sum_i c_i \, T e_i\). Hence \(T(E)\) is a basis of \(\mathbb{R}^m\) with exactly \(n\) elements (\(T\) injective, so \(|T(E)| = n\)). A

\(\mathbb{R}^m\) now has two bases: \(T(E)\) with \(n\) elements and the standard basis with \(m\) elements. By invariance of dimension, \(n = m\).

This is precisely the theorem: any two bases of \(\mathbb{R}^m\) are equinumerous. Note the theorem is doing all the work — without it, nothing stops one space from having bases of two different sizes. B

\[ \mathbb{R}^n \cong \mathbb{R}^m \iff n = m. \]

Reading. Linear algebra can tell \(\mathbb{R}^2\) and \(\mathbb{R}^3\) apart: the number of coordinates is an isomorphism invariant.

Scope. The same argument works verbatim for \(F^n \cong F^m\) over any field \(F\), and for arbitrary spaces: isomorphic spaces have equal dimension.

Example 2. The solution space of the Fibonacci recurrence. Let \(V = \{ (a_n)_{n \ge 0} \in \mathbb{R}^{\mathbb{N}} : a_{n+2} = a_{n+1} + a_n \ \forall n \}\), a subspace of the space of real sequences (closure under sums and scalar multiples is immediate from the linearity of the recurrence). Let \(\Phi = (0, 1, 1, 2, 3, 5, \dots)\) be the Fibonacci sequence and \(\Lambda = (2, 1, 3, 4, 7, 11, \dots)\) the Lucas sequence, both in \(V\). We show \(\{\Phi, \Lambda\}\) is a basis of \(V\), so every solution is a unique combination of them.

The map \(\varphi \colon V \to \mathbb{R}^2\), \(\varphi\left((a_n)\right) = (a_0, a_1)\), is a linear isomorphism; hence \(V\) has a basis of \(2\) elements, and by invariance of dimension \(\dim V = 2\).

Linearity is clear. Injectivity: if \(a_0 = a_1 = 0\), induction with \(a_{n+2} = a_{n+1} + a_n\) gives \(a_n = 0\) for all \(n\). Surjectivity: given \((x, y) \in \mathbb{R}^2\), define \(a_0 = x\), \(a_1 = y\), \(a_{n+2} = a_{n+1} + a_n\) by recursion — this constructs a preimage. As in Example 1, \(\varphi^{-1}\) carries the standard basis of \(\mathbb{R}^2\) to a basis of \(V\) of size \(2\); the theorem then fixes the size of every basis of \(V\) at \(2\). B

\(\{\Phi, \Lambda\}\) is linearly independent in \(V\).

Suppose \(\alpha \Phi + \beta \Lambda = 0\) in \(V\). Comparing entries \(n = 0\) and \(n = 1\): \(2\beta = 0\) and \(\alpha + \beta = 0\), so \(\beta = 0\), then \(\alpha = 0\). (Equivalently \(\varphi(\Phi) = (0,1)\), \(\varphi(\Lambda) = (2,1)\) are independent in \(\mathbb{R}^2\) and \(\varphi\) is injective.) A

An independent set of size \(2 = \dim V\) in \(V\) is a basis; hence \(\{\Phi, \Lambda\}\) is a basis of \(V\).

This is the corollary "independent set of size \(\dim V\) is a basis" (proved in Problem 4), which rests on invariance of dimension: if \(\{\Phi, \Lambda\}\) failed to span, some \(v \notin \operatorname{span}\{\Phi, \Lambda\}\) would extend it to an independent set of \(3\) elements, exceeding the size \(2\) of a basis — impossible by the Exchange Lemma. B

\[ (a_n) \text{ solves } a_{n+2} = a_{n+1} + a_n \iff (a_n) = \alpha\, \Phi + \beta\, \Lambda \ \text{ for unique } \alpha, \beta \in \mathbb{R}. \]

Reading. Two independent particular solutions of a second-order linear recurrence automatically generate all solutions — because the solution space has dimension exactly \(2\), and that number is basis-independent.

Scope. The same dimension count powers the general theory of linear recurrences and linear ODEs of order \(k\): the solution space has dimension \(k\), so \(k\) independent solutions always suffice.

Problems

Show that every basis of \(F^n\) has exactly \(n\) elements, so \(\dim_F F^n = n\).
Solution
The standard vectors \(e_1, \dots, e_n\) (with \(e_i\) having \(1\) in slot \(i\), \(0\) elsewhere) form a basis: if \(\sum c_i e_i = 0\) then reading off coordinate \(i\) gives \(c_i = 0\) (independence), and any \((x_1, \dots, x_n) = \sum x_i e_i\) (spanning). So \(F^n\) possesses a basis of \(n\) elements. By invariance of dimension, every basis of \(F^n\) is equinumerous with this one, hence has exactly \(n\) elements, and \(\dim_F F^n = n\).
Prove directly from the Exchange Lemma: every linearly independent subset of \(\mathbb{R}^3\) has at most \(3\) elements, and every spanning subset of \(\mathbb{R}^3\) has at least \(3\) elements.
Solution
Let \(L\) be independent. Any finite subset \(L_0 \subseteq L\) is independent, and \(S = \{e_1, e_2, e_3\}\) spans \(\mathbb{R}^3\), so the Exchange Lemma gives \(|L_0| \le 3\); hence \(L\) itself is finite with \(|L| \le 3\). Now let \(S'\) span \(\mathbb{R}^3\). If \(S'\) were finite with \(|S'| \le 2\), apply the Exchange Lemma with independent set \(\{e_1, e_2, e_3\}\) and spanning set \(S'\): it gives \(3 \le |S'| \le 2\), a contradiction. So every spanning set has at least \(3\) elements (infinite spanning sets satisfy this trivially).
Prove that the polynomial space \(\mathbb{R}[x]\) has no finite basis, and exhibit a countable basis. Conclude \(\dim_{\mathbb{R}} \mathbb{R}[x] = \aleph_0\).
Solution
Suppose \(\mathbb{R}[x]\) had a finite spanning set \(S\), \(|S| = n\). The set \(\{1, x, x^2, \dots, x^n\}\) is linearly independent: a relation \(\sum_{k=0}^{n} c_k x^k = 0\) is the zero polynomial, and a polynomial is zero exactly when all its coefficients vanish, so every \(c_k = 0\). The Exchange Lemma then gives \(n + 1 \le n\), absurd. Hence no finite spanning set, and in particular no finite basis. The set \(\{x^k : k \in \mathbb{N}\}\) is a basis: it is independent by the same coefficient argument (any finite relation involves finitely many powers), and it spans because a polynomial is by definition a finite linear combination of powers of \(x\). This basis is countably infinite, so by invariance of dimension every basis of \(\mathbb{R}[x]\) has cardinality exactly \(\aleph_0\): \(\dim_{\mathbb{R}} \mathbb{R}[x] = \aleph_0\).
Let \(\dim_F V = n\) be finite and let \(L \subseteq V\) be linearly independent with \(|L| = n\). Prove that \(L\) is a basis of \(V\).
Solution
Write \(L = \{v_1, \dots, v_n\}\) and suppose, for contradiction, that \(L\) does not span \(V\); pick \(v \in V \setminus \operatorname{span}(L)\). We claim \(L \cup \{v\}\) is independent: if \(c v + \sum_i c_i v_i = 0\) with not all coefficients zero, then \(c \neq 0\) (otherwise the relation is a nontrivial dependence in \(L\), contradicting independence), so \(v = -c^{-1} \sum_i c_i v_i \in \operatorname{span}(L)\) — contradicting the choice of \(v\); note the inversion of \(c\) uses that \(F\) is a field. So \(L \cup \{v\}\) is an independent set of \(n + 1\) elements. But \(V\) has a basis \(S\) with \(|S| = n\) (this is where \(\dim V = n\), i.e. invariance of dimension, is used: the number \(n\) is unambiguous), and \(S\) spans, so the Exchange Lemma forces \(n + 1 \le n\), absurd. Hence \(L\) spans, and being independent, \(L\) is a basis.
(Harder.) Let \(V\) be an \(F\)-vector space with basis \((e_n)_{n \in \mathbb{N}}\) and let \(R = \operatorname{End}_F(V)\), regarded as a left module over itself via composition, \(r \cdot s := r \circ s\). Define \(f, g \in R\) on the basis by \[ f(e_{2n}) = e_n, \quad f(e_{2n+1}) = 0, \qquad g(e_{2n}) = 0, \quad g(e_{2n+1}) = e_n. \] Show that \(\{\mathrm{id}_V\}\) and \(\{f, g\}\) are both bases of the left \(R\)-module \(R\), and explain exactly which step of the proof of invariance of dimension fails for \(R\).
Solution
\(f\) and \(g\) are well defined: a linear map may be prescribed arbitrarily on a basis (universal property of bases). \(\{\mathrm{id}_V\}\) is a basis: spanning, since every \(r \in R\) equals \(r \circ \mathrm{id}_V = r \cdot \mathrm{id}_V\); independent, since \(r \cdot \mathrm{id}_V = r = 0\) forces \(r = 0\). \(\{f, g\}\) spans: given \(h \in R\), define \(a, b \in R\) on the basis by \(a(e_n) = h(e_{2n})\) and \(b(e_n) = h(e_{2n+1})\). Then for every \(n\), \((a \circ f + b \circ g)(e_{2n}) = a(e_n) + 0 = h(e_{2n})\) and \((a \circ f + b \circ g)(e_{2n+1}) = 0 + b(e_n) = h(e_{2n+1})\); two linear maps agreeing on a basis are equal, so \(h = a \cdot f + b \cdot g\). \(\{f, g\}\) is independent: if \(a \cdot f + b \cdot g = 0\) then evaluating at \(e_{2n}\) gives \(a(e_n) = 0\) for all \(n\), so \(a = 0\) (zero on a basis), and evaluating at \(e_{2n+1}\) gives \(b(e_n) = 0\) for all \(n\), so \(b = 0\). Hence the free left \(R\)-module \(R\) has bases of cardinalities \(1\) and \(2\): \(R\) does not have invariant basis number, and indeed \(R \cong R \oplus R\) as left \(R\)-modules (send \(h \mapsto (a, b)\) as above). Where the proof breaks: Step 5 of the main proof solves for a vector by multiplying by \(b_{k+1}^{-1}\); in \(R\) the "scalars" are endomorphisms, and a nonzero endomorphism of an infinite-dimensional space need not be invertible (e.g. \(f\) above is surjective but not injective). Without division, the exchange cannot be performed, and with it falls the entire counting argument. This is consistent with the theorem, whose hypotheses require the scalars to form a field.