$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]

Solutions Collecting From Web of "$F$ is a free abelian group on a set $X$ , $H \subseteq F$ is a free abelian group on $Y$, then $|Y| \leq |X|$"

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).

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.

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$.

Well-ordering principle + Transfinite Induction

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