§ 7. Maximal Linearly Independent Subsets

Our principal goal in this section is to prove that every vector space has a basis. This result is important in the study of infinite-dimensional vector spaces because it is often difficult to construct an explicit basis for such a space. Consider, for example, the vector space of real numbers over the field of rational numbers. There is no obvious way to construct a basis for this space, and yet it follows from the results of this section that such a basis does exist.

The difficulty that arises in extending the theorems of the preceding section to infinite-dimensional vector spaces is that the principle of mathematical induction, which played a crucial role in many of the proofs of Section 6, is no longer adequate. Instead, a more general result called the maximal principle is needed.

Maximal Principle

Definition 7.1 : Maximal Set

Let \(\mathcal{F}\) be a family of sets. A member \(M\) of \(\mathcal{F}\) is called maximal (with respect to set inclusion) if \(M\) is contained in no member of \(\mathcal{F}\) other than \(M\) itself.

Example 7.2

Let \(\mathcal{F}\) be the family of all subsets of a nonempty set \(S\). (This family \(\mathcal{F}\) is called the power set of \(S\).) The set \(S\) is easily seen to be a maximal element of \(\mathcal{F}\).

Example 7.3

Let \(\mathcal{F}\) be the family of all finite subsets of an infinite set \(S\). Then \(\mathcal{F}\) has no maximal element. For if \(M\) is any member of \(\mathcal{F}\) and \(s\) is any element of \(S\) that is not in \(M\), then \(M \cup\{s\}\) is a member of \(\mathcal{F}\) that contains \(M\) as a proper subset.

Definition 7.4 : Chain of Sets

A collection of sets \(\mathcal{C}\) is called a chain (or nest or tower) if for each pair of sets \(A\) and \(B\) in \(\mathcal{C}\), either \(A \subseteq B\) or \(B \subseteq A\).

Definition 7.5 : Maximal Principle

Let \(\mathcal{F}\) be a family of sets. If, for each chain \(\mathcal{C} \subseteq \mathcal{F}\), there exists a member of \(\mathcal{F}\) that contains each member of \(\mathcal{C}\), then \(\mathcal{F}\) contains a maximal member.

Basis and Maximal Linearly Independent Subset

Definition 7.6 : Maximal Linearly Independent Subset

Let \(S\) be a subset of a vector space \(V\). A maximal linearly independent subset of \(S\) is a subset \(B\) of \(S\) satisfying both of the following conditions.

• (a) \(B\) is linearly independent.
• (b) The only linearly independent subset of \(S\) that contains \(B\) is \(B\) itself.

Theorem 7.7 : Basis is a maximal linearly independent subset.

A basis \(\beta\) for a vector space \(V\) is a maximal linearly independent subset of \(V\).

Proof

1. \(\beta\) is linearly independent by definition.
2. If \(v \in V\) and \(v \notin \beta\), then \(\beta \cup\{v\}\) is linearly dependent by Theorem 5.9 because \(\operatorname{span}(\beta)=V\).

Theorem 7.8 : Maximal linearly independent subset is a basis.

Let \(V\) be a vector space and \(S\) a subset that generates \(V\). If \(\beta\) is a maximal linearly independent subset of \(S\), then \(\beta\) is a basis for \(V\).

Proof

Let \(\beta\) be a maximal linearly independent subset of \(S\). Because \(\beta\) is linearly independent, it suffices to prove that \(\beta\) generates \(V\). We claim that \(S \subseteq \operatorname{span}(\beta)\), for otherwise there exists a \(v \in S\) such that \(v \notin \operatorname{span}(\beta)\). Since Theorem 5.9 implies that \(\beta \cup\{v\}\) is linearly independent, we have contradicted the maximality of \(\beta\). Therefore \(S \subseteq \operatorname{span}(\beta)\). Because \(\operatorname{span}(S)=V\), it follows from Theorem 4.3 that \(\operatorname{span}(\beta)=V\).

By Theorem 7.7 and Theorem 7.8, a subset of a vector space is a basis if and only if it is a maximal linearly independent subset of the vector space. Therefore we can accomplish our goal of proving that every vector space has a basis by showing that every vector space contains a maximal linearly independent subset.

Theorem 7.9 : Every vector space has a maximal linearly independent subset.

Let \(S\) be a linearly independent subset of a vector space \(V\). There exists a maximal linearly independent subset of \(V\) that contains \(S\).

Proof

Let \(\mathcal{F}\) denote the family of all linearly independent subsets of V that contain \(S\). In order to show that \(\mathcal{F}\) contains a maximal element, we must show that if \(\mathcal{C}\) is a chain in \(\mathcal{F}\), then there exists a member \(U\) of \(\mathcal{F}\) that contains each member of \(\mathcal{C}\). We claim that \(U\), the union of the members of \(\mathcal{C}\), is the desired set. Clearly \(U\) contains each member of \(\mathcal{C}\), and so it suffices to prove that \(U \in \mathcal{F}\) (i.e., that \(U\) is a linearly independent subset of \(V\) that contains \(S\)). Because each member of \(\mathcal{C}\) is a subset of V containing \(S\), we have \(S \subseteq U \subseteq V\). Thus we need only prove that \(U\) is linearly independent. Let \(u_{1}, u_{2}, \ldots, u_{n}\) be in \(U\) and \(a_{1}, a_{2}, \ldots, a_{n}\) be scalars such that \(a_{1} u_{1}+a_{2} u_{2}+\cdots+a_{n} u_{n}=0\). Because \(u_{i} \in U\) for \(i=1,2, \ldots, n\), there exists a set \(A_{i}\) in \(\mathcal{C}\) such that \(u_{i} \in A_{i}\). But since \(\mathcal{C}\) is a chain, one of these sets, say \(A_{k}\), contains all the others. Thus \(u_{i} \in A_{k}\) for \(i=1,2, \ldots, n\). However, \(A_{k}\) is a linearly independent set; so \(a_{1} u_{1}+a_{2} u_{2}+\cdots+a_{n} u_{n}=0\) implies that \(a_{1}=a_{2}=\cdots=a_{n}=0\). It follows that \(U\) is linearly independent.

The maximal principle implies that \(\mathcal{F}\) has a maximal element. This element is easily seen to be a maximal linearly independent subset of \(V\) that contains \(S\).

Corollary 7.10 : Every vector space has a basis.

Every vector space has a basis.

It can be shown, analogously to Corollary 6.6, that every basis for an infinite-dimensional vector space has the same cardinality. (Sets have the same cardinality if there is a one-to-one and onto mapping between them.)

Exercise

Exercise 7.3

Let \(V\) be the set of real numbers regarded as a vector space over the field of rational numbers. Prove that \(V\) is infinite-dimensional. Hint: Use the fact that \(\pi\) is transcendental, that is, \(\pi\) is not a zero of any polynomial with rational coefficients.

Exercise 7.4

Let \(W\) be a subspace of a (not necessarily finite-dimensional) vector space \(V\). Prove that any basis for \(W\) is a subset of a basis for \(V\).

Exercise 7.5

Prove the following infinite-dimensional version of Theorem 6.2: Let \(\beta\) be a subset of an infinite-dimensional vector space \(V\). Then \(\beta\) is a basis for \(V\) if and only if for each nonzero vector \(v\) in \(V\), there exist unique vectors \(u_{1}, u_{2}, \ldots, u_{n}\) in \(\beta\) and unique nonzero scalars \(c_{1}, c_{2}, \ldots, c_{n}\) such that \(v=c_{1} u_{1}+c_{2} u_{2}+\cdots+c_{n} u_{n}\).

Exercise 7.6

Prove the following generalization of Theorem 6.3: Let \(S_{1}\) and \(S_{2}\) be subsets of a vector space \(V\) such that \(S_{1} \subseteq S_{2}\). If \(S_{1}\) is linearly independent and \(S_{2}\) generates \(V\), then there exists a basis \(\beta\) for \(V\) such that \(S_{1} \subseteq \beta \subseteq S_{2}\). Hint: Apply the maximal principle to the family of all linearly independent subsets of \(S_{2}\) that contain \(S_{1}\), and proceed as in the proof of Theorem 7.9.

Exercise 7.7

Prove the following generalization of the replacement theorem (Theorem 6.5). Let \(\beta\) be a basis for a vector space \(V\), and let \(S\) be a linearly independent subset of \(V\). There exists a subset \(S_{1}\) of \(\beta\) such that \(S \cup S_{1}\) is a basis for \(V\).