The outline I (apparently) wrote on the previous post in this series says this post should talk about the Axiom of Choice in algebra, particularly how it affects vector spaces and groups. Before I talk about vector spaces and groups, though, I should (since I boldly subtitled this post “Choice in algebra”) mention some other places AC appears in algebra:
- AC implies that every field has an algebraic closure;
- AC implies that every nonzero ring* has a maximal ideal;
- AC implies that every subgroup of a free group is free (the Nielsen–Schreier theorem).
Moreover, each of these cannot be proved in ZF alone; that is,
- there is a model of ZF in which some field has no algebraic closure;
- there is a model of ZF in which some ring has no maximal ideal;**
- there is a model of ZF in which some free group has a non-freely-generated subgroup.
*In this post, ‘ring’ = ‘ring with identity’.
**I haven’t found a proof for this, actually, but Wikipedia claims the statement ‘every nonzero ring has a maximal ideal’ is actually equivalent to AC. My guess would be that the boolean ring of subsets of an amorphous set wouldn’t have a maximal ideal. I’ll look into it.
In this post I’m going to prove the following:
- AC is equivalent to the assertion ‘Every set can be endowed with a group structure’;
- the assertion ‘Every vector space has a basis’ is equivalent to AC; and
- assuming AC, bases in a vector space must have the same cardinality.
The first result I shamelessly pull from Ashutosh’s answer to this MO question. Apparently the result is due to Hajnal and Kertész.1 I’ll provide some more detail, though. Hopefully you’ll find that helpful.
Theorem 1. In ZF, the following are equivalent:
- For every set , there is a binary operation such that forms a group.
Proof. First suppose that AC holds, and let be a set. If is finite, we can give the cyclic group structure, so suppose is infinite. Then there is a bijection from to the set of finite subsets of . (In the presence of AC, this is an elementary exercise in cardinal arithmetic.) The set becomes a group when endowed with the symmetric difference operation: . If you don’t believe this, you should check it yourself. It’s a worthwhile exercise. Pulling this operation back along the bijection gives a group operation on .
The converse isn’t so easy. Suppose (2) holds. The first step is to obtain an ordinal (the least such is called the Hartogs number of ) such that there is no injection from into . The set of well-orderings of subsets of corresponds to a set of ordinals (namely the order-types of such well-orderings), which, being only a set, is bounded in the class of ordinals. So there are all kinds of ordinals greater than each order-type of a well-ordering of a subset of ; therefore there must be a least such ordinal .
Now let be a group operation on the disjoint union . For every there is an element such that ; indeed, the map given by is an injection, so its image cannot be contained in .
Using this fact, define a function in the following way. Equip with the lexicographic order (a well-ordering) . Now for let be the -minimal pair in such that . Then is an injection, as is clear from the fact that is a group operation. In summary, we have created a bijection from to a subset (namely ) of the well-ordered set , which induces a well-ordering on .
Under the assumption (2) we have proved in ZF that every set can be well-ordered. From this we deduce AC.
Hotovy wonders whether, in the presence of AC, you can always “put a ring on it” (his words). That is, he wonders whether every set can be made into a ring. The answer is yes: take the abelian group constructed above and, as he suggests, equip it with the trivial multiplication (or equip it with the multiplication given by ). This ring doesn’t have an identity, though. I don’t know whether it is possible (even with full AC) to endow any old set with a ring structure (commutative?) that gives the ring an identity, and I don’t know whether such an assertion is equivalent to AC.
The proof in ZFC that every vector space has a basis is a standard Zorn’s-Lemma argument. Since Andy has already done a fine job of outlining that argument here (hopefully he won’t mind the link), I won’t repeat it. Instead, I’ll provide a lovely proof (due to Andreas Blass) of the converse: in ZF, the assertion that every vector space has a basis implies AC.
First, some technicalities: We will need to consider a(n ostensibly) weakened version of AC here. Call the following assertion the ‘Axiom of Multiple Choice’ (AMC):
For every set not containing the empty set , there is a function that assigns to each element of a finite nonempty subset of .
Clearly AC implies AMC. It is also the case that in ZF, AMC implies AC. See Chapter 9 of Jech’s book The Axiom of Choice for details. We’re going to prove:
Theorem 2. In ZF, the assertion that every vector space has a basis implies AMC.
and deduce from this theorem that ‘Every vector space has a basis’ implies AC.
The basic idea of the proof is that we’ll have to construct a vector space out of a given set and force the vector space structure to spit out a bunch of finite nonempty subsets of members of . Blass’s great insight here, in my opinion, was that it’s important to make both the vector space and the ground field to work for you. Here’s his proof:
Proof of Theorem 2. Let be a set of nonempty (pairwise) disjoint sets indexed by a set . Our goal is to find a family of finite subsets of the . Let be any field, and put . Obtain the field of rational functions over by adjoining to all elements of as indeterminates and passing to the fraction field. So is the field whose elements are -rational functions in the ‘variables’ . For every define the –degree of a monomial in to be the sum of the exponents of members of in that monomial. We say a rational function is –homogeneous of degree if is a quotient such that every monomial in the numerator has the same -degree while every monomial in the denominator has the same -degree . (So the ‘of degree ‘ means each monomial in the numerator has -degree more than each monomial in the denominator.)
It isn’t difficult to see that those rational functions in which are -homogeneous of degree for every form a subfield of . (If you’re following along in Blass’s original paper or in Rubin & Rubin, notice that my is their .) Thus is a vector space over ; let be the subspace of (the -vector space)
generated spanned (whatever people say in lin. alg.) by the set .
(OK, the setup is done. Recap: we have a containment of fields , and thus the bigger field (rational functions) is a vector space over the smaller field (-homogeneous functions of degree 0). We have let be the subspace of spanned by the set .)
By assumption the -vector space has a basis . For a moment, fix a coordinate . For every element we can express as an -linear combination of basic elements. That is, there is a finite subset of the basis and nonzero coefficients , one for each , such that
For another element , we have a similar equation:
But we can multiply the equation by to get an alternative expression of as an -linear combination of basic vectors:
Before you do anything else, notice that, because and both belong to the set , the product is -homogeneous of degree , and so each coefficient is indeed a member of the ground field . But now we have two expressions of as an -linear combination of elements of the basis , so those two expressions must be the same. That is, we must have and for every . In particular, the finite subset of and the elements of depend only on the coordinate , not on the particular element .
We can therefore assign (uniquely, without any choice) to each coordinate its finite subset of and its elements of . Observe that, for each , is -homogeneous of degree (because of the in the denominator of ) and -homogeneous of degree for (by the definition of the field and the fact that each belongs to ). Therefore, when is written as a quotient of polynomials in reduced form, some indeterminates from must occur in the denominator. Define to be the set of members of that appear in the denominator of for some . Then is a finite nonempty subset of , which is what we wanted.
After one proves via Zorn’s Lemma that every vector space has a basis, it’s natural to ask whether infinite-dimensional vector spaces enjoy ‘uniqueness of dimension’ as finite-dimensional ones do. Luckily, in the presence of AC, linear algebra’s reputation for being pathology-free is not tarnished here, as I show below. I direct your critical eye to the proof of this theorem on Wikipedia, which I dislike for several reasons. Zeroth, it’s not very enlightening, as a good proof would be. First, it uses so-called ‘contradiction’ (really contraposition in this case, I suppose) unnecessarily and without benefit to the reader. (That is an awful habit.) Second (a failure of the presentation rather than the proof), it fails to describe why there is a bijection from the first basis to the chosen set of elements in the second which span the first, when this is the crux of the argument! Finally, it uses full Choice when much less is needed, and using less makes for a better, more illuminating proof.
In preparing for this blog post, I set out to prove this result by Zorn’s-Lemma-ing the poset of partial span-preserving bijections , where is a subset of the first basis and is a subset of the second. This seems to work; try it for yourself if you want. But, like Wikipedia’s proof, it uses full choice (ZL) without good reason. Luckily, I stumbled on a wonderful proof (possibly also due to Andreas Blass, whom early polls show to be the favourite for MVP of this post, but maybe a result from Rubin & Rubin3 (though I can’t find it there…)) that is much, much cuter than the others and uses only the Compactness Theorem (independent of ZF but equivalent to the Prime Ideal Theorem, which is weaker than full AC).
Theorem 3. Suppose is a vector space (over any field) and and are both bases for Then there is a bijection .
Proof. It suffices, by the Schröder–Bernstein Theorem, to find an injection . For every element there is a unique minimal finite subset of such that belongs to the span of . (The set is unique since is independent.) We are going to insist that for every . This seems to make the problem more difficult, but it (doesn’t and) allows us to reformulate the problem in terms of the satisfiability of a set of propositional formulas, which we define as follows: Let mean . Consider the following formulas:
- (‘ is a function’);
- (‘ is an injection’);
- for each , the disjunction (‘ is defined at every and ‘).
To say that these formulas are simultaneously satisfiable is to say that there is an injection such that for every . By the Compactness Theorem, we need only prove that every finite subset of these formulas is satisfiable. That is, we need to show that for each finite subset of , there is an injection from to sending every to an element of .
Let be a finite subset of , and let be a subset of . The set (hopefully it’s clear what that means) is a(n independent) subset of that spans , an independent set. By standard finite-dimensional linear algebra we can’t have , for this would mean that we could express linearly independent vectors as the linear combination of fewer than vectors. That is, it must be that for every subset of . By Hall’s Matching Theorem, there is an injection sending every to an element of . The proof is complete, by the Compactness Theorem. =^]
I like these linear-algebra–AC proofs. Each uses the sort-of ‘local’ finiteness of a vector space and the rigidness linear independence provides to transfer information between vector space structure and sets. Pretty cool, eh?
1Hajnal, A., Kertész, A. Some new algebraic equivalents of the axiom of choice, Publ. Math. Debrecen 19 (1972), 339–340. (MR0329895)
2Blass, Andreas. Existence of bases implies the axiom of choice. Axiomatic set theory (Boulder, Colo., 1983), 31–33, Contemp. Math., 31, Amer. Math. Soc., Providence, RI, 1984. (MR0763890)
3Rubin, H., Rubin, J. E. Equivalents of the axiom of choice. II. Studies in Logic and the Foundations of Mathematics, 116. North-Holland Publishing Co., Amsterdam, 1985. (MR0798475)