Free Groups and the Axiom of Choice Philipp Kleppmann University of Cambridge Department of Pure Mathematics and Mathematical Statistics Corpus Christi College August 2015 This dissertation is submitted for the degree of Doctor of Philosophy Declaration This dissertation is the result of my own work and includes nothing which is the outcome of work done in collaboration except as declared in the Acknowledgements and specified in the text. Chapters 1 and 2, and sections 4.1 and 4.2 consist of review material. Chapter 3, section 4.3, and chapters 5 and 6 are original work. This dissertation is not substantially the same as any that I have submitted, or, is being concurrently submitted for a degree or diploma or other qualification at the University of Cambridge or any other University or similar institution except as declared in the Acknowledgements and specified in the text. I further state that no substantial part of my dissertation has already been submitted, or, is being concurrently submitted for any such degree, diploma or other qualification at the University of Cambridge or any other University of similar institution except as declared in the Acknowledgements and specified in the text Philipp Kleppmann 2 Acknowledgments I would like to express my gratitude to my supervisor, Thomas Forster, for asking about the Nielsen–Schreier theorem and for his advice and guidance over the last three years. My thanks also go to John Truss and Benedikt Lo¨we for finding an error and suggesting a correction in the proof of proposition 5.13, to Thomas Forster for finding a simplification in the proof of proposition 5.13, to Vu Dang for spotting a gap in the proof of theorem 5.23, and to Alex Kruckman for providing the example 6.1. I would like to thank: Zachiri McKenzie, David Matthai, and Adam Lewicki for fruitful discussions; Debbie and Randall Holmes for hosting me in Boise for three weeks; the logic group in Leeds for informative and entertaining meetings; and Thomas Forster, Nicola Kleppmann, and Martin Kleppmann for proofreading my manuscript. I am grateful to Corpus Christi College and the Department of Pure Mathematics and Mathematical Statistics for providing me with financial support which allowed me to complete my studies. None of this would have been possible without my family’s constant support and en- couragement. It means a lot to me. 3 Free Groups and the Axiom of Choice Philipp Kleppmann Summary The Nielsen–Schreier theorem states that subgroups of free groups are free. As all of its proofs use the Axiom of Choice, it is natural to ask whether the theorem is equivalent to the Axiom of Choice. Other questions arise in this context, such as whether the same is true for free abelian groups, and whether free groups have a notion of dimension in the absence of Choice. In chapters 1 and 2 we define basic concepts and introduce Fraenkel–Mostowski models. In chapter 3 the notion of dimension in free groups is investigated. We prove, without using the full Axiom of Choice, that all bases of a free group have the same cardinality. In contrast, a closely related statement is shown to be equivalent to the Axiom of Choice. Schreier graphs are used to prove the Nielsen–Schreier theorem in chapter 4. For later reference, we also classify Schreier graphs of (normal) subgroups of free groups. Chapter 5 starts with an analysis of the use of the Axiom of Choice in the proof of the Nielsen–Schreier theorem. Then we introduce representative functions – a tool for constructing choice functions from bases. They are used to deduce the finite Axiom of Choice from Nielsen–Schreier, and to prove the equivalence of a strong form of Nielsen– Schreier and the Axiom of Choice. Using Fraenkel–Mostowski models, we show that Nielsen–Schreier cannot be deduced from the Boolean Prime Ideal Theorem. Chapter 6 explores properties of free abelian groups that are similar to those considered in chapter 5. However, the commutative setting requires new ideas and different proofs. Using representative functions, we deduce the Axiom of Choice for pairs from the abelian version of the Nielsen–Schreier theorem. This implication is shown to be strict by proving that it doesn’t follow from the Boolean Prime Ideal Theorem. We end with a section on potential applications to vector spaces. 4 5Contents 1 Preliminaries 7 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3 Free groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.4 Free abelian groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.5 Choice principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2 Fraenkel–Mostowski models 16 2.1 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2 An example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.3 Two models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.4 A transfer theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3 The size of bases 27 3.1 Bases of isomorphic free groups . . . . . . . . . . . . . . . . . . . . . . . 28 3.2 Bases of equipollent free groups . . . . . . . . . . . . . . . . . . . . . . . 31 64 Nielsen–Schreier 34 4.1 Schreier graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.2 A proof of the Nielsen–Schreier theorem . . . . . . . . . . . . . . . . . . 38 4.3 Classifying Schreier graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5 Nielsen–Schreier and the Axiom of Choice 46 5.1 A brief history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 5.2 The use of the Axiom of Choice . . . . . . . . . . . . . . . . . . . . . . . 49 5.3 Does Nielsen–Schreier imply the Axiom of Choice? . . . . . . . . . . . . 52 5.4 Nielsen–Schreier implies the finite Axiom of Choice . . . . . . . . . . . . 56 5.5 Nielsen–Schreier doesn’t follow from the Prime Ideal Theorem . . . . . . 63 5.6 Reduced Nielsen–Schreier implies the Axiom of Choice . . . . . . . . . . 66 6 Free abelian groups 74 6.1 Abelian Nielsen–Schreier implies AC2 . . . . . . . . . . . . . . . . . . . . 75 6.2 The implication is strict . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 6.3 More on representative functions . . . . . . . . . . . . . . . . . . . . . . 81 Bibliography 86 7Chapter 1 Preliminaries 1.1 Introduction The Axiom of Choice was formulated in 1904 by Zermelo [41] in order to prove the well-ordering theorem. It is the only axiom of set theory that asserts the existence of a set without also defining it. Although it was disputed in its early days, it is now a well established axiom of set theory. In 1964, Mendelson [32] (p. 201) wrote: The status of the Axiom of Choice has become less controversial in recent years. To most mathematicians it seems quite plausible and it has so many important applications in practically all branches of mathematics that not to accept it would seem to be a wilful hobbling of the practicing mathematician. The controversy has led to the Axiom of Choice occupying a distinguished position among the axioms of Zermelo–Fraenkel set theory with Choice (ZFC). As many general and powerful theorems are among its consequences, its use in proofs of such results has been studied. Theorems of ZFC can be viewed as choice principles ordered by implication over Zermelo–Fraenkel set theory (ZF), i.e. φ ≥ ψ iff ZF ` φ ⇒ ψ. This gives rise to a hierarchy of statements which is the subject of several reference books – including 8 Preliminaries Howard and Rubin [19], Herrlich [14], and Jech [22] – and the numerous papers cited in them. One choice principle that stands out is the Nielsen–Schreier theorem, which states that subgroups of free groups are free. Although the theorem is elegant and simple to state, little is known about its deductive strength. No progress has been made on this problem since the 1980s (Howard [16], Howard [17]). This gap in our knowledge is the starting point of this dissertation. We will improve the known results and prove some new theorems about subgroups of free groups and the Axiom of Choice. The relation between bases of vector spaces and the Axiom of Choice has been studied in many articles. Vector spaces share some properties with free groups, and free abelian groups act as a bridge between them. This allows an exchange of questions and solutions to take place between free groups and vector spaces. We will analyse the notion of dimension, which is important in linear algebra, in the new context of free groups. In the last chapter, we also translate the technique of using representative functions, originally developed for free groups, to the new context of free abelian groups. In the remainder of this chapter we give definitions, fix conventions, and review some basic results. Section 1.2 describes the set theories ZF and ZFA and introduces some notation. In section 1.3 we define free groups and review some of their elementary properties. Free abelian groups are defined in section 1.4. In this thesis we investigate the relationship between free groups and the Axiom of Choice. A list of choice principles considered in later chapters is given in section 1.5. 1.2 Sets We shall be working with two different kinds of set theory: The usual Zermelo-Fraenkel set theory with the Axiom of Choice (ZFC) or without it (ZF), and set theory with atoms (ZFA). The following list of ZF-axioms is taken from chapter 1 of Jech’s textbook [21]. 1. Axiom of Extensionality. If X and Y have the same elements, then X = Y . 1.2 Sets 9 2. Axiom of Pairing. For any a and b there exists a set {a, b} that contains exactly a and b. 3. Axiom Schema of Separation. If P is a property (with parameter p), then for any X and p there exists a set Y = {u ∈ X : P (u, p)} that contains all those u ∈ X that have property P . 4. Axiom of Union. For any X there exists a set Y = ⋃ X, the union of all elements of X. 5. Axiom of Power Set. For any X there exists a set Y = P(X), the set of all subsets of X. 6. Axiom of Infinity. There exists an infinite set. 7. Axiom Schema of Replacement. If a class F is a function, then for any X there exists a set Y = F (X) = {F (x) : x ∈ X}. 8. Axiom of Regularity. Every nonempty set has an ∈-minimal element. Adding the Axiom of Choice, we obtain ZFC: Axiom of Choice. Every family of nonempty sets has a choice function. ZFA is a close relative of ZF. It differs in that it allows for a set of atoms. In essence, an atom is an empty object that is indistinguishable from other atoms. In addition to the binary relation symbol ∈, ZFA has two constant symbols: A for the set of atoms, and ∅ for the empty set. The axioms of ZFA are the same as those of ZF, except for the following changes: We say that x is a set if x 6∈ A, and that x is an atom if x ∈ A. The ZF-axioms of Extensionality and Regularity are weakened to apply to sets only: 10 Preliminaries 1. Axiom of Extensionality. If X and Y are two sets with the same ele- ments, then X = Y . 8. Axiom of Regularity. Every nonempty set has an -minimal element. And there are two new axioms: 9. ∅ has no members. 10. Atoms have no members. Ordered pairs are written in angle brackets: 〈x, y〉. They are taken to be Kuratowski ordered pairs, i.e. 〈x, y〉 = {{x}, {x, y}}. Ordered n-tuples are also written in angle brackets: 〈x1, ..., xn〉. They are inductively defined by 〈x1, ..., xn〉 = 〈x1, 〈x2, ..., xn〉〉. Functions f : X → Y are implemented as subsets of X × Y . Given the function f , we may choose to apply it to subsets of X instead of elements of X: We define, for any A ⊆ X, f“A = {f(a) : a ∈ A}. If A ⊆ X, then the restriction of f to A is f |A : A→ Y : a 7→ f(a). Let X be a set. The cardinality of X is written |X|. An aleph is the cardinality of a well- ordered set. The Hartogs aleph of X, written ℵ(X) is the least aleph with ℵ(X) 6≤ |X|. The von Neumann hierarchy is defined by V0 = ∅ Vα+1 = P(Vα) Vλ = ⋃ α<λ Vα for λ a non-zero limit ordinal We can overload the Vα as an operation on sets. If X is a set, then we let V0(X) = X Vα+1(X) = P(Vα(X)) ∪ Vα(X) Vλ(X) = ⋃ α<λ Vα(X) for λ a non-zero limit ordinal 1.3 Free groups 11 1.3 Free groups Let X be any set. Before defining the free group F(X) on X, we must introduce some vocabulary. Definition 1.1. X−1 = {x−1 : x ∈ X} is a set of formal inverses of members of X. X−1 is always assumed to be disjoint from X. For brevity, we write X± for X ∪X−1. Elements of X± are X-letters. X-words are products x1 · · ·xn, where n ≥ 0 and xi ∈ X± for i = 1, ..., n. Sometimes it is more convenient to write them as x11 · · ·xnn , where n ≥ 0, and, for i = 1, ..., n, xi ∈ X and i ∈ {1,−1}. They are implemented as finite sequences 〈x1, ..., xn〉 of elements of X±. The process of removing a pair xx− from the X-word x11 · · ·xx− · · ·xnn is called cancellation. An X-word is X-reduced if no cancellation is possible. The X-reduction of an X-word α is the result of performing all possible cancellations in α. It is independent of the order in which the cancellations are performed. Two X-words are equivalent if they have the same X-reductions. The X-length of an X-word α, written `X(α) is the number of letters in the X-reduction of α. When there is no danger of confusion, we may omit references to X. Definition 1.2. The free group F(X) consists of the set of all reduced X-words, together with a binary operation ∗ defined to be concatenation followed by X-reduction. The identity element of F(X) is the empty word, written 1. This means that, if α = x1 · · · xn and β = y1 · · · ym are reducedX-words with xi, yi ∈ X±, then α∗β is the X-reduction of x1 · · ·xny1 · · · ym. For notational simplicity we often don’t 12 Preliminaries make a distinction between an X-word and its X-reduction, and we may colloquially take F(X) to be the set of all X-words together with the binary operation of concatenation. Definition 1.3. Let F be a group. F is a free group if there is X ⊆ F such that F ∼= F(X). If this is the case, we say that F is free on X, and that X is a basis for F . This means that a group F is free if there is X ⊆ F such that every element α ∈ F can be written as a unique reduced product x1 · · · xn of X-letters. Free groups are characterised by a universal property: Let F be a free group with basis X. If G is a group and f : X → G is any function, then f has a unique extension to a homomorphism φ : F → G, defined by: φ : F → G : x11 · · ·xnn 7→ f(x1)1 · · · f(xn)n . Definition 1.4. If G is a group and X ⊆ G, then X is said to be free if there are no non-trivial relations between members of X. This means that, if x1 · · ·xn is a reduced product of X-letters, and x1 · · ·xn = 1, then n = 0. Let F be a free group. It is straightforward to check that X ⊆ F is a basis (as defined in definition 1.3) if and only if it is a free generating set of F . A fundamental result in the theory of free groups is the Nielsen–Schreier theorem. It states that subgroups of free groups are themselves free. The theorem was first proved in the finitely generated case by Nielsen [34]. Schreier [39] later used a different method to prove the general case. English versions of both proofs can be found in chapters 2 and 3 of Johnson’s book [25]. Theorem 1.5 (Nielsen–Schreier). If F is a free group and H is a subgroup of F , then H is a free group. 1.5 Free abelian groups 13 1.4 Free abelian groups Definition 1.6. Let X be a set. The free abelian group on X, written FA(X), is the quotient of the free group on X by its commutator subgroup. In other words, FA(X) = F(X)/〈{αβα−1β−1 : α, β ∈ F(X)}〉. The process of taking the quotient of a group by its commutator subgroup is called abelianisation. We use additive notation for abelian groups. So every α ∈ FA(X) may be written as a finite sum α = n1x1 + ...+ nkxk, where k ≥ 0, the x1, ..., xk ∈ X are distinct, and n1, ..., nk ∈ Z \ {0}. This expression is unique up to the ordering of its terms. Definition 1.7. If F = FA(X) is a free abelian group and B ⊆ F , then B is a basis of F if every α ∈ F can be uniquely written as a finite sum α = n1b1 + ... + nkbk with k ≥ 0, b1, ..., bk ∈ B distinct, and n1, ..., nk ∈ Z \ {0}. Free abelian groups enjoy a similar universal property to free groups. Let F = FA(X) be a free abelian group, and let A be any abelian group. If f : X → A is any function, then f has a unique extension to a group homomorphism φ : F → A : ∑ nixi 7→ ∑ nif(xi). 1.5 Choice principles In the following chapters, we will investigate the relationship between the Axiom of Choice, the Nielsen–Schreier theorem, and several related theorems. First, we list the well-known set theoretic choice principles. 14 Preliminaries AC (Axiom of Choice): For any family {Xi : i ∈ I} of non-empty sets there is a function which assigns, to each i ∈ I, a single element of Xi. BPIT (Boolean Prime Ideal Theorem): Every boolean algebra has a prime ideal. ACfin (Axiom of Finite Choice): For any family {Xi : i ∈ I} of non-empty finite sets there is a function which assigns, to each i ∈ I, a single element of Xi. ACn (Axiom of Choice for n-element sets): For any family {Xi : i ∈ I} of n-element sets there is a function which assigns, to each i ∈ I, a single element of Xi. These statements have been studied in depth, and their relative strengths (in ZF) are known – see figure 1.1 below. We will also meet the following algebraic choice principles. Their deductive strengths are largely unexplored. Determining them is the subject of this dissertation. NS (Nielsen–Schreier): If F is any free group and K ≤ F is any subgroup, then K is a free group. NSnorm (Nielsen–Schreier for normal subgroups): If F is any free group and K ≤ F is a normal subgroup, then K is a free group. NSred (reduced Nielsen–Schreier): If F is the free group on a set X and K ≤ F is any subgroup, then K has a basis that is reduced with respect to X. (For a definition of reduced bases, see section 5.6.) NSab (Nielsen–Schreier for abelian groups): If F is a free abelian group and K ≤ F is a subgroup, then K is a free abelian group. CB1 (Cardinality of bases, version 1): F(X) ∼= F(Y ) ⇒ |X| = |Y | for any sets X and Y . CB2 (Cardinality of bases, version 2): |F(X)| = |F(Y )| ⇒ |X| = |Y | for infinite sets X and Y . Figure 1.1 summarises the main results of this thesis. Double-headed arrows represent 1.5 Choice principles 15 equivalences, and the remaining solid arrows stand for strict implications. Implications that may be equivalences appear as dashed arrows. The unlabelled arrows are taken from diagram 2.21 of Herrlich [14]. CB2 AC NSred BPIT NS CB1 NSnorm ACfin AC2 NSab thm 3.10 prop 3.1(ii) cor 5.24 prop 5.19 thm 4.11 clear prop 5.13 cor 5.17 thm 3.7 prop 6.2 prop 6.5 cor 6.11 Figure 1.1: Implications between Choice principles 16 Chapter 2 Fraenkel–Mostowski models We now turn to a procedure for proving independence results concerning the Axiom of Choice, which was developed by A. Fraenkel and A. Mostowski. The purpose of the method is to produce new models of set theory from old ones, and to control the be- haviour of the new models by choosing suitable parameters. It later inspired P. Cohen’s proof ([3], [4]) of the independence of the Axiom of Choice from ZF by constructing a symmetric submodel of a generic extension of a given model of ZFC. In section 2.1 we define Fraenkel–Mostowski models. After going through a sample application of Fraenkel–Mostowski models in section 2.2, two new models are introduced in section 2.3, and we explore some of their basic properties. Section 2.4 concludes the chapter by introducing a theorem which allows us to easily transfer statements from ZFA to ZF. 2.1 Setup A Fraenkel–Mostowski model M is constructed as a substructure of a given model N of set theory. M consists of those sets in N that are sufficiently symmetric under a specified group of automorphisms of N. This automorphism group controls the properties of M. Since there are no non-trivial ∈-automorphsims for ZF-models, the Fraenkel–Mostowski 2.1 Setup 17 method uses models of ZFA instead. So let N be a model of ZFA+AC with universe V and set A of atoms. ∈-automorphisms of V are obtained by letting pi be any permutation of A, and extending pi to all of V by setting pi(x) = pi“x for any x ∈ V . We will always identify permutations of A with their canonical extensions to V . Let G ∈ N be any group of permutations of A, viewed as automorphisms of N. Definition 2.1. If x ∈ V , then orb(x) = {pi(x) : pi ∈ G} ⊆ V is the orbit of x, stab(x) = {pi ∈ G : pi(x) = x} ≤ G is the (setwise) stabiliser of x, and fix(x) = {pi ∈ G : (∀y ∈ x)pi(y) = y} ≤ G is the (pointwise) stabiliser of x. It is easily verified that fix(x) ≤ stab(x) for any set x. But equality needn’t hold, as there might be elements of G which permute the members of x without moving x itself. Before defining Fraenkel–Mostowski models, we need to introduce another parameter of the construction: Definition 2.2. A set F of subgroups of G is a normal filter if 1. G ∈ F , 2. (∀H,K ≤ G) (H ∈ F ∧H ≤ K ⇒ K ∈ F), 3. (∀H,K ∈ F) H ∩K ∈ F , 4. (∀pi ∈ G) (∀H ∈ F) piHpi−1 ∈ F , 18 Fraenkel–Mostowski models 5. (∀a ∈ A) stab(a) ∈ F . Definition 2.3. Let x ∈ V . x is F-symmetric if stab(x) ∈ F , and it is hereditarily F-symmetric if x is F -symmetric and all members of the transitive closure of x are F -symmetric. We will omit the reference to F if it is clear from the context. As normal filters are upward closed, members of a normal filter F can be thought of as ‘large’ subgroups of G. Hence the name symmetric: a set x is symmetric if it has a ‘large’ stabiliser, i.e. if it is left unchanged by ‘most’ permutations in G. Definition 2.4. Given a set A of atoms, a group G of permutations of A, and a normal filter F of subgroups of G, define the substructure M ≤ N to consist of all hereditarily symmetric sets of V , with the ∈-relation restricted from N. M is called the Fraenkel– Mostowski model with respect to A, G, and F . The next theorem states that Fraenkel–Mostowski models are models of ZFA. Theorem 2.5 (Jech [22], page 46). M |= ZFA. We now introduce the notion of pure, or atomless, sets. As they don’t involve any atoms, we expect them to behave like ZF-sets. And indeed, the collection of all pure sets constitutes a model of ZF. Objects such as the ordinals or the real numbers, are implemented as pure sets in ZFA. Definition 2.6. A set x ∈ N is pure if it is not an atom and its transitive closure contains no atoms. The collection of all pure sets is the kernel of N. Notice that, as pure sets don’t involve atoms that could be moved by members of G, each pure set is fixed by all permutations of the atoms. Hence stab(x) = G ∈ F for any pure set x and any normal filter F . So the kernel of a Fraenkel–Mostowski model M is always the same as the kernel of its parent model N. It may not be entirely clear how to produce a normal filter F of subgroups of G. The easiest way of doing this is to define a normal ideal I of subsets of A and to take F to be the filter induced by I. This method is used for all models discussed in this thesis. 2.1 Setup 19 Definition 2.7. A set I of subsets of A is a normal ideal if 1. ∅ ∈ I 2. (∀E,F ⊆ A) (E ∈ I ∧ F ⊆ E ⇒ F ∈ I) 3. (∀E,F ∈ I) E ∪ F ∈ I 4. (∀pi ∈ G) (∀E ∈ I) pi“E ∈ I 5. (∀a ∈ A) {a} ∈ I Corresponding to the intuition that members of a normal filter F are ‘large’, we may think of members of a normal ideal as ‘small’ sets of atoms. Normal ideals of subsets of A are easy to find. The smallest possible normal ideal is I = {E ⊆ A : E is finite}, the finite ideal. This is the most common choice for Fraenkel–Mostowski models. Definition 2.8. Every normal ideal I of subsets of A induces a filter F of subgroups of G, defined by {H ≤ G : (∃E ∈ I) fix(E) ≤ H}. It is easy to check that F is a normal filter. A description of the induced filter in terms of supports is useful: Definition 2.9. If E ⊆ A and x ∈M, then E is a support for x if fix(E) ≤ stab(x). In other words, E is a support for x if every permutation pi ∈ G fixing all points of E satisfies pi(x) = x. Supports capture information about the atoms in the transitive closure of x which are responsible for the asymmetry of x. For example, pure sets – which are fixed under all possible permutations of the atoms – have an empty support. It is important to note that supports, if they exist, are in general not unique. 20 Fraenkel–Mostowski models Observe that x is symmetric ⇔ stab(x) ∈ F ⇔ (∃E ∈ I) fix(E) ≤ stab(x) ⇔ x has a support in I. This means that a set x ∈ N is in the Fraenkel–Mostowski model M if and only if x and all members of the transitive closure of x have supports in I. We are now ready to see an important Fraenkel–Mostowski model, and to prove a basic independence result. A large catalogue of Fraenkel–Mostowski models and their prop- erties is in Howard and Rubin [19]. 2.2 An example In this section, we review an example from H. La¨uchli’s influential paper [31]. It illus- trates how the Fraenkel–Mostowski method is used to obtain independence results in set theory, and it foreshadows some proofs that we will encounter later in the text. First, we introduce the model M, called Fraenkel’s basic model. It is the simplest non-trivial Fraenkel–Mostowski model. The three parameters are (a) a countably infinite set A of atoms, (b) the full symmetry group G = Sym(A) of A, and (c) the normal filter F of subgroups of G induced by the finite ideal on A. We now present H. La¨uchli’s proof that there is a free group in M with a subgroup that is not free. In section 5.5 we give a more refined argument to show that the Nielsen- Schreier theorem fails in a Fraenkel–Mostowski model satisfying the Boolean Prime Ideal Theorem. Theorem 2.10 (La¨uchli [31]). M |= ¬NS. 2.2 An example 21 Proof. Let F = F(A) be the free group generated by A in M. We will show that the commutator subgroup K = 〈{αβα−1β−1 : α, β ∈ F}〉 ≤ F is not free. If it is, then there is a basis B ∈M with a (necessarily finite) support E ⊆ A. We will derive a contradiction. Let u, v ∈ A \ E be distinct, and let α = uvu−1v−1 ∈ K. If φ ∈ G is the transposition (uv), then φ(α) = φ(u)φ(v)φ(u)−1φ(v)−1 = vuv−1u−1 = α−1, and φ(B) = B because u, v 6∈ E. Writing α = b1 · · · bn as a reduced product of elements of B±, we deduce that φ(b1) · · ·φ(bn) = b−1n · · · b−11 , i.e. that φ(bn) = b −1 1 , φ(bn−1) = b −1 2 , ..., φ(b1) = b −1 n . (2.1) As no bi ∈ B± is equal to its own inverse, n = 2k must be even. This allows us to define β = b1 · · · bk as the ‘first half’ of α. Since β is a product of elements of B±, β ∈ K. Write β = a1 · · · am as a reduced A-word, with a1, ..., am ∈ A±. Then a1 · · · amφ(am)−1 · · ·φ(a1)−1 = βφ(β)−1 = b1 · · · bkφ(bk)−1 · · ·φ(b1)−1 = b1 · · · bkbk+1 · · · bn (by (2.1)) = α = uvu−1v−1. We conclude that a1 = u, a2 = v, φ(a3) = a3, ..., φ(am) = am. As a3, ..., am are fixed by φ, none of them can be equal to u or v. Hence the sum of the exponents of the letter u in β = a1 · · · am is 1, contradicting the choice of β as an element of the commutator subgroup of F . Hence every proof of the Nielsen–Schreier theorem in ZFA must use a fragment of the Axiom of Choice. In section 2.4 we will see how this result can be transferred from ZFA to the standard set theory ZF. 22 Fraenkel–Mostowski models The idea of splitting α and writing it as a product of its two halves is critical. It will be a recurring theme in chapter 5, even in sections that have nothing to do with Fraenkel–Mostowski models. 2.3 Two models The Dawson–Howard model The Dawson–Howard model is a close relative of the well studied cousin, Mostowski’s ordered model (see Jech [22], section 4.5). It was introduced by Dawson and Howard [6] and is called N 29 in Howard and Rubin [19]. The three parameters A, G, and F are defined as follows: (a) Let {〈Ai, 0, λ(ei) ∈ B, and i ∈ {1,−1} for i = 1, ..., n, is B-reduced, then `X(ξ) ≥ `B(ξ) = n > 0. (4.2) In particular, ξ 6= 1. 4.3 A proof of the Nielsen–Schreier theorem 41 The only place in this proof where the Axiom of Choice was used is the assertion of the existence of a spanning tree in the Schreier graph. As the next example shows, the geometrically intuitive and constructive nature of this proof lets us find explicit bases of some subgroups of free groups. Example 4.12. We construct a basis for the commutator subgroup of the free group F({a, b}) on two letters by exhibiting a spanning tree of the Schreier graph found in example 4.4. Identify right cosets Cξ with points of the grid Z× Z. Then T = {〈〈m,n〉, 〈m+ 1, n〉〉 : m,n ∈ Z} ∪ {〈〈0, n〉, 〈0, n+ 1〉〉 : n ∈ Z} is a spanning tree. It is highlighted in figure 4.4. Using the proof of theorem 4.11, we deduce that {bnamba−mb−(n+1) : m,n ∈ Z,m 6= 0} is a basis for C. ... ... ... · · · Ca−1b Cb Cab · · · · · · Ca−1 C Ca · · · · · · Ca−1b−1 Cb−1 Cab−1 · · · ... ... ... a a a a a a a a a a a a b b b b b b b b b b b b Figure 4.4: The Schreier graph of the commutator subgroup C of F({a, b}) 42 Nielsen–Schreier 4.3 Classifying Schreier graphs In this section, we show that a digraph is the Schreier graph of a subgroup of a free group if and only if it is connected and satisfies a regularity condition. Later, we show that the subgroup is normal if and only if the corresponding Schreier graph also satisfies a homogeneity condition. These classification results will allow us to determine how much of the Axiom of Choice is used when asserting the existence of spanning trees in Schreier graphs. Recall from section 4.1 the following observation about Schreier graphs: For any vertex Kξ and any x ∈ X±, there is one edge labelled x terminating at Kξ, and there is one edge labelled x starting at Kξ. This property deserves a name: Definition 4.13. If G = 〈V,E〉 is a digraph with edges labelled by elements of a set X±, then G is X-regular if, for every x ∈ X± and v ∈ V , there is one edge labelled x starting at v and there is one edge labelled x ending at v. G is regular if it is X-regular for some X. Before classifying Schreier graphs, we introduce a useful piece of notation. Definition 4.14. Let F = F(X) be a free group, let K ≤ F be a subgroup, and let G be the Schreier graph of K ≤ F . The expression Kξ x−→ Kζ means there is an edge in G which starts at Kξ, ends at Kζ, and has label x. Proposition 4.15. Let G = 〈V,E〉 be a digraph. G is a Schreier graph if and only if it is regular and connected. Proof. ⇒ X-regularity was observed in section 4.1. Proposition 4.9(ii) shows that Schreier graphs are connected. ⇐ Let X be a set such that G is X-regular, and fix any vertex v ∈ V for the rest of this proof. As mentioned in section 4.1, X-regularity gives a natural interpretation 4.3 Classifying Schreier graphs 43 of words x1 · · ·xn ∈ F , where xi ∈ X± for i = 1, ..., n, as paths in G beginning at v. Let K be the group of cycles in G based at v. By identifying the cycles in G with words x1 · · ·xn, where xi ∈ X±, we may view K as a subgroup of the free group F = F(X). We will show that G is the Schreier graph of K ≤ F . Define a function L : V → F/K from vertices of G to right cosets of K in F as follows: Let w ∈ V , and let α ∈ F represent a path in G from v to w (this exists, as G is connected). Define L(w) = Kα. We must check that L(w) is independent of the choice of α: Suppose α, β are two paths in G from v to w. Then αβ−1 is a cycle in G based at v, so that αβ−1 ∈ K. Hence Kα = Kβ. So L is a well-defined labelling of the vertices. In fact, L is a bijection: Injectivity : Suppose L(w1) = L(w2). In other words, if α, β are paths in G starting at v and ending at w1, w2, respectively, then Kα = Kβ. It follows that αβ−1 ∈ K, i.e. that αβ−1 is a cycle in G. Hence the paths represented by α and β have the same end points, i.e. w1 = w2. Surjectivity : If Kα is a coset, let w ∈ V be the end point of the path represented by α and starting at v. Then L(w) = Kα. From now on, we identify vertices of G and cosets of K ≤ F using the function L. In particular, the vertex v that was fixed at the beginning of the proof is now referred to as K. It remains to check that, for each x ∈ X± and any Kξ,Kζ ∈ V , Kξ x−→ Kζ if and only if Kξx = Kζ; see also figure 4.5. 44 Nielsen–Schreier K Kξ Kζ ζξ x Figure 4.5: The labelling in the Schreier graph of K ≤ F Kξ x−→ Kζ ⇔the two paths represented by ξx, ζ starting at K have the same endpoint ⇔ξxζ−1 represents a cycle based at K ⇔ξxζ−1 ∈ K ⇔Kξx = Kζ, as required. Normal subgroups of free groups will play an important role in chapter 5. It will be useful to know what the Schreier graphs of such groups look like. Here we find a simple condition on Schreier graphs which characterises the normal subgroups. Definition 4.16. Every α ∈ F may be viewed as a translation function on G, sending the vertex Kξ to the vertex Kαξ. G is translation invariant if Kξ x−→ Kζ ⇔ Kαξ x−→ Kαζ for all words α ∈ F , all letters x ∈ X±, and all vertices Kξ,Kζ ∈ V . So G is translation invariant if it ‘looks the same everywhere’. We can now classify the Schreier graphs of normal subgroups of free groups: Proposition 4.17. Let F = F(X) be a free group, and let K ≤ F be a subgroup. Then K is normal if and only if the Schreier graph of K ≤ F is translation invariant. 4.3 Classifying Schreier graphs 45 Proof. ⇒ Suppose K is a normal subgroup of F . Let α, ξ, ζ ∈ F and x ∈ X± be arbitrary. Then Kξ x−→ Kζ ⇔ Kξx = Kζ ⇔ ξxζ−1 ∈ K ⇔ αξxζ−1α−1 ∈ K (as K is normal) ⇔ Kαζ = Kαξx ⇔ Kαξ x−→ Kαζ ⇐ If K is not normal in F , then there are α ∈ F and β ∈ K with αβα−1 6∈ K. As β can’t be the identity, we let x ∈ X± be the first X-letter of the X-reduction of β, and we define ζ = β−1x. Then xζ−1 = β ∈ K ⇒ Kx = Kζ ⇒ K x−→ Kζ. But, on the other hand, αxζ−1α−1 = αβα−1 6∈ K ⇒ Kαx 6= Kαζ ⇒ ¬(Kα x−→ Kαζ) Combining this result with proposition 4.15, we obtain a full classification. Corollary 4.18. The Schreier graphs of normal subgroups of free groups are precisely the regular, connected, and translation invariant digraphs. 46 Chapter 5 Nielsen–Schreier and the Axiom of Choice All proofs of the Nielsen–Schreier theorem use the Axiom of Choice, so it is natural to ask whether it is equivalent to the Axiom of Choice. In this chapter we attempt to answer this question. Section 5.1 gives a short account of all results that have been published in this area. In section 5.2 we analyse how the Axiom of Choice is used in the proof of theorem 4.11, as well as several other proofs. Many approaches are available to anyone who wants to deduce the Axiom of Choice from the Nielsen–Schreier theorem. One approach that comes to mind is to reverse-engineer the proof of the Nielsen–Schreier theorem given in chapter 4, i.e. to construct a spanning tree of a Schreier graph of K ≤ F from a basis of K. In section 5.3, we show that this is not possible. Section 5.4 presents a new proof that the Nielsen–Schreier theorem implies the Axiom of Finite Choice. For this proof we introduce counting homomorphisms and representative functions. They are a tool for constructing choice functions from bases of algebraic structures. The technique is sufficiently general, so that it can be used for free abelian 5.1 A brief history 47 groups in chapter 6. The results in section 5.4 are strengthened in section 5.5. We show that the Nielsen– Schreier theorem does not follow from the Boolean Prime Ideal Theorem. In particular, it doesn’t follow from the Finite Axiom of Choice. So the implication proved in section 5.4 cannot be reversed. The chapter is concluded by section 5.6, where we show, using the technology developed in section 5.4, that a strong form of the Nielsen–Schreier theorem is equivalent to the Axiom of Choice. 5.1 A brief history The first result concerning the relationship between NS and the Axiom of Choice was La¨uchli’s theorem using Fraenkel-Mostowski models, which was presented in section 2.2: Theorem 5.1 (La¨uchli [31]). NS is not a theorem of ZFA. This means that every proof of the Nielsen–Schreier theorem in set theory with atoms must use the Axiom of Choice. We saw in example 2.16 that ¬NS is a boundable state- ment. Hence the Transfer Theorem (theorem 2.17) immediately gives the corresponding result for ZF: Theorem 5.2. NS is not a theorem of ZF. In 1985, Howard proved a more specific result. He showed that Theorem 5.3 (Howard [16]). ZF ` NS⇒ ACfin. This is the strongest known theorem about the deductive strength of the Nielsen–Schreier theorem. However, two variations have been investigated, and both of them have turned out to be equivalent to the Axiom of Choice. Before stating the theorems, we need some definitions. 48 Nielsen–Schreier and the Axiom of Choice Definition 5.4 (Howard [16]). Let F = F(X) and B ⊆ F . B is level (with respect to X) if, for all β ∈ 〈B〉, β ∈ 〈{b ∈ B : `X(b) ≤ `X(β)}〉. B has the Nielsen property (with respect to X) if (i) B ∩B−1 = ∅, (ii) if b1, b2 ∈ B± and `X(b1b2) < `X(b1), then b2 = b−11 , (iii) if b1, b2, b3 ∈ B± and `X(b1b2b3) ≤ `X(b1) − `X(b2) + `X(b3), then b2 = b−11 or b3 = b −1 2 . The Nielsen–Schreier theorem guarantees the existence of bases of subgroups of free groups. We can strengthen it by placing restrictions on the kind of basis that it produces. For example, requiring it to be level or to have the Nielsen property gives us two new versions of the theorem, both of which are provable in ZFC. It turns out that they are equivalent to the Axiom of Choice in the presence of the other axioms of set theory: Theorem 5.5 (Howard [16], Howard [17]). (i) The statement If F = F(X) and K ≤ F is a subgroup, then there is a basis B of K which has the Nielsen property with respect to X. is equivalent to the Axiom of Choice. (ii) The statement If F = F(X) and K ≤ F is a subgroup, then there is a basis B of K which is level with respect to X. is equivalent to the Axiom of Choice Federer and Jonsson [8] showed that every set with the Nielsen property is level. Hence (ii) implies (i). 5.2 The use of the Axiom of Choice 49 No more papers in this area have been published since 1987. In the following sections we will improve, extend, and complement the known results. 5.2 The use of the Axiom of Choice When determining whether or not the Nielsen–Schreier theorem is equivalent to the Axiom of Choice, the first question that must be answered is: How much Choice do the known proofs use? If any of them doesn’t use the full Axiom of Choice, then there is no point in trying to show that NS is equivalent to AC. We will see in this section that the full Axiom of Choice is necessary for the standard proofs. The only invocation of AC was in the assertion that every Schreier graph has a spanning tree. It is well known that the existence of spanning trees in connected graphs is equiv- alent to the Axiom of Choice; see for example the paper by Delhomme´ and Morillon [7]. But not every graph is a Schreier graph. Is the class of Schreier graphs nevertheless large enough, so that this assertion requires the full Axiom of Choice? Proposition 5.6. The existence of spanning trees in regular connected graphs is equiv- alent to the Axiom of Choice. Proof. The Axiom of Choice implies that every connected regular graph has a spanning tree by a standard application of Zorn’s Lemma. For the converse, let S = {Xi : i ∈ I} be a family of non-empty sets. Without loss of generality, the Xi are pairwise disjoint. Let X = ⋃ i∈I Xi. We will construct a connected X-regular graph such that every spanning tree immediately gives a choice function for S. Let G′ = 〈V,E〉 be the graph defined as follows. V = I ∪ {∗}, where ∗ 6∈ I is arbitrary. For every i ∈ I and x ∈ X±i , E contains an edge labelled x from ∗ to i and an edge labelled x from i to ∗. The resulting graph is illustrated in figure 5.1. Any spanning tree T of G′ yields a choice function for S: For every i ∈ I there is only 50 Nielsen–Schreier and the Axiom of Choice ∗ i1 i2 i3 X±i3X ± i1 X±i2 I Figure 5.1: The graph G′ one branch in T connecting the vertices ∗ and i. This branch corresponds to a single element of Xi. However, G′ is not regular. To fix this, we add to each vertex as many loops (with suitable labels) as are necessary to make the graph X-regular, forming a new digraph G. Every spanning tree of G is a spanning tree of G′, because trees do not contain loops. Hence every spanning tree of G gives rise to a choice function for S. Now the classification of Schreier graphs in proposition 4.15 immediately yields: Theorem 5.7. The statement Every Schreier graph has a spanning tree is equivalent to the Axiom of Choice. We briefly mention several other proofs, and state why all of them use the full Axiom of Choice. Nielsen’s proof Nielsen’s proof [34] of the theorem for finitely generated free groups is generalised to the infinitely generated case in chapter 3 of Johnson’s book [25]. His proof relies on a well-ordering of the generating set of arbitrary free groups. Since any set can be used as a generating set, this requires the Well-ordering Principle. 5.2 The use of the Axiom of Choice 51 Schreier’s proof An English version of Schreier’s proof [39] is given in chapter 2 of Johnson’s textbook [25]. The underlying strategy of the proof is exactly the same as in the proof given in chapter 4, but it is written using exclusively algebraic language instead of trees in digraphs. The Axiom of Choice is used to find a Schreier transversal (see chapter 2 of Johnson [25] for the definition). However, Schreier transversals are just spanning trees of Schreier graphs in an algebraic costume. So, by theorem 5.7, the full Axiom of Choice is used. A topological proof A proof using covering spaces in algebraic topology is given in section 1.A of Hatcher [13]. If F = F(X) is a free group, then it is isomorphic to the fundamental group of a bouquet of circles indexed by elements of X. Every subgroup K ≤ F corresponds to a covering space of this topological space. It turns out that covering spaces are precisely the Schreier graphs of subgroups K ≤ F . A spanning tree of the graph is used to show that its fundamental group, K, is a free group. Again, the full Axiom of Choice is used to find a spanning tree of a Schreier graph. A proof using wreath products Ribes and Steinberg [38] used wreath products to prove the Nielsen–Schreier theorem. Their approach also requires the existence of a Schreier transversal, so, as in Schreier’s version, the full Axiom of Choice is used. But what about the theorem? Now we have seen that the standard proofs of the Nielsen–Schreier theorem all use the full Axiom of Choice. But this doesn’t mean that there is no proof which uses less 52 Nielsen–Schreier and the Axiom of Choice Choice. Question. Is the Nielsen–Schreier theorem equivalent to the Axiom of Choice? 5.3 Does Nielsen–Schreier imply the Axiom of Choice? If our aim is to deduce the Axiom of Choice from the Nielsen–Schreier theorem, one possible approach is to reverse engineer the proof of NS – to start from the statement of the theorem and to work backwards to the place in its proof where the Axiom of Choice is used. So we would like to know if it is possible to construct a spanning tree of the Schreier graph of K ≤ F = F(X) from a basis of K. In this section we show that this is not possible in general. The strategy is to find a Fraenkel-Mostowski model M containing a subgroup K of a free group F where K has a basis in M, but the Schreier graph of K ≤ F has no spanning tree in M. A suitable model is van Douwen’s model, described in section 2.3. It is constructed from a collection {〈Ai, a, and 54 Nielsen–Schreier and the Axiom of Choice K Kj A \ Aj A Ki A \ Ai A A A \ Aj A \ Ai A Aj Ai Aj Ai Figure 5.2: The Schreier graph of K write a− 1 for the greatest b ∈ A satisfying b < a. With this notation, the definition of B becomes much simpler: B = {a(a+ 1)−1 : a ∈ A}. We will show that B is a basis for K. (i) 〈B〉 = K. Let i < ω, and let a, b ∈ Ai. If a < b, we can write ab−1 = a(a+ 1)−1 · (a+ 1)(a+ 2)−1 · · · (b− 1)b−1. If a > b, we have ab−1 = (ba−1)−1 = (b(b+ 1)−1 · · · (a− 1)a−1)−1. It follows that {ab−1 : (∃i < ω) a, b ∈ Ai} ⊆ 〈B〉, i.e. that 〈B〉 = K. (ii) B is free. 5.3 Does Nielsen–Schreier imply the Axiom of Choice? 55 Associate each member a(a + 1)−1 ∈ B with an arrow from a to a + 1 and each (a+ 1)a−1 ∈ B−1 with an arrow from a+ 1 to a. This turns A into a digraph with connected components {Ai : i < ω}. Removing any b ∈ B and its inverse from the digraph disconnects one of the Ai. In other words, b 6∈ 〈B \ {b}〉. This means that no b ∈ B can be written as a product of other basis elements. Independence follows immediately: Suppose b1 · · · bn = 1 is a reduced B-word with n > 0 and b1, ..., bn ∈ B±. Then b1 = b−1n · · · b−12 , giving a contradiction. Combining lemmas 5.8 and 5.9 we get the following result: Theorem 5.10. There is a Fraenkel-Mostowski model M with a free group F and a subgroup K satisfying 1. The Schreier graph of K ≤ F has no spanning tree, 2. K has a basis B. This result is translated to ZF using the Transfer Theorem. Corollary 5.11. There is a model of ZF with a free group F and a subgroup K satisfying conditions 1. and 2. above. Proof. Write 〈F,1, ∗〉 for the free group F , and write φ(F,1, ∗, X,K) = X is a basis of F and the Schreier graph of 〈K,1, ∗|K〉 ≤ 〈F,1, ∗〉 has no spanning tree ψ(K,1, ∗, B) = B is a basis of 〈K,1, ∗|K〉 In example 2.15 we saw that ψ(K,1, ∗, B) is a boundable formula. It remains to show that φ(F,1, ∗, X,K) is also boundable. Of course, X is a basis of F is just ψ(F,1, ∗, X), which is boundable. Write G = 〈W,E〉 for the Schreier graph. 56 Nielsen–Schreier and the Axiom of Choice The vertex set W is the set of right cosets of K, so W ⊆ P(F ). Every edge of G can be written as a triple 〈w1, x, w2〉, where w1 ∈ W is the beginning, w2 ∈ W is the end, and x ∈ X± is the label of the edge. So each edge is an element of V4(W ∪X). Hence E ∈ V5(W ∪X), and G = 〈W,E〉 ∈ V7(W ∪X) ⊆ V8(F ∪X). In order to verify that G has no spanning tree it suffices to check every element of V8(F ∪X). So φ is boundable, as required. The corollary follows from the Transfer Theorem 2.17. This result shows that it is impossible to prove ZF ` NS⇒ AC by reducing the problem to the construction of a spanning tree in a Schreier graph from a basis of a subgroup K ≤ F . We conclude this section with one final remark. Notice that all elements of K have even A-length because the members of the generating set have length 2. Since all elements of the basis B constructed in the proof of lemma 5.9 have A-length 2, B is level. This is surprising in the light of theorem 5.5(ii), which says that the existence of level bases implies the Axiom of Choice. What is more, the property of being level is boundable, so it can be transferred to ZF. 5.4 Nielsen–Schreier implies the finite Axiom of Choice As stated in section 5.1, Howard [16] showed that ZF ` NS ⇒ ACfin. Here we prove a slightly stronger result with an entirely new proof. It is easier and shorter than Howard’s proof, and it introduces some general ideas that will be applied in later sections. Most of the material in this section also appears in Kleppmann’s article [29]. Representative functions In this section we give a general description of representative functions and counting functions which will also be used in several other sections. The details will vary, so it 5.4 Nielsen–Schreier implies the finite Axiom of Choice 57 doesn’t make sense to give precise definitions at this stage. But, as the fundamental mechanisms are always the same, we introduce the ideas by going over a simplified example. We are given a non-empty set y, and we would like to pick an element from y without making any choices. Let F = F(y) be the free group on y, and let K = 〈{wx−1 : w, x ∈ y}〉 ≤ F. Using NS, we may assume that K has a basis B, say. Notice that all members of K have even y-length, so w 6∈ K for all w ∈ y. But we can use B to find representatives of letters w ∈ y in the subgroup K. More precisely, we define a function f : y → K such that f(w) behaves like w in a suitably defined sense. To define f , let w ∈ y be arbitrary, and choose x ∈ y \ {w}. Since wx−1 ∈ K, we may write wx−1 = b1 · · · bn as a B-reduced word with b1, ..., bn ∈ B±. If n = 2k is even, we define f(w) = b1 · · · bk to be the ‘first half’ of wx−1 in terms of the new basis B. Intuitively, the first half of wx−1 should behave like w and the second half should behave like x−1. Under the right circumstances, f is well defined and wx−1 = f(w)f(x)−1. (5.1) Of course, f will not be well defined in general, and it is far from obvious that it will exhibit the correct behaviour. However, a careful choice of parameters does make it work. If this is the case, we define a new function g : y → F by g(w) = f(w)−1w. If (5.1) holds for all w, x ∈ y, then g is a constant function. Let α ∈ F be the value of g. It can be used to choose an element of y: As remarked earlier, w 6∈ K for all w ∈ y; it follows that f(w) 6= w for all w ∈ y, and that α 6= 1. So we can take the first letter of the y-reduction of α as the chosen element of y. 58 Nielsen–Schreier and the Axiom of Choice Counting homomorphisms Let Y be a family of non-empty pairwise disjoint sets, let X = ⋃ Y , and let F = F(X) be the free group on X. It will be useful to count letters of words α ∈ F . To this end we define, for each y ∈ Y , a counting function #y : F → Z. If α ∈ F , we may write α = x11 · · ·xnn as an X-reduced word with x1, ..., xn ∈ X and 1, ..., n ∈ {1,−1}. Then #y(α) is equal to the sum of exponents of y-letters in α: #y(α) = ∑ i:xi∈y i. It is easy to check that each #y is a group homomorphism from F to the additive group of integers. We now have the tools necessary for the proof. The proof As we will be concerned with normal subgroups of free groups, we introduce a new choice principle: NSnorm (Nielsen–Schreier for normal subgroups): If F is any free group and K ≤ F is any normal subgroup, then K is a free group. This principle only makes a statement about normal subgroups of free groups, so it is weaker than NS. Hence the implication NSnorm ⇒ ACfin proved here is at least as strong as the already known implication NS⇒ ACfin. Before proving the full theorem, we must handle a special case. Lemma 5.12. ZF ` NSnorm ⇒ AC2. Proof. Let Y be a family of pairwise disjoint 2-element sets. Let X = ⋃ Y , let F = F(X) be the free group on X, and define the subgroup K ≤ F by K = ⋂ {ker(#y) : y ∈ Y }. K is non-trivial, because it contains, for example, wx−1 for each y = {w, x} ∈ Y . 5.4 Nielsen–Schreier implies the finite Axiom of Choice 59 Moreover, as kernels of homomorphisms are normal, so is K. By NSnorm, there is a basis B for K. Let y ∈ Y be arbitrary but fixed. We shall show how to single out one element of y without making any choices. Define the swapping function sy : y → y to transpose the two elements of y. For any x ∈ y, we have y = {x, sy(x)}. To simplify notation, we write xi = s i y(x) for i ∈ Z, so that y = {x0, x1}. Since x0x−11 , x1x−10 ∈ K, we may write x0x −1 1 = b0,1 · · · b0,`0 x1x −1 0 = b1,1 · · · b1,`1 , as reduced B-words, where the bi,j ∈ B±. From x0x−11 = (x1x−10 )−1 we deduce that `0 = `1 = `, say, and that b1,1 = b −1 0,` , ..., b1,` = b −1 0,1. (5.2) There are two cases: (1) ` is odd. Set k = (`− 1)/2. The middle B-letter of x0x−11 is b0,k+1, while the middle B-letter of x1x −1 0 is b1,k+1 = b −1 0,k+1. Just one of these two is an element of B. The chosen element of y is the unique xi such that the middle B-letter of xix −1 i+1 is in B (and not in B−1). (2) ` is even. Let k = `/2. Define the representative function fy and its companion gy as follows: fy : y → K : xi 7→ bi,1 · · · bi,k gy : y → F : xi 7→ fy(xi)−1xi. Then fy(x0)fy(x1) −1 = b0,1 · · · b0,kb−11,k · · · b−11,1 = b0,1 · · · b0,kb0,k+1 · · · b0,l (by (5.2)) = x0x −1 1 , 60 Nielsen–Schreier and the Axiom of Choice so gy(x0) = gy(x1), and gy is a constant function taking just one value, αy, say. We check that αy mentions letters from y: #y(αy) = #y(fy(x0) −1x0) = #y(x0)−#y(fy(x0)) = 1− 0 (as x0 ∈ y and fy(x0) ∈ K ≤ ker(#y).) Since #y(αy) = 1, αy mentions at least one y-letter. So we choose an element of y by picking the first y-letter appearing in αy. This proof serves as an introduction to ideas used in the main proof. The general case is more complicated and requires more structure to carry out the argument using representative functions. Proposition 5.13. ZF ` NSnorm ⇒ ACfin. Proof. Let Z be a set of finite non-empty sets. We will find a choice function for Z by induction on the size of its members. In order to do this, it will be useful to close Z under non-empty subsets. So let Y = {y : y 6= ∅ ∧ (∃z ∈ Z)y ⊆ z}. As Z ⊆ Y , it suffices to find a choice function for Y . Replacing each y ∈ Y with y×{y}, we may assume that the members of y are pairwise disjoint. Let X = ⋃ Y , let F = F(X) be the free group on X, and let K ≤ F be the subgroup defined by K = ⋂ {ker(#y) : y ∈ Y }. As in lemma 5.12, K is a non-trivial normal subgroup of F . By NSnorm, K has a basis B, say. For each n such that 2 ≤ n < ω, write Y (n) = {y ∈ Y : |y| = n} and Y (≤n) = {y ∈ Y : |y| ≤ n}. By induction on n, we will find nested choice functions cn on Y (≤n) for each n < ω. Then ⋃ n<ω cn is a choice function for Y . 5.4 Nielsen–Schreier implies the finite Axiom of Choice 61 By lemma 5.12 there is a choice function c2 on Y (≤2). So assume that n ≥ 3 and that there is a choice function cn−1 on Y (≤n−1). For every y ∈ Y (n) we define a function sy as follows: sy : y → y : x 7→ cn−1(y \ {x}). Note that y \ {x} ∈ Y (n−1), because Y is closed under taking non-empty subsets, so cn−1(y \ {x}) is defined. There are four cases: (i) sy is not a bijection. In this case, |sy“y| ≤ n− 1, so defining cn(y) = cn−1(sy“y) gives a choice of element of y. Again, this is well-defined, because Y is closed under taking non-empty subsets. (ii) sy is a bijection with at least two orbits. 1 As sy(x) 6= x for all x ∈ y, the number of orbits is ≤ n− 1. But, since there are at least two orbits, the size of each orbit is also ≤ n − 1. So we can choose a single element of y by picking a point from each orbit, and then picking one from among them. More precisely, we define cn(y) = cn−1({cn−1(orb(x)) : x ∈ y}), where orb(x) is the orbit of x ∈ y under the action of sy. (iii) sy is a bijection with one orbit, and n is even. If n is even, s2y is a bijection with two orbits. Remembering that we are assuming n ≥ 3, this gives us ≤ n− 1 orbits of size ≤ n− 1 each. A choice is made as in the previous case. (iv) sy is a bijection with one orbit, and n is odd. For any x ∈ y, y = {x, sy(x), s2y(x), ..., sn−1y (x)}. For simplicity, we write xi = siy(x) for i ∈ Z, so that y = {x0, x1, ..., xn−1}. 1Thank you to Thomas Forster for suggesting a simplification to this part of the proof. 62 Nielsen–Schreier and the Axiom of Choice Recall the basis B of K. We may write x0x −1 1 = b0,1 · · · b0,`0 x1x −1 2 = b1,1 · · · b1,`1 ... xn−1x−10 = bn−1,1 · · · bn−1,`n−1 as reduced B-words, with the bi,j ∈ B±. Before defining a representative function, we must prepare the ground. This is done in two steps: (1) If it is not the case that `0 = ... = `n−1, let ` = min{`i : i = 0, ..., n− 1}. Then {xi : `i = `} is a proper non-empty subset of y, and we define cn(y) = cn−1({xi : `i = `}). From now on, we assume `0 = ... = `n−1 = `. (2) Note that (x0x −1 1 )(x1x −1 2 ) · · · (xn−1x−10 ) = 1, i.e. (b0,1 · · · b0,`)(b1,1 · · · b1,`) · · · (bn−1,1 · · · bn−1,`) = 1. (5.3) For i = 0, ..., n− 1, let ki be the number of B-cancellations in (bi,1 · · · bi,`)(bi+1,1 · · · bi+1,`). (5.4) If it is not the case that k0 = ... = kn−1, let k = min{ki : i = 0, ..., n − 1}. Then {xi : ki = k} is a proper non-empty subset of y, and we define cn(y) = cn−1({xi : ki = k}). From now on, we assume k0 = ... = kn−1 = k. As letters always cancel in pairs, (5.3) implies that n` is even.2 Since we are assuming that n is odd, it follows that ` is even. Define m = `/2, and note that 2I would like to thank John Truss and Benedikt Lo¨we for finding an error in this proof and suggesting a solution. 5.5 Nielsen–Schreier doesn’t follow from the Prime Ideal Theorem 63 k ≥ m: if not, then complete cancellation in (5.3) would not be possible. Now we can define a representative function fy and its companion function gy: fy : y → K : xi 7→ bi,1 · · · bi,m gy : y → F : xi 7→ x−1i fy(xi). Since there are k ≥ m cancellations in (5.4), we have bi+1,1 = b−1i,` , ..., bi+1,m = b−1i,`−m+1 = b −1 i,m+1. This implies that fy(xi)fy(xi+1) −1 = xix−1i+1 for each i. Hence gy(xi) = gy(xi+1) for all i, and gy : y → F is again constant. If we let αy be the constant value of gy, then #y(αy) = 1, so αy mentions at least one element of y. As in lemma 5.12, we choose an element of y by picking the first y-letter appearing in αy. Finiteness was used in this proof to define the functions sy, giving a cyclic ordering of each finite set. Using this structure, it was possible to define the representative function. If we try to prove NS ⇒ AC, it seems likely that a similar structure could be used to define representative functions. But, as this remains an unsolved problem, we will employ the Fraenkel–Mostowski method to strengthen proposition 5.13 in the next section. 5.5 Nielsen–Schreier doesn’t follow from the Prime Ideal Theorem We have seen that NSnorm implies the Axiom of Choice for families of non-empty finite sets. So AC⇒ NS⇒ NSnorm ⇒ ACfin. 64 Nielsen–Schreier and the Axiom of Choice From what we have seen so far, it is possible that NS is equivalent to ACfin. However, in this section we shall see that NSnorm does not follow from the Boolean Prime Ideal Theorem (defined in chapter 1.5). As ZF ` BPIT ⇒ ACfin, it follows immediately that NSnorm, and hence also NS, are strictly stronger than ACfin. The material in this section is adapted from Kleppmann [28]. Our aim is to find a model of ZF set theory in which the Boolean Prime Ideal Theo- rem holds and NSnorm fails. Using the Transfer Theorem, it suffices to find a Fraenkel– Mostowski satisfying these properties. We can build on the work of Dawson and Howard, who introduced the Dawson–Howard model (see section 2.3) and showed that the Boolean Prime Ideal Theorem holds in it. It remains to be shown that NSnorm fails in this model. For the rest of this section, we write M for the Dawson–Howard model. Recall that the set A of atoms in M is constructed by taking a family {〈Ai, 0 be integers. Then ZF ` ACnk ⇒ ACn. Let {Xi : i ∈ I} be a family of n-element sets. Then {Xki : i ∈ I} is a family of nk-element sets. Using ACnk , there is a function f defined on I such that f(i) = 〈f1(i), ..., fk(i)〉 ∈ Xki for each i ∈ I. f1 is a choice function for the original family {Xi : i ∈ I}. Now let S = {Xi : i ∈ I} be a family of non-empty sets. For each n with 0 < n < m, let S(n) = {Xi : |Xi| = n}, and let T = S \ ⋃ n0 nibi, n(β) = ∑ i:ni<0 nibi. Here are some basic properties of p and n: 1. For all β ∈ K, β = p(β) + n(β). 2. Multiplication by −1 swaps positive and negative parts: −n(−β) = p(β) and −p(−β) = n(β) for all β ∈ K. 3. The functions p, n : K → K are not group homomorphisms: Pick any b ∈ B and define β1 = −b, β2 = 2b. Then p(β1 +β2) = p(b) = b while p(β1)+p(β2) = 0+2b = 2b. Similarly, n(β1 + β2) 6= n(β1) + n(β2). We have now defined all of the tools necessary to prove our next result. Proposition 6.5. ZF ` NSab ⇒ AC2 6.2 Abelian Nielsen–Schreier implies AC2 77 Proof. Recall that Y is a family of pairwise disjoint 2-element sets. Fix a member y ∈ Y . We will find a way of picking one of its elements without making any choices. Write y = {x0, x1}. After stipulating that i ≡ j (mod 2) ⇒ xi = xj, it makes sense to talk about points xi ∈ y, where i ∈ Z. This convention will improve readability later in the proof. Now define the representative function fy by fy : y → K : xi 7→ p(xi − xi+1). On a superficial intuitive level, it makes sense to associate xi with the positive part of xi−xi+1 and −xi+1 with the negative part of xi−xi+1. Amazingly, this definition works. As usual, fy comes with its companion function gy, defined by gy : y → F : x 7→ x− fy(x). fy exhibits the good behaviour that we have come to expect from it: fy(xi)− fy(xi+1) = p(xi − xi+1)− p(xi+1 − xi+2) = p(xi − xi+1) + n(xi+2 − xi+1) = p(xi − xi+1) + n(xi − xi+1) = xi − xi+1 Hence gy(x0) = gy(x1) and gy is a constant function. Let αy be the single element of its image. Then #y(αy) = #y(x0 − fy(x0)) = #y(x0)−#y(fy(x0)) (#y is a homomorphism) = 1 (x0 ∈ y and fy(x0) ∈ K ≤ ker(#y)) So, when writing αy as a Z-linear combination of basis elements x ∈ X, the coefficients of x0 ∈ y and x1 ∈ y cannot be equal. For if they were, they would both have to be 1/2. An element of y is chosen by picking the member with the larger coefficient in αy. 78 Free abelian groups 6.2 The implication is strict Let M be the Dawson–Howard model described in section 2.3. We saw in corollary 5.16 that M |= BPIT ∧ ¬NS. In this section, we show that M |= ¬NSab. In particular, this means that, just like NS, NSab does not follow from BPIT, and that the implication ZF ` NSab ⇒ AC2 cannot be reversed. In order to prove the failure of NSab in the Dawson–Howard model, let F = FA(A) be the free abelian group on A, the set of atoms in M. Define the usual subgroup K = ⋂ {ker(#Ai) : i < ω} ≤ F, where the counting functions #Ai are defined in section 6.1. If M |= NSab, then K has a basis B with finite support E ⊆ A. We will derive a contradiction. Recall definition 3.6, where we defined the set of A-components of α = n1a1 + ...+ nkak, where a1, ..., ak ∈ A are distinct and n1, ..., nk ∈ Z \ {0}, to be CA(α) = {a1, ..., ak}. Definition 6.6. If β is any element of the subgroup K, write β = n1b1 + ... + nkbk, where b1, ..., bk ∈ B are distinct and n1, ..., nk ∈ Z \ {0}. The set of A-components of β via B is CBA (β) = ⋃k i=1 CA(bi). Example 6.7. Let i < ω, let a, b, c, d ∈ Ai be distinct, and suppose that {a − b + c − d, c − d} ⊆ B. Defining β = a − b ∈ K, we see immediately that CA(β) = {a, b}. Moreover, since β = (a− b+ c− d)− (c− d) in terms of B, CBA (β) = {a, b, c, d}. Note that the sets CA(α) and CBA (β) are always finite, whatever the choice of α ∈ F and β ∈ K. Moreover, (∀β ∈ K) CA(β) ⊆ CBA (β). As example 6.7 shows, this inclusion may be strict. We now describe the ideas behind the proof. Our aim is to find β ∈ K which can be expressed as a Z-linear combination of elements of B in two different ways, giving the required contradiction. We will find an element β = a1 − a2 of K such that the set of 6.2 The implication is strict 79 A-components of β contains a point a 6∈ E ∪ {a1, a2} (where E is the support of B). There are permutations of A which move a while at the same time fixing E ∪ {a1, a2}. Such permutations fix β, but they don’t fix its B-components. This gives two different B-expressions for β. Having seen the strategy of the proof, we are now ready to prove some lemmas before moving on to the main theorem. Lemma 6.8. Let β ∈ K and j < ω be arbitrary. Then |CA(β) ∩ Aj| is either 0 or ≥ 2. Proof. Suppose there is β ∈ K and j < ω with |CA(β) ∩ Aj| = 1. Write β = n1a1 + ... + nkak, where a1, ..., ak ∈ A are distinct and n1, ..., nk ∈ Z \ {0}. After reordering if necessary, a1 ∈ Aj and a2, ..., ak 6∈ Aj. It follows that #Aj(β) = n1 6= 0, contradicting β ∈ K ≤ ker(#Aj). Lemma 6.9. There are a1, a2 ∈ A with a1 − a2 ∈ K and CBA (a1 − a2) 6⊆ E ∪ {a1, a2}. Proof. Let j < ω be such that E ∩ Aj = ∅, and let a1, a2, a3 ∈ Aj be arbitrary and distinct. (In particular, a1, a2, a3 6∈ E). If CBA (a1 − a3) 6⊆ E ∪ {a1, a3} or CBA (a2 − a3) 6⊆ E ∪ {a2, a3}, then we are done. So assume that CBA (a1 − a3) ⊆ E ∪ {a1, a3} and CBA (a2 − a3) ⊆ E ∪ {a2, a3}. Write a1 − a3 = n1b1 + ...+ nkbk (6.2) a2 − a3 = n′1b′1 + ...+ n′k′b′k′ , (6.3) where the bi ∈ B are distinct, the b′i ∈ B are distinct, and ni, n′i ∈ Z \ {0}. Since E ∩ Aj = ∅, CBA (a1 − a3) ⊆ E ∪ {a1, a3} implies that CBA (a1 − a3) ∩ Aj ⊆ {a1, a3}. This gives CA(bi) ∩ Aj ⊆ {a1, a3} for i = 1, ..., k. 80 Free abelian groups By lemma 6.8, CA(bi) ∩ Aj is either ∅ or {a1, a3} for each i = 1, ..., k. In other words, the bi either mention neither a1 nor a3, or they mention both. Since the left-hand side of (6.2) mentions a1 and a3, at least one of the bi mentions both. By rearranging the sum, we may assume that this is b1. Subtracting (6.3) from (6.2), we obtain a1 − a2 = n1b1 + ...+ nkbk − (n′1b′1 + ...+ n′k′b′k′). (6.4) Since CBA (a2 − a3) ⊆ E ∪ {a2, a3}, b1 isn’t equal to any of b′1, ..., b′k′ . Hence it doesn’t cancel out when reducing the right-hand side of (6.4) with respect to B. So a3 ∈ CA(b1) ⊆ CBA (a1 − a2), proving that CA(a1 − a2) 6⊆ E ∪ {a1, a2}, as required. Theorem 6.10. M |= ¬NSab. Proof. By lemma 6.9, let a1, a2 ∈ A be such that β = a1 − a2 ∈ K and CBA (β) 6⊆ E ∪ {a1, a2}. Write β = n1b1 + ... + nkbk, where n1, ..., nk ∈ Z \ {0} and b1, ..., bk ∈ B are distinct. By reordering the summands, we may assume that CA(b1) 6⊆ E ∪ {a1, a2}. Let a ∈ CA(b1)\ (E∪{a1, a2}). Since {pi(a) : pi ∈ fix(E∪{a1, a2})} is infinite and CBA (β) is finite, there is pi ∈ fix(E ∪ {a1, a2}) with pi(a) 6∈ CBA (β). Now n1b1 + ...+ nkbk = β = pi(β) (as pi ∈ fix({a1, a2})) = n1pi(b1) + ...+ nkpi(bk), so n1b1 + ...+ nkbk − (n1pi(b1) + ...+ nkpi(bk)) = 0. (6.5) We have arranged pi ∈ fix(E), so pi(b1), ..., pi(bk) ∈ B. Moreover, the pi(bi) are distinct, as the bi were chosen to be distinct. By the choice of pi, we have pi(a) 6∈ CBA (β), which shows that pi(b1) 6∈ {b1, ..., bk}. Hence at least the one summand n1pi(b1) remains when reducing the left-hand side of equation (6.5) with respect to B. Since n1 6= 0, (6.5) is a non-trivial B-expression for 0, so that B is no basis after all. This is the required contradiction. 6.3 More on representative functions 81 We saw in example 2.16 that ¬NS is a transferable statement. A Similar argument shows that ¬NSab is also transferable. Thus: Corollary 6.11. ZF 6` BPIT⇒ NSab In particular, as BPIT ⇒ AC2, this shows that the implication NSab ⇒ AC2 is not reversible. 6.3 More on representative functions In this section we do not prove any new results. Instead, we present work that might lead to stronger and more general results in the future. The foundations for this section were laid in section 6.1 where we deduced AC2 from NSab by finding representative functions for sets of size 2. Here we will construct representative functions for sets of any finite size. Recall the set-up from section 6.1: We start with a family Y of pairwise disjoint non- empty finite sets. Then we let X = ⋃ Y , F = FA(X), and K = ⋂{ker(#y) : y ∈ Y }. Using NSab, we obtain a basis B for K. As the general case is rather involved, we present the construction for a family 3-element sets first. This special case illustrates all of the main ideas needed for the full construc- tion. Example 6.12. Assume Y is a family of pairwise disjoint 3-element sets. Let y ∈ Y , and write it as y = {x0, x1, x2}. We will use the indices 0, 1, 2 to distinguish the elements of y, but we will not use them to choose from among them, or to put them in a certain order. Define β0 = 2x0 − x1 − x2, β1 = −x0 + 2x1 − x2, β2 = −x0 − x1 + 2x2. 82 Free abelian groups Each βi distinguishes xi from the other elements of y by putting more weight on xi. Inspired by their shape, we call such elements of a free abelian group spikes. Note that β0, β1, β2 ∈ K and β0 + β1 + β2 = 0. The representative function fy : y → K is given by fy(x0) = p(β0)− n(β1)− n(β2) fy(x1) = −n(β0) + p(β1)− n(β2) fy(x2) = −n(β0)− n(β1) + p(β2) Let us define the companion function to fy by gy : y → F : xi 7→ 3xi − fy(xi). Our aim is to use fy to show that gy is a constant function. For this purpose we will need the following equality: 2fy(x0)− fy(x1)− fy(x2) = (2p(β0) + n(β0) + n(β0)) + (−2n(β1)− p(β1) + n(β1)) + (−2n(β2) + n(β2)− p(β2)) = 2β0 − β1 − β2 = 3β0 − (β0 + β1 + β2) = 3β0 = 3(2x0 − x1 − x2). Similar calculations show that −fy(x0) + 2fy(x1)− fy(x2) = 3(−x0 + 2x1 − x2) and −fy(x0)− fy(x1) + 2fy(x2) = 3(−x0 − x1 + 2x2). These three equalities are summarised by the following matrix equation: 2 −1 −1 −1 2 −1 −1 −1 2   gy(x0) gy(x1) gy(x2)  = 0. 6.3 More on representative functions 83 By elementary linear algebra, it follows that gy(x0) = gy(x1) = gy(x2), i.e. that g is a constant function, as desired. Having seen this special case, it is straightforward to find a generalisation for any family Y of pairwise disjoint non-empty finite sets. Let y ∈ Y be arbitrary, and suppose |y| = n ≥ 2. Writing y = {x0, ..., xn−1}, we define, for each i = 0, ..., n− 1 a spike βi = (n− 1)xi − ∑ j 6=i xj, a representative function fy : y → K : xi 7→ p(βi)− ∑ j 6=i n(βj), and a companion function gy : y → F : xi 7→ nxi − fy(xi). Fix any i ∈ {0, ..., n− 1}. Then (n− 1)fy(xi)− ∑ k 6=i fy(xk) = (n− 1) ( p(βi)− ∑ j 6=i n(βj) ) − ∑ k 6=i ( p(βk)− ∑ l 6=k n(βl) ) = (n− 1)p(βi)− ∑ j 6=i ((n− 1)n(βj) + p(βj)) + ∑ k 6=i ∑ l 6=k n(βl) There are n− 1 pairs 〈k, l〉 where k 6= i, and l 6= k, and l = i. So = (n− 1)(p(βi) + n(βi))− ∑ j 6=i ((n− 1)n(βj) + p(βj)) + ∑ k 6=i ∑ l 6=i,k n(βl) 84 Free abelian groups For each j 6= i there are n− 2 pairs 〈k, l〉 where k 6= i, and l 6= i, k, and l = j. So = (n− 1)(p(βi) + n(βi))− ∑ j 6=i ((n− 1)n(βj) + p(βj)− (n− 2)n(βj)) = (n− 1)(p(βi) + n(βi))− ∑ j 6=i (p(βj) + n(βj)) = (n− 1)βi − ∑ j 6=i βj = nβi − ∑ j βj = nβi = n ( (n− 1)xi − ∑ k 6=i xk ) . In summary, we have (n − 1)fy(xi) − ∑ k 6=i fy(xk) = n ( (n− 1)xi − ∑ k 6=i xk ) for all i = 0, ..., n− 1. As in the earlier example, this gives a matrix equation n− 1 −1 . . . −1 −1 n− 1 . . . −1 ... ... . . . ... −1 −1 . . . n− 1   gy(x0) gy(x1) ... gy(xn−1)  = 0, which in turn implies that gy is a constant function by elementary linear algebra. In order to pick a single element of y, our standard procedure is to let αy be the constant value of gy. Then #y(αy) = #y(nx0 − fy(x0)) = n 6= 0 implies that αy mentions letters from y. If we were dealing with free groups, we could choose an element of y by picking the first y-letter appearing in αy. But in free abelian groups, it is no longer possible to use the ordering of letters to make a choice. Instead, we must distinguish the letters by their coefficients in αy. If we could guarantee that the y-letters appearing in αy don’t all have the same coefficient, then ACfin could be deduced from NSab. The above construction of representative functions works for vector spaces over fields whose characteristic does not divide n. This might give a fresh point of view on state- ments of current interest, such as B(F ) (existence of bases): Every F -vector space has a basis. 6.3 More on representative functions 85 Blass [1] showed that the Axiom of Choice follows from (∀F )B(F ). However, if we restrict our attention to B(F ) for a particular field F , such as the two-element field F2 or the rationals Q, then we obtain a weaker Choice principle. A list of open questions relating to this principle is given at the end of Howard and Tachtsis [20]. Among them are: Question. Is there a field F for which B(F ) implies AC? Question. Is there a field F for which B(F ) does not imply AC? The literature only offers partial answers. Keremedis [26] showed that B(Q) implies that every infinite well-ordered set of two-element sets has an infinite subset with a choice function. Later, Howard [18] proved that B(F2) implies that every well-ordered collection of two-element sets has a choice function. This was improved by Morillon [33], who deduced AC2 from B(F2). (This is not stated explicitly, but it is implicit in the proofs.) The most recent paper in this field is Howard and Tachtsis [20]. They showed that, for every field F in the Dawson–Howard model there is an F -vector space with no basis. To end this chapter, I would like to formulate a conjecture. Its proof would be a sig- nificant improvement of the results published in the past few years. Representative functions seem to be a promising tool for attacking it. Conjecture. If F is a field of characteristic 0, then ZF ` B(F )⇒ ACfin. 86 Bibliography [1] A. Blass. Existence of bases implies the Axiom of Choice. Contemporary Mathe- matics, 31:31–33, 1984. [2] B. Bolloba´s. Graph theory : an introductory course. Springer Verlag, New York, 1979. [3] P. J. Cohen. The Independence of the Continuum Hypothesis. Proc. Natl. Acad. Sci. USA, 50(6):1143–1148, 1963. [4] P. J. Cohen. The Independence of the Continuum Hypothesis, II. Proc. Natl. Acad. Sci. USA, 51(1):105–110, 1964. [5] P. M. Cohn. Classic algebra. Wiley, 2000. [6] J. W. Dawson and P. Howard. Factorials of infinite cardinals. Fundamenta Mathe- maticae, 93:186–195, 1976. [7] C. Delhomme´ and M. Morillon. Spanning graphs and the Axiom of Choice. Reports on Mathematical Logic, 40:165–180, 2006. [8] H. Federer and B. Jonsson. Some properties of free groups. Transactions of the American Mathematical Society, 68:1–27, 1950. [9] M. Hall. Combinatorial Theory. Wiley Classics Library. Wiley, 1998. [10] P. Hall. On representatives of subsets. Journal of the London Mathematical Society, 10:26–30, 1935. 87 [11] J. Halpern. Bases in vector spaces and the Axiom of Choice. Proceedings of the American Mathematical Society, 17:670–673, 1966. [12] J. Halpern. On a question of Tarski and a maximal theorem of Kurepa. Pacific Journal of Mathematics, 41:111–121, 1972. [13] A. Hatcher. Algebraic Topology. Cambridge University Press, 2002. [14] H. Herrlich. Axiom of Choice. Springer Verlag, Berlin, Heidelberg, 2006. [15] P. Howard. Limitations on the Fraenkel-Mostowski method of independence proofs. Journal of Symbolic Logic, 38:416–422, 1973. [16] P. Howard. Subgroups of a Free Group and the Axiom of Choice. Journal of Symbolic Logic, 50:458–467, 1985. [17] P. Howard. The existence of level sets in a free group implies the Axiom of Choice. Zeitschrift fu¨r mathematische Logik und Grundlagen der Mathematik, 33:315–316, 1987. [18] P. Howard. Bases, spanning sets, and the Axiom of Choice. Mathematical Logic Quarterly, 53(3):247–254, 2007. [19] P. Howard and J. E. Rubin. Consequences of the Axiom of Choice. American Mathematical Society, 1998. [20] P. Howard and E. Tachtsis. On vector spaces over specific fields without choice. Mathematical Logic Quarterly, 59(3):128–146, 2013. [21] T. Jech. Set Theory: The Third Millennium Edition. Springer, 2003. [22] T. Jech. The Axiom of Choice. Dover Publications, Inc., 2008. [23] T. Jech and A. Sochor. Applications of the θ-model. Bulletin de l’Acade´mie Polon- aise des Sciences: Se´rie des sciences mathe´matiques, astronomiques, et physiques, 14:351–355, 1966. 88 [24] T. Jech and A. Sochor. On θ-model of the set theory. Bulletin de l’Acade´mie Polon- aise des Sciences: Se´rie des sciences mathe´matiques, astronomiques, et physiques, 14:297–303, 1966. [25] D. L. Johnson. Presentations of Groups. London Mathematical Society Student Texts. Cambridge University Press, 1997. [26] K. Keremedis. The Vector Space Kinna–Wagner Principle is Equivalent to the Axiom of Choice. Mathematical Logic Quarterly, 47(2):205–210, 2001. [27] P. Kleppmann. Generating sets of free groups and the axiom of choice. Mathematical Logic Quarterly, 60:239–241, 2014. [28] P. Kleppmann. Nielsen-Schreier and the Axiom of Choice. Mathematical Logic Quarterly, 2015. doi: 10.1002/malq.201400046. [29] P. Kleppmann. Nielsen-Schreier implies the finite Axiom of Choice, June 2015. arXiv:1506.03435v2 [math.LO]. [30] S. Lang. Algebra. Graduate Texts in Mathematics. Springer, 3rd edition edition, 2005. [31] H. La¨uchli. Auswahlaxiom in der Algebra. Commentarii Mathematici Helvetici, 37:1–18, 1962. [32] E. Mendelson. Introduction to Mathematical Logic. D. Van Nostrand Company, Inc., 1964. [33] M. Morillon. Linear forms and axioms of choice. Commentationes Mathematicae Universitatis Carolinae, 50(3):421–431, 2009. [34] J. Nielsen. Om Regning med ikke-kommutative Faktorer og dens Anvendelse i Gruppeteorien. Matematisk Tidsskrift, B:77–94, 1921. [35] D. Pincus. Zermelo-Fraenkel Consistency Results by Fraenkel-Mostowski Methods. Journal of Symbolic Logic, 37:721–743, 1972. 89 [36] D. Pincus. Adding Dependent Choice. Annals of Mathematical Logic, 11:105–145, 1977. [37] D. Pincus. Adding Dependent Choice to the Prime Ideal Theorem. Logic Collo- quium, 76:547–565, 1977. [38] L. Ribes and B. Steinberg. A Wreath Product Approach to Classical Subgroup Theorems, December 2008. arXiv:0812.0027v2 [math.GR]. [39] O. Schreier. Die Untergruppen der freien Gruppen. Abhandlungen aus dem Math- ematischen Seminar der Universita¨t Hamburg, 5:161–183, 1927. [40] E. K. van Douwen. Horrors of topology without AC: A non-normal orderable space. Proceedings of the American Mathematical Society, 95(1):101–105, 1985. [41] E. Zermelo. Beweis, dass jede Menge wohlgeordnet werden kann. Mathematische Annalen, 59(4):514–516, 1904.