Axiom of Choice and Well Ordered Sets

Let \(A\) be a well-ordered set. Let \(S \subset A\), \(S \ne \emptyset\), and \(S\) is bounded above. Note that since \(A\) is well-ordered and \(S\) is a subset of \(A\) nor is it empty, \(S\) has a smallest element (which we denote \(x\)). Then, \(x\) is the greatest lower bound for \(S\). Since \(S\) is an arbitrary set, we have shown that every nonempty subset of \(S\) has the greatest lower bound property. By a theorem proven about the least upper bound property, it follows that the greatest lower bound property implies the least upper bound property. Hence, \(A\) has the least upper bound property.

Suppose \(A\) is a simply ordered set that is not well-ordered. There exists a nonempty subset \(S\) so that \(S\) has no smallest element. If \(S\) is finite, it would be well-ordered since every nonempty finite ordered set has the order type of a section of the positive integers, which contradicts the fact that \(S\) is not well-ordered. So, \(S\) is infinite. By axiom of choice, we can define a function \(f: \mathbb{Z} \rightarrow S_*\) as follows: choose \(x_1 \in S\) arbitrarily. Let \(f(-1) = x_1\). Since \(S\) is infinite and \(S\) has no smallest element, choose \(x_2 < x_1\) (where \(<\) refers to the simple order on \(A\)) and let \(f(-2) = x_2\). In general, define \(f(-1) = x_1\) and \(f(-n) = \text{ choose arbitrary } x_n \in S \setminus \{x_1, ..., x_{n-1}\}\) for all \(n > 1\) so that \(x_n < x_{n-1} < ... < x_1\). Also, let \(S_* = \{x_n\}_{n=1}^\infty\). Then, \(f\) is an order-preserving bijection. Since \(S_* \subset S \subset A\), it follows that \(S_*\) is a subset of \(A\) that has the same order type as \(\mathbb{Z}_{-}\). Now, we prove the converse. Suppose that there exists a subset of \(A\) having the same order type as \(\mathbb{Z}\), called \(S\). Then, there exists an order-preserving bijection \(f: S \rightarrow \mathbb{Z}_{-}\). Suppose for contradiction that \(S\) has a smallest element, \(a\). Then, for every \(s \in S\), \(a \le s\) (where \(\le\) refers to the order relation on \(A\)). So, \(f(a) \le f(s)\) for all \(s \in S\). Since \(f(S) = \mathbb{Z}_{-}\), that means \(f(a) \le n\) for all \(n \in \mathbb{Z}_{-}\). This would imply that \(\mathbb{Z}_{-}\) has a smallest element, \(f(a)\). This would contradict the fact \(\mathbb{Z}_{-}\) is not well-ordered, so \(A\) fails to be well ordered.

Let \(S \subset A\) and \(S \ne \emptyset\). If \(S\) is countable, we know it is well-ordered, so we are done. Suppose \(S\) is uncountable. Suppose for contradiction that \(S\) fails to be well-ordered. Then, by Theorem 7, there exists \(T \subset S\) so that \(T\) has the same order type as \(\mathbb{Z}_{-}\). This means there is an order-preserving bijection between \(T\) and \(\mathbb{Z}_{-}\), implying that \(T\) is countable. Then, since \(T \subset S \subset A\), \(T\) is well-ordered since every countable subset of \(A\) is well-ordered. But this contradicts the fact that \(\mathbb{Z}_{-}\) is not well-ordered.

Let \(\mathcal{A}\) be a collection of disjoint nonempty sets. Let \(B = \cup_{A \in \mathcal{A}} A\). By the well-ordering theorem, there exists an order-relation, \(<_B\), that is a well-ordering. For each \(A \in \mathcal{A}\), \(A\) is non-empty, so there exists a smallest element \(x_A\) under the order relation \(<_B\). Let \(C = \cup_{A \in \mathcal{A}} \{x_A\}\). For two sets \(A\) and \(A'\) contained in \(\mathcal{A}\), \(x_A \ne x_{A'}\) (since \(A\) and \(A'\) are disjoint) and \(C \cap A\) has one element for every \(A \in \mathcal{A}\). Also, \(C \subset B\).

Suppose for contradiction that \(J_0 \ne J\). Then, since \(J_0 \subset J\), there exists \(x \in J\) such that \(x \not\in J_0\). This means that \(J \setminus J_0 \ne \emptyset\). Since \(J\) is well-ordered, \(J - J_0\) is well-ordered, and there exists a smallest element \(\alpha \in J - J_0\). Consider \(S_\alpha\). Consider \(\alpha' \in S_\alpha\). Then, \(\alpha' \not\in J - J_0\), since then \(\alpha' < \alpha\) is the smallest element of \(J - J_0\), which contradicts the fact that \(\alpha\) is the smallest element of \(J - J_0\). Since \(S_\alpha \subset J\), \(\alpha' \in J\), so \(\alpha' \in J_0\). Since \(\alpha'\) was arbitrary, \(S_\alpha \subset J_0\). Since \(J_0\) is inductive, that means \(\alpha \in J_0\). But this contradicts the fact that \(\alpha \in J - J_0\). So, the initial assumption was wrong, and \(J_0 = J\).

Let \(h: D \rightarrow C\) and \(k: E \rightarrow C\) where \(D\) is a section of \(J\) or all of \(J\) and \(E\) is a section of \(J\) or all of \(J\). It is clear that \(D \cap E\) is either a section of \(J\) or \(J\) itself. Suppose \(h(x) = \text{smallest}[C - h(S_x)]\) and \(k(x) = \text{smallest}[C - k(S_x)]\). By hypothesis, there exists no surjective function mapping a section of \(J\) into \(C\), so \(h(S_x) \ne C\) and \(C - h(S_x) \ne \emptyset\). Similarly, \(C - k(S_x) \ne \emptyset\). Since \(C\) is well-ordered, \(C - h(S_x)\) and \(C - k(S_x)\) are well-ordered and they both have a smallest element. So, \(h(x)\) and \(k(x)\) are both well-defined. Let \(F = D \cap E\). Since \(F \subset J\) and \(J\) is well-ordered, \(F\) is well-ordered. Then, there exists a smallest element \(\alpha \in F\). Since \(F\) is either a section of \(J\) or \(J\) itself, this smallest element \(\alpha\) is the smallest element of \(J\). Then, \(S_\alpha \ne \emptyset\) and $h(α) = \text{smallest element of \(C\)} = k(α)$. Suppose for contradiction that there exists \(x \in F\) so that \(h(x) \ne k(x)\). Let \(X = \{x \in F: h(x) \ne k(x)\}\). Since \(X \subset F\), \(X\) is well-ordered, and there exists a smallest element \(x_0 \in X\). Clearly, \(x_0 \ne \alpha\), and since \(\alpha\) is the smallest element of \(J\), it follows that \(\alpha < x_0\). For all \(x \in F\) where \(x < x_0\), \(h(x) = k(x)\). Then, \(h(x_0) = \text{smallest element of} [C - h(S_{x_0})]\) and \(k(x_0) = \text{smallest element of} [C - k(S_{x_0})]\). Since \(h(S_{x_0}) = k(S_{x_0})\) and the smallest element is unique, \(h(x_0) = k(x_0)\), contradicting the initial assumption. So, \(h(x) = k(x)\) for all \(x \in F\).

Define \(k: S_\alpha \cup \{\alpha\} \rightarrow C\) so that \(k(x) = h(x)\) for all \(x \in S_\alpha\) and \(k(\alpha) = \text{smallest element} [C - h(S_x)]\). Let \(X = \{x \in S_\alpha: k(x) \text{ does not satisfy } (\star) \}\). Then, since \(X \subset X_\alpha \subset J\), \(X\) is well-ordered, so there exists a smallest element \(\alpha_0 \in X\). Since \(S_\alpha = \{x \in J: x < \alpha\}\), \(S_\alpha\) is well-ordered and the smallest element of \(S_\alpha\), \(\alpha_0\), is also the smallest element of \(J\). Then, \(S_{\alpha_0} = \emptyset\) and \(k(\alpha_0) = h(\alpha_0) = \text{smallest element of } C\). So, \(k\) satisfies \((\star)\) at \(\alpha_0\). Then, \(x_0 \ne \alpha_0\), since \(k\) does not satisfy \((\star)\) at \(x_0\). For all \(x < x_0\), \(k\) does satisfy \((\star)\) at \(x\). That is, \(k\) does satisfy \((\star)\) for all \(x \in S_{x_0}\). Also, \(k(x) = h(x)\) for all \(x \in S_{x_0}\). So, \(k(S_{x_0}) = h(S_{x_0})\). Then, \(k(x_0) := h(x_0) = \text{smallest element of} [C - h(S_{x_0})] = \text{smallest element of} [C - k(S_{x_0})]\). So, \(k\) satisfies \((\star)\) for \(x_0\), which contradicts the fact \(k\) doesn't satisfy \((\star)\) at \(x_0\). So, \(k\) satisfies \((\star)\) for all \(x \in S_\alpha\). For \(x = \alpha\), \(k(\alpha) := \text{smallest element} [C - h(S_\alpha)]\). We know \(h(S_\alpha) = k(S_\alpha)\), so \(k(\alpha) = \text{smallest element} [C - k(S_\alpha)]\).

Define \(k: \cup_{\alpha \in K} S_\alpha \rightarrow C\) so that \(k(x) := h_{\alpha_0}(x)\) where \(\alpha_0\) is the smallest element of \(K\) for which \(x \in S_{\alpha_0} \cup \{\alpha_0\}\). Since \(K \subset J\), \(K\) is well-ordered, so there exists a smallest element. Furthermore, if \(\alpha_1 < \alpha_2\), then \(S_{\alpha_1} \subset S_{\alpha_2}\). These facts imply that there exists a smallest \(\alpha_0\) in \(K\) for which \(x \in S_{\alpha_0}\) and \(x \not\in S_\alpha\) for any other \(\alpha \in K\). That is, the set \(\{\alpha \in K: x \in S_\alpha\}\) has a smallest element. So, \(k\) is well-defined. We now show \(k\) satisfies \((\star)\). Suppose there exists \(x \in \bigcup_{\alpha \in K} S_\alpha\) so that \((\star)\) is not satisfied. Let \(\beta\) be the smallest element of \(\cup_{\alpha \in K} S_\alpha\). Then, \(k(\beta) = h_\beta(\beta) = \text{smallest element of } C\) since \(S_\beta = \emptyset\). So, \(x \ne \beta\). Then, the set \(\{x \in \bigcup_{\alpha \in K}: k(x) \text{ does not satisfy } (\star)\}\) has a smallest element \(x_0 > \beta\). For all \(x < x_0\), \(k(x)\) does satisfy \((\star)\). Then, \(k(x) = h_x(x)\) for all \(x \in S_{x_0}\). So, \(k(S_{x_0}) = h_{x_0}(S_{x_0})\). Then, \(k(x_0) = h_{x_0}(x_0) = \text{ smallest element } [C - h_{x_0}(S_{x_0})] = \text{ smallest element } [C - k(S_{x_0})]\). So, \(k\) satisfies \((\star)\) at \(x_0\). This contradicts the fact that \(k\) does not satisfy \((\star)\) at \(x_0\). So, \(k: \bigcup_{\alpha \in K} S_\alpha \rightarrow C\) satisfies \((\star)\).

Let \(J_0 = \{\alpha \in J: \text{ there exists } h_\alpha: S_\alpha \rightarrow C \text{ satisfying } (\star)\}\). We know from Lemma 13 that there exists \(h_{\alpha_0}: \{\alpha_0\} \rightarrow C\) satisfying \((\star)\), namely, the one that assigns \(h(\alpha_0) = \text{ smallest element of } C\), where \(\alpha_0\) is the smallest element of \(J\). Therefore, \(J_0 \ne \emptyset\). Let \(\beta \in J\). Suppose \(S_\beta \subset J_0\). We show \(\beta \in J_0\). Suppose \(\beta\) has an immediate predecessor \(\alpha\). Then, \(S_\beta = S_\alpha \cup \{\alpha\}\). Since \(\alpha \in S_\beta\), \(\alpha \in J_0\), so there exists \(h_\alpha: S_\alpha \rightarrow C\) satisfying \((\star)\). By Lemma 13, there exists \(k: S_\alpha \cup \{\alpha\} \rightarrow C\) satisfying \((\star)\). That is, there exists \(k: S_\beta \rightarrow C\) satisfying \((\star)\). So, \(\beta \in J_0\). Now suppose that \(\beta\) does not have an immediate predecessor. Then, \(S_\beta = \cup_{\{\alpha \in J_0: \alpha < \beta\}} S_\alpha\). Let \(K \subset J_0\). Then, for every \(\alpha \in K\), there exists \(h_\alpha: S_\alpha \rightarrow C\) satisfying \((\star)\). That is, there exists \(k: S_\beta \rightarrow C\) satisfying \((\star)\). So, \(\beta \in J_0\). Therefore, \(J_0\) is an inductive set. Since \(J\) is well-defined, \(J_0 = J\) by The Principle of Transfinite Induction. So, for every \(\beta \in J\), there exists \(h_\beta: S_\beta \rightarrow C\) satisfying \((\star)\).

By Lemma 15, for every \(\beta \in J\), there exists \(h_\beta: S_\beta \rightarrow C\) satisfying \((\star)\). Every element of \(J\) has an immediate successor or is the largest element of \(J\). Let \(x \in J\). If \(x\) has an immediate successor, \(y\), then we can let \(h(x) = h_y(x)\), where \(h_y: S_y \rightarrow C\) satisfies \((\star)\). If \(x\) is the largest element of \(J\), we can define \(h(x) = \text{smallest element} [C - h(S_x)]\). Since \(h\) is not surjective, \(C - h(S_x)\) is nonempty, so \(h\) is well-defined. It is clear \(h\) satisfies \((\star)\) for the largest element of \(J\) (if it exists). Let \(x \in J\) not be the largest element. Then, it has an immediate successor \(y\), so that \(h(x) = h_y(x)\). We have:

\begin{align*} h(S_x) &= \{z < x: h(z)\} \\ &= \{z < z' < x, z' \text{ is immediate successor }: h_{z'}(z)\} \end{align*}

And:

\begin{align*} h_y(S_x) &= \{z < x: h_y(z)\} \\ \end{align*}

For all \(z < x\), \(h_y\) satisfies \((\star)\) at \(z\) and \(h_{z'}\) satisfies \((\star)\) at \(z\) (where \(z'\) is the immediate successor of \(z\)). So, by Lemma 12, \(h_{z'}(z) = h_y(z)\). This implies \(h(z) = h_y(z)\). Then, \(h(S_x) = h_y(S_x)\) and \(h\) satisfies \((\star)\) for all \(x \in J\). For any other \(k\) satisfying \((\star)\) on \(J\) or a section of \(J\), \(h(x) = k(x)\), so \(h: J \rightarrow C\) is unique by Lemma 12.

First, suppose there exists a bijection between \(A\) and \(B\). Then, by definition, they are of the same cardinality. Now, suppose that \(A\) and \(B\) are not of the same cardinality. Suppose for contradiction that \(A\) is not of greater cardinality than \(B\) and \(B\) is not of greater cardinality than \(A\). Then, for every map \(f: A \rightarrow B\), \(f\) is not an injection from \(A\) to \(B\) and for every map \(g: B \rightarrow A\), \(g\) is not an injection from \(B\) to \(A\). We consider four cases:

1. \(f\) is a surjection and \(g\) is a surjection
2. \(f\) is not a surjection and \(g\) is a surjection
3. \(f\) is a surjection and \(g\) is not a surjection
4. \(f\) is not a surjection and \(g\) is not a surjection

By The Maximum Principle, there exists a maximal simply ordered subset of \(A\), \(B\). Then, \(B\) has an upper bound, \(c \in A\), by hypothesis. Suppose for contradiction that \(A\) has no maximal element. Then, there exists \(a \in A\) for which \(c \prec a\). By transitivity, since \(b \prec a\) for all \(b \in B\). Then, the set \(B \cup \{a\}\) is a simply ordered set (comparability is not broken since there is no \(b \in B\) for which \(a \prec b\) holds, only \(b \prec a\) holds). However, \(B\) is a proper subset of \(B \cup \{a\}\), which violates the fact that it is a maximal simply ordered subset of \(A\).

Let \(\mathcal{B}\) be a subcollection of \(\mathcal{A}\) that is simply ordered by proper inclusion. Then, \(\bigcup_{B \in \mathcal{B}} B \in \mathcal{A}\) by hypothesis. For each \(B \in \mathcal{B}\), \(B \subset \bigcup_{B \in \mathcal{B}} B\) which is proper or \(B = \bigcup_{B' \in \mathcal{B}} B'\). Then, \(\cup_{B \in \mathcal{B}} B\) is an upper bound for \(\mathcal{B}\). By Zorn's Lemma, there exists a maximal element \(A \in \mathcal{A}\). That is, for every \(B \in \mathcal{A}\), the relation "\(A\) is a proper subset of \(B\)" does not hold. That is, \(A\) is properly contained in no other element of \(\mathcal{A}\).

Let \(\mathcal{B}\) be a subcollection of \(\mathcal{A}\), simply ordered by proper inclusion. Let \(C = \bigcup_{B \in \mathcal{B}} B\). We show \(C \in \mathcal{A}\). To do this, we show that every finite subset of \(C\) is in \(\mathcal{A}\). Let \(F\) be an arbitrary finite subset of \(C\). We show by induction on the cardinality of \(F\) that \(F \subset B\) for some \(B \in \mathcal{B}\). If this is the case, then since \(B \in \mathcal{A}\), every finite subset of \(B\) is in \(\mathcal{B}\), so \(F \in \mathcal{A}\), which would imply that \(C \in \mathcal{A}\). Let \(F_1\) be a subset of \(C\) of cardinality \(1\). Then, \(F_1 = \{x\} \subset C\). Then, \(x \in B\) for some \(B \in \mathcal{B}\). Since every finite subset of \(B\) is in \(\mathcal{A}\), \(\{x\} \in \mathcal{A}\). Now suppose for some \(n \in \mathcal{N}\), every finite subset of \(C\) of cardinality \(n\) is a subset of some \(B \in \mathcal{B}\). Let \(F\) be a finite subset of \(C\) of cardinality \(n + 1\). We show \(F \subset B\) for some \(B \in \mathcal{B}\). Suppose for contradiction, that \(F \not\subset B\) for every \(B \in \mathcal{B}\). Let \(x \in F\) be an arbitrary element. Then, write \(F = E \cup \{x\}\) where \(E = F \setminus \{x\}\). E is a finite subset of \(C\) of cardinality \(n\). By the inductive hypothesis, there exists \(B_1 \in \mathcal{B}\) so that \(E \subset B_1\). Since \(F \subset C\) but \(F \not\subset B_1\), there exists \(B_2 \in \mathcal{B}\) so that \(\{x\} \subset B_2\) and \(B_1 \ne B_2\) (we know that \(\{x\}\) is contained in some element of \(\mathcal{B}\) since we prove the base case for singletons). Since \(\mathcal{B}\) is simply ordered by proper inclusion, either \(B_1 \subset B_2\) or \(B_2 \subset B_1\). If \(B_1 \subset B_2\), then \(E \subset B_2\) and \(\{x\} \subset B_2\), so \(F = E \cup \{x\} \subset B_2\). But this contradicts that \(F \not\subset B\) for any \(B \in \mathcal{B}\). If \(B_2 \subset B_1\), then \(\{x\} \subset B_1\) and \(E \subset B_1\), so \(F = E \cup \{x\} \subset B_1\). But this contradicts the fact that \(F \not\subset B_1\) since \(B_1 \in \mathcal{B}\). Hence, the initial assumption was false, and there exists \(B \in \mathcal{B}\) so that \(F \subset B\). This finishes the inductive step, so every finite subset of \(C\) is contained in some \(B \in \mathcal{B}\). Then, \(C \in \mathcal{A}\) as discussed before. By Kuratowski's Lemma, \(\mathcal{A}\) has an element that is properly contained in no other element of \(\mathcal{A}\).

Let \(\prec\) be a strict partial order on \(A\) and let \(\mathcal{A}\) be the collection of all subsets of \(A\) that are simply ordered by \(\prec\). We show \(\mathcal{A}\) is of finite type. Let \(B \in \mathcal{A}\). We show that every finite subset of \(B \in \mathcal{A}\). Let \(F \subset B\) be a finite subset. Then, since \(B \in A\), \(F \subset A\). Since \(B\) is simply ordered by \(\prec\), \(F\) is also simply ordered by \(\prec\), so \(F \in \mathcal{A}\). Now suppose that every finite subset of \(B\) is contained in \(\mathcal{A}\). We show \(B \in \mathcal{A}\). First, suppose that \(B\) is finite. Then, \(B \subset B\) is a finite subset, so \(B \in \mathcal{A}\). Now, suppose \(B\) is infinite. First, let \(x \in B\). Then, \(\{x\} \in \mathcal{A}\), so \(\{x\}\) is simply ordered by \(\prec\). Then, the relation \(x \prec x\) does not hold. Since \(x \in B\) was arbitrary, \(x \prec x\) does not hold for any \(x \in B\). Let \(x, y \in B\) be 2 arbitrary elements. Then, \(\{x, y\} \in \mathcal{A}\), so \(\{x, y\}\) is simply ordered by \(\prec\). Then, \(x \prec y\) or \(y \prec x\). Let \(x, y, z \in B\) and suppose \(x \prec y\) and \(y \prec z\). Since \(\{x, y, z\} \in \mathcal{A}\), \(\{x, y, z\}\) is simply ordered by \(\prec\), so \(x \prec z\) by transitivity. Then, \(\prec\) is a simple ordering on \(B\), so \(B \in \mathcal{A}\). Since \(B\) was an arbitrary element of \(\mathcal{A}\), \(\mathcal{A}\) is of finite type, so Tukey's Lemma implies that \(\mathcal{A}\) has an element, \(C\), that is properly contained in no other element of \(\mathcal{A}\). Also, \(C\) is simply ordered by \(\prec\). So, \(C\) is a maximal simply ordered subset.

Suppose \(A \cup \{v\}\) is not independent. Then, there exists a finite collection of vectors \(\{\vec{v_k}\}_{k=1}^n\) so that \(\sum_{k=1}^n c_k \vec{v_k} = \vec{0}\), where \(c_k \ne 0\) for some \(1 \le k \le n\). Suppose \(\vec{v} \not\in \{\vec{v_k}\}_{k=1}^n\). Then, \(\vec{v_k} \in A\) for all \(1 \le k \le n\). By independence of \(A\), \(\sum_{k=1}^n c_k \vec{v_k} = \vec{0}\) only when \(c_k = 0\) for all \(1 \le k \le n\), which contradicts the assumption that \(c_k \ne 0\) for some \(1 \le k \le n\). Therefore, \(\vec{v} \in \{\vec{v_k}\}_{k=1}^n\). Without loss of generality, \(\vec{v_1} = \vec{v}\). Then, \(c_1 \ne 0\): if it were, then \(c_k \ne 0\) for some \(2 \le k \le n\). This would imply that \(\sum_{k=2}^n c_k \vec{v_k} = \vec{0}\) where \(c_k \ne 0\) for some \(2 \le k \le n\), which contradicts the independence of \(A\) since \(v_k \in A\) for all \(2 \le k \le n\). So:

\begin{align*} \sum_{k=1}^n c_k \vec{v_k} &= c_1 \vec{v_1} + \sum_{k=2}^n c_k \vec{v_k} = 0\\ &\implies \vec{v_1} = \sum_{k=2}^n \frac{c_k}{c_1} v_k \end{align*}

Then, \(\vec{v_1}\) is a finite linear combination of the \(\{v_k\}_{k=2}^n\), so \(v_1\) is in the span of \(A\), which contradicts the assumption that \(\vec{v_1} = \vec{v}\) is not in the span of \(A\). So, \(A \cup \{v\}\) is independent.

Let \(\mathcal{A}\) be a collection of all independent sets in \(V\). We show that \(\mathcal{A}\) is of finite type. Let \(B \in \mathcal{A}\). Since \(B\) is independent, for every finite subset \(F = \{\vec{v_1}, ..., \vec{v_n}\}\) of \(B\), \(\sum_{k=1}^n c_k \vec{v_k} = \vec{0}\) only whenever \(c_k = 0\) for all \(1 \le k \le n\). Then, for some \(1 \le m \le n\), \(\sum_{k=1}^m c_k \vec{v_k} = \vec{0}\) and \(c_k \ne 0\) for some \(1 \le k \le m\). Then, let \(c_k = 0\) for all \(m + 1 \le k \le n\). Then, \(\sum_{k=1}^n c_k \vec{v_k} = \vec{0}\) and \(c_k \ne 0\) for some \(1 \le k \le m \le n\). This contradicts the fact that \(\sum_{k=1}^n c_k \vec{v_k} = \vec{0}\) only whenever \(c_k = 0\) for all \(1 \le k \le n\). So, \(F\) is independent as every finite linear combination of elements of \(F\) that equals \(\vec{0}\) implies that \(c_k = 0\) for all \(1 \le k \le n\). Since \(F\) was arbitrary, every finite subset of \(B\) is in \(\mathcal{A}\). Now suppose that every finite subset of \(B\) is in \(\mathcal{A}\). We show that \(B \in \mathcal{A}\). For \(B\) to be independent, every finite linear combination of elements of \(B\) equals the zero vector only when all the coefficients are zero. Put another way, we require that for every finite subset \(F = \{\vec{v_1}, ..., \vec{v_n}\}\) of \(B\), \(\sum_{k=1}^n c_k \vec{v_k} = \vec{0}\) only when \(c_k = 0\) for all \(1 \le k \le n\). This is true since \(F \in \mathcal{A}\) (\(F\) is independent). So, \(B \in \mathcal{A}\). Then, \(\mathcal{A}\) is of finite type. By Tukey's Lemma (which we have shown is equivalent to Zorn's Lemma), it contains an element that is properly contained in no other element of \(\mathcal{A}\), i.e, a maximal element. Let \(C \in \mathcal{A}\) be this maximal element. Suppose \(C\) does not span \(V\). Then, there exists \(\vec{v} \in V\) so that $\vec{v} is not in the span of \(C\). Since \(C\) is independent, \(C \cup \{v\}\) is independent by Lemma 22. And, \(C \cup \{v\}\) properly contains \(C\). But \(C\) is the maximal element of \(\mathcal{A}\). This is a contradiction, so the initial assumption was false, and \(C\) spans \(V\). Consequently, \(C\) is a basis.