Intereting Posts

Maximum of $\sin A\sin B\cos C+\sin B\sin C\cos A+\sin C\sin A\cos B$ in triangle
Divisibility of multinomial by a prime number
generalized inverse of a matrix and convergence for singular matrix
Is the ring of germs of $C^\infty$ functions at $0$ Noetherian?
Book Reference for Calculus and Linear Algebra :: Engineer
Showing that a topological space is ${\rm T}_1$
Different definitions of handle attachment
Proof of Cartesian product intersection
Prove functions defined by sup and inf are continuous
Support of a module with extended scalars
The limit of $\sin(1/x)$ as $x\to 0$ does not exists
Closed form for an infinite sum over Gamma functions?
Testing Zeros Of The Riemann Hypothesis
Fractional part of $b \log a$
“Canceling Out The Zeroes” In A Mathematically Sane Way $\frac{0\times x}{0\times 1}$

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:

- The free abelian group monad
- Subgroups of finite abelian groups.
- Does every ring with unity arise as an endomorphism ring?
- Is there a homomorphism from a full product of finite cyclic groups onto $\mathbb Z$?
- $G$ a group s.t. every non-identity element has order 2. If $G$ is finite, prove $|G| = 2^n$ and $G \simeq C_2 \times C_2 \times\cdots\times C_2$
- Prove that $\mathbb Z^n$ is not isomorphic to $\mathbb Z^m$ for $m\neq n$

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]

- Axiom of choice, non-measurable sets, countable unions
- Showing that a cyclic automorphism group makes a finite group abelian
- Give an example of a nonabelian group in which a product of elements of finite order can have infinite order.
- Finding an explicit isomorphism from $\mathbb{Z}^{4}/H$ to $\mathbb{Z} \oplus \mathbb{Z}/18\mathbb{Z}$
- A non-abelian group such that $G/z(G)$ is abelian.
- Status of the classification of non-finitely generated abelian groups.
- $X$ is a basis for free abelian group $A_{n}$ if and only if $\det (M) = \pm 1$
- Compact but not sequentially compact question
- Strange consequences of Axiom of Choice in Zermelo set theory
- If $f\in\hbox{Hom}_{\mathbb{Z}}(\prod_{i=1}^{\infty }\mathbb{Z},\mathbb{Z})$ and $f\mid_{\bigoplus_{i=1}^{\infty } \mathbb{Z}}=0$ then $f=0$.

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.

- If $h$ divides $|G|$, not necessary that $G$ has a subgroup of order $h$
- What are $10^k \pmod 3$ and $n = \overline{a_ka_{k -1} \ldots a_1a_0}$?
- Finding $d=\gcd(a,b)$; finding integers $m$ and $n$: $d=ma+nb$
- Are these two statements equivalent?
- Ramanujan theta function and its continued fraction
- Find the recurrence relation for the number of bit strings that contain the string $01$.
- Why does the amoeba shrink to its skeleton when we go to infinity?
- Jordan Canonical form of $T(f(x))=f'''(x)+2f(x)$
- Proving rigorously the supremum of a set
- Find the volume of the largest right circular cone that can be inscribed in a sphere of radius r?
- How I can calculate $\sum_{n=0}^\infty{\frac{n}{3^n}}$?
- If the dot product between two vectors is $0$, are the two linearly independent?
- Trace of a real, symmetric positive semi-definite matrix
- What is the best way to define the diameter of the empty subset of a metric space?
- how many zeroes does 2012! have at the end?