Vector space bases from Zorn's lemma 2026-10-14
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:
- For a nonempty chain in a partial order , put . Any finite linear relation in lies in one member of : among finitely many containing members, one contains the rest. Its linear independence makes every coefficient zero. Thus is an upper bound. For the empty chain in a partial order, use ; its empty union need not contain .
- Zorn's lemma gives a maximal element . If a vector lies outside its linear span, then is linearly independent: a linear relation with nonzero coefficient on would express in that linear span. This contradicts maximality, so is a spanning set and hence a basis.[ref]
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.
Weighted three-vector matroid 2026-10-14
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 . ThereforeDeleting 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.
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 meansThe 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]
How to use Zorn’s lemma by Timothy Gowers. How to use Zorn’s lemma, “General discussion”: statement and distinction between maximal and bigger than everything else
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.
