Prove that Every Vector Space Has a Basis

Question

My textbook extended the following proof to show that every vector space, including the infinite-dimensional case, has a basis.

Condition: $S$ is a linearly independent subset of a vector space $V$.
Theorem: There is a maximal linearly independent subset of $V$ that contains $S$.

Proof. Let $F$ be the family of all linearly independent subsets of $V$ that contains $S$. If $C$ is a chain in $F$ and there exists a member $U \in F$ that contains each member of $C$, by the maximal principle, $U$ is the maximal element of $F$, the family of all linearly independent subsets of $V$. As a result, $U$ is the maximal linearly independent subset of $V$. So $U$ is the basis of $V$.

Let $U$ be the union of the elements of $C$. Clearly $U$ contains each element of $C$. To show that $U$ is a linearly independent subset of $V$, first note that $S \subset U$. Let $u_1, u_2, \ldots, u_n$ be vectors in $U$ and $c_1, c_2 ... c_n$ be scalars such that $0 = \sum_{i=1}^{n} {c_i}{u_i}$. Because $u_i \in U$ for all $i$, there exist sets $A_i$ in $C$ such that $u_i \in A_i$. Since $C$ is a chain, there is one set, say $A_k$, that contains all the others. So $u_1, u_2,\ldots, u_n \in A_k$. But since $A_k$ is linearly independent, $c_i = 0$ for all $i$. Therefore, $U$ is linearly independent. By the maximal principle, $U$ is the maximal element of $F$. $\square$

---

My questions are as follows:

1. Is the author arguing that since each vector space has a basis, the infinite-dimensional vector space also has a basis? This is similar to saying that $\lim_{n \rightarrow \infty} a_n = 0$ if $a_n = 0$ for all $n$.

2. How come the author is checking one chain $C \in F$ only? I thought that the maximal principle requires that the maximal element contains all members of each chains.

3. I am still not sure of how $u_1, u_2, \ldots, u_n$ are picked out. The greatest number of vectors in a linearly independent subset cannot exceed $\dim(V)$, but that is assuming that $V$ has a basis. So, how does the author know what the finite number $n$ is?

4. When the author is assigning $u_i$ to $A_i$, the set $\{A_i\}$ is not yet a chain. But the $A_i$ can be rearranged to form a chain. For example, $u_1 \in B_1$, $u_1, u_2 \in B_2,\ldots,$ and $u_1, u_2,\ldots, u_n \in B_n$.

Answer 1

If you quoted that accurately, it's a bit of a mess. The maximal principle actually says that there is a maximal chain $C$ in $F$, and that's the one that the author proceeds to consider. (There may of course be more than one, but any one of them will serve.) If $U\in F$ contains each member of $C$, then $C\cup\{U\}$ is a chain in $F$, and clearly $C\subseteq C\cup\{U\}$, so by the maximality of $C$ we must have $C=C\cup\{U\}$ and hence $U\in C$. Clearly, then, there cannot be any $M\in F$ such that $U\subsetneqq M$, since then $C\cup\{M\}$ would be a strictly larger chain than the maximal chain $C$. Thus, $U$ is a maximal element of $F$; in general it is not the maximal element of $F$, because in general $F$ has no unique maximal element.

The rest of the paragraph is better: it's simply a proof that if we set $U=\bigcup C$, then $U\in F$. Since obviously this $U$ contains each member of $C$, that establishes (by the argument above) that $U$ is a maximal element of $F$. Proving that $U\in F$ merely requires establishing that $U$ is linearly independent. To do this, we must show that every finite subset of $U$ is linearly independent: that's the definition of linear independence for infinite sets. The author's $\{u_1,\dots,u_n\}$ is simply an arbitrary finite subset of $U$. Then each $u_i$ belongs to some member $A_i$ of the chain $C$. Because $C$ is a chain, we know that these sets $A_1,\dots,A_n$ are nested, and there is no harm in assuming that we've numbered them so that $A_1\subseteq A_2\subseteq\ldots\subseteq A_n$. Then $\{u_1,\dots,u_n\}\subseteq A_n$, and $A_n$ is a linearly independent set, so $\{u_1,\dots,u_n\}$ is also linearly independent, as desired.

Answer 2

(1) The author is arguing the existence of a maximal linearly independent subset of a vector space $V$. His argument applies to any vector space, and it is irrelevant whether or not $V$ is finite-dimensional. He has not yet proved the existence of a basis, because an additional argument is necessary to prove that a maximal linearly independent subset of a vector space is in fact a basis.

(2) The chain $C$ is an arbitrary chain in $F$. The author's goal is to show that every chain in $F$ admits an upper bound in $F$. Zorn's lemma says that a non-empty partially ordered set admits a maximal element if every chain in the set admits an upper bound in the set.

(3) The author has constructed a set $U$, the union of the sets in $C$, and he is trying to show that it is an element of $F$. By definition, $F$ consists of all linearly independent subsets of $V$. So the author must show that the set $U$ which has been constructed is in fact linearly independent. What does linear independence mean? It means there are no non-trivial linear relations among the vectors in $U$. To show that this holds, one must take an arbitrary finite subset of $U$, say the subset consisting of the vectors $v_1,\ldots,v_n$, and prove that if there are scalars $c_1,\ldots,c_n$ with $\sum_i c_iv_i=0$, then $c_i=0$ for all $i$. These vectors are arbitrary elements of $U$. They are not "picked." The integer $n$ is just telling you the number of vectors in the subset of $U$. But this linear independence has to be verified for every finite subset of $U$, so every subset of cardinality $n$ for every integer $n\geq 0$. The integer $n$ is not chosen. It is just notation. This is how one checks linear independence. You can't talk about dimension because you haven't proved the existence of a basis yet.

(4) Each $u_i$ is in $U$, and $U$ is the union of the sets in $C$, so by definition, for each $i$, there is some set $A_i\in C$ such that $u_i\in A_i$. The chain is $C$, and the sets $A_i$ are elements of $C$.

Incidentally, perhaps I'm not understanding the formulation of Zorn's lemma being used, what is being called the maximal principle, but the second sentence in the excerpt, as well as the final sentence, do not make sense to me. Zorn's lemma allows one to conclude the existence of a maximal element by proving that every chain has an upper bound. The upper bound one proves exists is usually not going to be a maximal element of the set. The author proves that the set $U$ is an upper bound in $F$ for $C$, so by Zorn's lemma, there is a maximal element of $F$, but it need not have anything to do with $U$.

EDIT: Brian M. Scott's answer makes it clear to me what "version" of Zorn's lemma is being used, what is usually called the maximal principle. But the meat of the argument is the same whether you're trying to use Zorn's lemma or the maximal principle, and in either case, the second and last sentences of the excerpt do not make complete sense.

Answer 3

Here are some answers to your questions:

1. This is not like saying that if the limit is $0$ then all the elements of the sequences are zero. This is like saying that if all the natural numbers are rational numbers then in particular $0$ is a rational number.

   That is, we say that if all vector spaces have a basis, then infinitely dimensional vector spaces (which are in fact vector spaces) have a basis.

2. The author doesn't check for just one $C\subseteq F$ (not $\in$, by the way). We don't specify which $C$ we took; $C$ is arbitrary. Therefore this, if true, holds for all the chains in $F$.

   In the spirit of previous analogues, if we pick an arbitrary natural number $n$, and we show that $n$ is rational, then we may conclude that every natural number is rational.

3. No. We don't use a basis. We use the fact that if a set of vector is not linearly independent, then there is a finite subset which exhibits that. This is because by their definition linear combinations are finite combinations, so if there is a non-trivial linear combination which gives out $0$ it only involves a finite number of vectors.

4. Now, since we only have a finite number of vectors, and they all appear somewhere in our chain $C$, there is some $A_i\in C$ which contains them all. This is because $C$ is a chain, and $U$ is the union of all the sets in that chain. Therefore if $u_i\in U$ there is some $A_i\in C$ such that $u_i\in A_i$. Since we only have a finite number of relevant vectors, we can pick $A_i$ for each $u_i$.

   The collection $\{A_i\mid i=1,\ldots,n\}\subseteq C$. You should prove, in case you don't see it already, that a subset of a chain is a chain; and that a finite chain has a maximal element. Therefore we have some $A\in C$ such that $u_1,\ldots,u_n\in A$.