Editing Basis (linear algebra) (section)

==Proof that every vector space has a basis==

Let {{math|'''V'''}} be any vector space over some field {{math|'''F'''}}. Let {{math|'''X'''}} be the set of all linearly independent subsets of {{math|'''V'''}}.

The set {{math|'''X'''}} is nonempty since the empty set is an independent subset of {{math|'''V'''}}, and it is [[Partial order|partially ordered]] by inclusion, which is denoted, as usual, by {{math|⊆}}.

Let {{math|'''Y'''}} be a subset of {{math|'''X'''}} that is totally ordered by {{math|⊆}}, and let {{math|L<sub>'''Y'''</sub>}} be the union of all the elements of {{math|'''Y'''}} (which are themselves certain subsets of {{math|'''V'''}}).

Since {{math|('''Y''', ⊆)}} is totally ordered, every finite subset of {{math|L<sub>'''Y'''</sub>}} is a subset of an element of {{math|'''Y'''}}, which is a linearly independent subset of {{math|'''V'''}}, and hence {{math|L<sub>'''Y'''</sub>}} is linearly independent. Thus {{math|L<sub>'''Y'''</sub>}} is an element of {{math|'''X'''}}. Therefore, {{math|L<sub>'''Y'''</sub>}} is an upper bound for {{math|'''Y'''}} in {{math|('''X''', ⊆)}}: it is an element of {{math|'''X'''}}, that contains every element of {{math|'''Y'''}}.

As {{math|'''X'''}} is nonempty, and every totally ordered subset of {{math|('''X''', ⊆)}} has an upper bound in {{math|'''X'''}}, [[Zorn's lemma]] asserts that {{math|'''X'''}} has a maximal element. In other words, there exists some element {{math|L<sub>'''max'''</sub>}} of {{math|'''X'''}} satisfying the condition that whenever {{math|L<sub>'''max'''</sub> ⊆ L}} for some element {{math|L}} of {{math|'''X'''}}, then {{math|1=L = L<sub>'''max'''</sub>}}.

It remains to prove that {{math|L<sub>'''max'''</sub>}} is a basis of {{math|'''V'''}}. Since {{math|L<sub>'''max'''</sub>}} belongs to {{math|'''X'''}}, we already know that {{math|L<sub>'''max'''</sub>}} is a linearly independent subset of {{math|'''V'''}}.

If there were some vector {{math|'''w'''}} of {{math|'''V'''}} that is not in the span of {{math|L<sub>'''max'''</sub>}}, then {{math|'''w'''}} would not be an element of {{math|L<sub>'''max'''</sub>}} either. Let {{math|1=L<sub>'''w'''</sub> = L<sub>'''max'''</sub> ∪ {'''w'''}<nowiki/>}}. This set is an element of {{math|'''X'''}}, that is, it is a linearly independent subset of {{math|'''V'''}} (because '''w''' is not in the span of {{math|L<sub>'''max'''</sub>}}, and {{math|L<sub>'''max'''</sub>}} is independent). As {{math|L<sub>'''max'''</sub> ⊆ L<sub>'''w'''</sub>}}, and {{math|L<sub>'''max'''</sub> ≠ L<sub>'''w'''</sub>}} (because {{math|L<sub>'''w'''</sub>}} contains the vector {{math|'''w'''}} that is not contained in {{math|L<sub>'''max'''</sub>}}), this contradicts the maximality of {{math|L<sub>'''max'''</sub>}}. Thus this shows that {{math|L<sub>'''max'''</sub>}} spans {{math|'''V'''}}.

Hence {{math|L<sub>'''max'''</sub>}} is linearly independent and spans {{math|'''V'''}}. It is thus a basis of {{math|'''V'''}}, and this proves that every vector space has a basis.

This proof relies on Zorn's lemma, which is equivalent to the [[axiom of choice]]. Conversely, it has been proved that if every vector space has a basis, then the axiom of choice is true.<ref>{{Harvnb|Blass|1984}}</ref> Thus the two assertions are equivalent.