Every vector space over a field has a basis, assuming the axiom of choice. More generally, any linearly independent subset extends to a basis. This is an algebraic Hamel basis: each representation uses a finite linear combination, even when the basis is infinite.[ref]
Use the poset of linearly independent subsets containing :
It is a set, being a subset of the power set of , and is nonempty because .
A short proof outline supplies both essential steps:
Taking proves existence, including , whose basis is the empty set. The chain in a partial order need not be indexed by the natural numbers: only the finitely many members needed for a particular linear relation are compared. An arbitrary union of linearly independent sets can fail: and for a nonzero vector over the real numbers are each linearly independent, but their union is linearly dependent. The nesting of a chain in a partial order is what prevents this failure.
Take labels and vectors in the real vector space :
Here is the complete independence check for all eight subsets. The empty set is independent. Each of is independent because its vector is nonzero. Every pair is independent: the determinants of the two-column matrices , , and are respectively , , and . The triple is dependent because . Therefore
Deleting elements from any listed subset stays in this list, verifying heredity. Every exchange comparison has sizes , , or . From the empty set, any element of the larger matroid independent set works: this covers three singleton targets and three pair targets. From any singleton to any pair, every element of the pair outside the singleton works, since every resulting pair is independent. This covers all nine singleton-pair comparisons, including disjoint ones. There are no other comparisons: all fifteen ordered size-increasing pairs satisfy exchange.
Figure 1.
Three vectors have three independent pairs and one dependent triple; the heaviest matroid basis is with weight
. Details.
The three matroid bases are , , and , all of cardinality two, with weights , , and . The matroid greedy algorithm considers , then , then : it admits , admits because their determinant is nonzero, and rejects because the triple is dependent. The resulting matroid basis has weight , the largest of the three totals. Every singleton can grow, so none is maximal; the three pairs are both maximal and maximum in cardinality.
Zermelo set theory 2026-10-14
The usual set theory with extensionality, empty set, pairing, union, power set, infinity and full separation, before adjoining replacement. Modern presentations often include foundation; the convention should be specified when comparing theories. Class-theoretic variants add classes and class comprehension, rather than treating proper classes as sets.
Zorn's lemma 2026-10-14
Let be a nonempty partially ordered set. If every chain in a partial order has an upper bound in , then has a maximal element. The hypothesis means
The upper bound may depend on and need not belong to . A least upper bound is not required. The conclusion asserts that some satisfies ; it does not assert a greatest element, which would satisfy for every .[ref]
Here a chain in a partial order may be the empty set. Every member of is an upper bound of the empty chain in a partial order, so including it in the hypothesis already forces to be nonempty. If “chain” means only nonempty chains in a partial order, the separate nonempty- assumption is essential: the empty poset otherwise satisfies the hypothesis vacuously and has no maximal element. These are two equivalent conventions for the theorem.
The strength of Zorn's lemma is that compatible partial constructions can have a completed, unextendible member without an explicit procedure for finding it. The next examples separate the upper bound calculation from the reason a maximal element has the desired property. All chains in a partial order must be covered, including uncountable ones, rather than just increasing sequences. The condition is sufficient, not necessary: a poset can have a maximal element and still have an unbounded chain in a partial order elsewhere.