$F$ is a free abelian group on a set $X$ , $H \subseteq F$ is a free abelian group on $Y$, then $|Y| \leq |X|$

I am confused by the proof a proposition:

$F$ is a free abelian group on a set $X$ and $H$ is a subgroup of $F$, then $H$ is free abelian on a set $Y$, where $|Y| \leq |X|.$

The proof is:

Let $X$ be well-ordered in some fashion, say as $\{ x_{\alpha} | \alpha < \beta \}$ where $\beta$ is an ordinal number. Define $F_{\alpha} = \langle x_{\gamma} | \gamma < \alpha \rangle$: then $F_{\alpha+1} = F_{\alpha} \oplus \langle x_{\alpha} \rangle$ and $F_{\beta} = F$. Writing $H_{\alpha}$ for $H \cap F_{\alpha}$, we have from the second isomorphism theorem $$H_{\alpha+1}/H_{\alpha} \cong (H \cap F_{\alpha+1})F_{\alpha}/F_{\alpha} \leq F_{\alpha+1}/F_{\alpha} \cong \langle x_{\alpha} \rangle.$$ Thus, either $H_{\alpha} = H_{\alpha+1}$ or $H_{\alpha+1}/H_{\alpha}$ is infinite cyclic. We may therefore write $H_{\alpha+1} = H_{\alpha} \oplus \langle y_{\alpha} \rangle$ where $y_{\alpha}$ may be $0$. Clearly $H$ is the direct sum of the $\langle y_{\alpha} \rangle$'s and $H$ is free on the set $Y = \{ y_{\alpha} \neq 0| \alpha < \beta \}$.

I don't know why can $X$ be well-ordered. Also, in the proof, the author defines $F_{\alpha+1}$. Does this mean considering $X$ as being countable? In fact, $X$ is just a set in the proposition, and we do not know whether or not $X$ is well-ordered/countable.

Would you please give me some explanation or hint as to my confusion? Thanks very much.

[On Page 100 and 101 of A Course in the Theory of Groups written by Derek J.S. Robinson, GTM80]

-
You wrote: I don't know why can X be well-ordered. See en.wikipedia.org/wiki/Well-ordering_principle - this can be derived from Axiom of Choice. (In fact, WO and AC are equivalent.) – Martin Sleziak Nov 11 '11 at 11:54
As Martin says in the comment above, given the Axiom of Choice, any set can be well ordered. Once this is done, one can use Transfinite induction: en.wikipedia.org/wiki/Transfinite_induction – Bill Cook Nov 11 '11 at 12:02
It is important to add, without the axiom of choice it is consistent to have a free group whose commutator subgroup is not free, so the use of the axiom of choice here is essential. – Asaf Karagila Nov 11 '11 at 12:51
this is strange... $\mathbb F_2$ contains a copy of $\mathbb F_3$.. – Valerio Capraro Nov 11 '11 at 22:14

There are three issues here: well-ordering, ordinals, and transfinite induction.

Theorem. The following are equivalent in ZF:

(i) The Axiom of Choice: Given a nonempty family of nonempty sets $\{A_i\}_{i\in I}$, there exists a choice function for the family: a function $f\colon I\to\cup A_i$ such that $f(i)\in A_i$ for each $i\in I$.

(ii) Zorn's Lemma: If $(X,\preceq)$ is a partially ordered set in which every chain has an upper bound, then $X$ has $\preceq$-maximal elements.

(ii) The Well-ordering Principle: Given any set $X$, there exists an ordering $\leq\subseteq X\times X$ that is a well-ordering on $X$; that is, a total order on $X$ such that every nonempty subset of $X$ has a first element under $\leq$.

You can see a nice proof of the equivalence in this handout by George Bergman. (It's in Postscript).

So, assuming the Axiom of Choice, every set can be given a well-ordering.

Ordinals are special sets that generalize the natural numbers. One can prove that given two well-ordered sets $W_1$ and $W_2$, either $W_1$ and $W_2$ are order-isomorphic (there is a bijection between them that respects the order); or $W_1$ is isomorphic to an initial segment of $W_2$ (a subset $I$ such that if $a\in I$ and $b\in W_2$ with $b\leq a$, then $b\in I$); or $W_2$ is isomorphic to an initial segment of $W_1$.

The idea is to define ordinals to be sets where we define an ordering $\alpha\lt\beta$ if and only if $\alpha\in \beta$, and where each ordinal $\alpha$ is given by $\alpha=\{\beta\mid\beta\text{ is an ordinal, and }\beta\in\alpha\}$.

A set $T$ is transitive if $x\in T\Rightarrow x\subseteq T$. We define

Definition. An ordinal is a transitive set that is well-ordered by $\in$.

Under this definition: $0=\emptyset$ is an ordinal; if $\alpha$ is an ordinal and $\beta\in\alpha$, then $\beta$ is an ordinal; if $\alpha$ and $\beta$ are ordinals, and $\alpha\subsetneq \beta$, then $\alpha\in\beta$; and if $\alpha$ and $\beta$ are ordinals, then either $\alpha\subseteq \beta$ or $\beta\subseteq \alpha$. If $\alpha$ is an ordinal, then so is $\alpha^+ = \alpha\cup\{\alpha\}$.

Also, every well-ordered set is order isomorphic to one and only one ordinal.

The finite ordinals are precisely the natural numbers. But there are other ordinals.

An ordinal $\alpha$ such that $\alpha=\beta^+$ for some ordinal $\beta$ is called a "successor ordinal". If $\alpha$ is not a successor ordinal, then $\alpha=\sup\{\beta\mid \beta\lt \alpha\}=\cup\alpha$, and $\alpha$ is called a "limit ordinal."

The finite ordinals correspond to the natural numbers; you can think of them as just finite ordered lists. So, for example, the ordinal $5$ can be thought of as a list with five items, namely the elements $0$, $1$, $2$, $3$ and $4$, in that order: $$5:\qquad \stackrel{0}{\bullet}\quad \stackrel{1}{\bullet}\quad \stackrel{2}{\bullet} \quad \stackrel{3}{\bullet}\quad\stackrel{4}{\bullet}$$ The first infinite ordinal is $\omega$, which corresponds to the set of all natural numbers in their usual order. $$\omega: \qquad \stackrel{0}{\bullet}\quad \stackrel{1}{\bullet}\quad \stackrel{2}{\bullet} \quad \stackrel{3}{\bullet}\quad \cdots \quad\longrightarrow$$ where $\longrightarrow$ is meant to represent that it keeps going.

The next ordinal after $\omega$ is $\omega^+$; it is like having the natural numbers, and then another item which is strictly larger than every natural number: $$\omega+1: \qquad \stackrel{0}{\bullet}\quad \stackrel{1}{\bullet}\quad \stackrel{2}{\bullet} \quad \stackrel{3}{\bullet}\quad \cdots \quad\longrightarrow\quad \stackrel{\omega+1}{\bullet}$$

Then $(\omega^+)^+$ (usually written $\omega+2$), which is a copy of the natural numbers, and then two more items larger than all natural numbers: $$\omega+2: \qquad \stackrel{0}{\bullet}\quad \stackrel{1}{\bullet}\quad \stackrel{2}{\bullet} \quad \stackrel{3}{\bullet}\quad \cdots \quad\longrightarrow\quad \stackrel{\omega+1}{\bullet}\quad\stackrel{\omega+2}{\bullet}$$

And so on. Later, you get to $\omega+\omega$, two copies of the natural numbers (say, blue and red natural numbers, with every blue natural number smaller than every red natural number): $$\omega+2: \qquad \stackrel{0}{\bullet}\quad \stackrel{1}{\bullet}\quad \stackrel{2}{\bullet} \quad \stackrel{3}{\bullet}\quad \cdots \quad\longrightarrow\quad \stackrel{\omega+1}{\bullet}\quad\stackrel{\omega+2}{\bullet}\quad\stackrel{\omega+3}{\bullet}\quad\cdots\quad\longrightarrow$$ And so on.

Finally, transfinite induction:

Transfinite Induction. Let $C$ be a class of ordinals, and assume that:

• (i) $0\in C$;
• (ii) If $\alpha\in C$, then $\alpha^+\in C$.
• (iii) If $\alpha$ is a nonzero limit ordinal, and $\beta\in C$ for all $\beta\in \alpha$, then $\alpha\in C$.

Then $C$ is the class of all ordinals.

This generalizes usual induction (which would only use parts (i) and (ii)). The main difference is how to deal with "limit ordinals"; the process is similar to that used in strong induction: assume valid for every ordinal strictly smaller, prove it for the current ordinal.

So now, looking at the proof offered by Robinson. Your group $F$ has a basis $X$, because it is free abelian. Invoking the Well Ordering Principle, we may assume that $X$ is actually well-ordered; since every well-ordered set is isomorphic to an ordinal, we may go so far as to just assume that that the basis is given as a set indexed by an ordinal $\beta$, $X=\{x_{\alpha}\}_{\alpha\in\beta}$.

For each ordinal $\alpha$, let $F_{\alpha}=\langle x_{\gamma}\mid \gamma\lt\alpha\rangle$. So $F_{\alpha}=F$ for any $\alpha\geq\beta$. We are going to prove by transfinite induction that the class of all ordinals $\alpha$ such that

$H_{\alpha} = H\cap F_{\alpha}$ is free abelian of rank at most $\alpha$.

is the class of all ordinals. Since $H_{\beta}=H$, if we can prove that the class is the class of all ordinals, we will have our desired result (that $H$ is free).

So we proceed by transfinite induction. $F_{0}=\{0\}$, and $H\cap F_{0}=\{0\}$ is free on the empty set, so we are done. $0$ has the property.

Assume that $\alpha$ has the property that $H_{\alpha}$ is free abelian, and consider $H_{\alpha+1}$. If $\alpha\geq \beta$, there is nothing to do: $H_{\alpha+1}=H_{\alpha}$, hence it is free abelian, so we may assume that $\alpha\lt\beta$. Then proceeding as Robinson does, we see that $H_{\alpha+1}$ is either equal to $H_{\alpha}$, or is isomorphic to $H_{\alpha}\oplus \mathbb{Z}$, and since $H_{\alpha}$ is free abelian, so is $H_{\alpha}\oplus\mathbb{Z}$, hence $H_{\alpha+1}$ is free abelian. Thus, if $\alpha$ has the property, then so does $\alpha+1$.

Finally, we need to show the result holds if $\alpha$ is a limit ordinal; Robinson is omitting this part (I'm not sure why; maybe he has a different proof in mind). We know that for every $\gamma\lt \alpha$, $H_{\gamma}$ is free. It is not hard to see that $$F_{\alpha} = \bigcup_{\gamma\lt\alpha}F_{\gamma}$$ and so $$H_{\alpha} = H\cap F_{\alpha} = H\cap\left(\bigcup_{\gamma\lt\alpha}F_{\gamma}\right) = \bigcup_{\gamma\lt\alpha}H\cap F_{\gamma} = \bigcup_{\gamma\lt\alpha}H_{\gamma}.$$ And it is, in turn, not hard to verify that this union is free abelian (you need to be careful, but you can pick bases for $H_{\gamma}$ for each $\gamma$, again inductively, in such a way that if $\gamma'\lt\gamma$, then the basis of $H_{\gamma'}$ is a subset of the basis of $H_{\gamma}$; then the union of the bases of the $H_{\gamma}$ is a basis for $H_{\alpha}$); and that the cardinality of this basis is at must the supremum of the cardinals of the bases of the $H_{\gamma}$, which is bounded above by $\alpha$ by the inductive hypothesis.

So the conclusion also holds for limit ordinals, hence holds for all ordinals (since it holds for $0$, for successor ordinals, and for limit ordinals).

-
To define $\alpha = \{\beta\mid\beta\ \text{is an ordinal}\land\beta\in\alpha\}$ is a bit circular, don't you think? – Asaf Karagila Nov 11 '11 at 20:07
@Asaf: Yes, which is why that is not the definition (the definition comes later), just the intuition of "what we want". The definition is that ordinal is a transitive set that is well-ordered by $\in$ (two lines later). – Arturo Magidin Nov 11 '11 at 20:12
@Arturo Magidin: Thank you really very much for this detailed answer. I have learned a lot, although it is still a little strange for me thinking of an uncountable set as to be isomorphic to an ordinal, which is a generazation of natural numbers (countable). I thought sets of different cardinality were VERY DIFFERENT. – ShinyaSakai Nov 13 '11 at 12:29
@ShinyaSakai: What you need to realize is that "well-ordered" does not mean "ordered like the naturals". Uncountable ordinals are very different from countable ordinals. – Arturo Magidin Nov 13 '11 at 21:58
@Arturo Magidin: Thank you for explaining. I begin to understand. – ShinyaSakai Nov 14 '11 at 11:26

The axiom of choice is equivalent to the statement that every set can be well ordered. That is, every set can be given a transitive and irreflexive ordering which is linear, and every nonempty subset has a minimal element.

This does not mean that we can only well order countable sets. Similarly we can define an induction on ordinals, and not only on the natural numbers.

In transfinite induction, as the name suggests, we go beyond finite numbers and so we need to deal with limit cases as well. It might sound complicated, but usually it is not.

-
Can you expand a bit on how choiceless pathologies regarding subgroups of free groups are relevant to this question? – user83827 Nov 11 '11 at 13:35
So you are not claiming that AC is necessary for the proposition asked about in the title (about subgroups of free abelian groups)? – user83827 Nov 11 '11 at 14:19
@Asaf: Are the pathologies for free abelian groups, or for (absolutely) free groups? – Arturo Magidin Nov 11 '11 at 14:35
@Arturo: After I thought about it some more, I have decided to post a question on MathOverflow. – Asaf Karagila Nov 12 '11 at 21:36
@Arturo: As you have suspected, it is possible to have a space with a basis which has a subspace without a basis. I'll see if I can use the spaces goldstern found to construct a free abelian group with a subgroup which is not free. – Asaf Karagila Nov 14 '11 at 7:02

FYI, here's an alternate approach, assuming that $X$ is infinite (if $X$ is finite, then you can use basic linear algebra arguments to show that any basis of $H$ must have at most $\vert X \vert$ elements).

Since $F$ is free abelian on $X$, we have $F \cong \bigoplus\limits_{x\in X}\mathbb{Z}$. Assuming the axiom of choice--which gives us the fact that $\vert A \vert = \vert A \times A \vert$ for any infinite set $A$--it's not too tough to show that $\vert X \vert = \vert F \vert$.

Now, clearly $Y\subseteq F$ since $H\subseteq F$. However, this implies that $\vert Y \vert \leq \vert F \vert = \vert X \vert$, and hence $\vert Y \vert \leq \vert X \vert$.

-
Thank you very much for the answer. I am sorry I don't know how to prove $|X|=|F|$. Is this because $|F|$ is a finite multiplication of $|X|$? Would you please tell me the reason? I think this proof is very good after the freeness of $H$, which is an arbitrary subgroup of $G$, has been shown. – ShinyaSakai Nov 13 '11 at 12:36

These tools allow you to set up inductive arguments on any set not just those which are countable.

-
Thanks very much for the answer. Now I know what is going on in the proof. – ShinyaSakai Nov 13 '11 at 12:30