\documentclass[12pt]{exam}
\input{defs}
\begin{document}

                              


\centerline {\underbar {\bf THE WELL-ORDERING PRINCIPLE AND THE AXIOM OF CHOICE}}
 \noi                            
    At the beginning of the twentieth century, Cantor's set theory was mired in paradox (e.g. Russell's paradox). There were various attempts to construct an axiomatic
set theory devoid of these paradoxes. One of the more successful of these programs was the Zermelo-
Fraenkel (or ZF) axioms of set theory. This theory (and others similar to it) is the foundation of
modern mathematics.
\noi
    Now, we have seen that although the real numbers with the standard "less than or equal to"
ordering is a totally  ordered set, this does not define a well-order, for even the interval
(0,1) has no least member. Cantor had conjectured that every set can be well-ordered. This is what
is known as the Well-Ordering Principle (or WOP), and in 1904 it was proven by Zermelo. His proof
was purely an "existence proof", however, and did not give any information about how to construct
such a well-order on an arbitrary set. Indeed, there is still no known well-order on the real numbers,
although Zermelo, if we are to believe him, insists that one exists. Should we believe him?
\noi
    The catch here is that Zermelo explicitly assumed, in his proof, the validity of what is now known
as the Axiom of Choice (or AC). Indeed, Cantor had implicitly assumed such an axiom in
developing his "Naive Set Theory". Since Cantor's work had led to paradoxes, a controversy arose
over the validity of AC. The proponents of AC set out to show that it could actually be proven, as
a theorem, in the ZF system. We will return to this
story shortly, but first we examine the AC and its relationship to the WOP in more detail.
\noi
AXIOM OF CHOICE: Let $\{ A_{\alpha} : \alpha \in \Lambda \}$ be a non-empty collection of
non-empty sets. Then there exists a function $f:\Lambda \rightarrow \cup_{\alpha \in \Lambda}
A_{\alpha}$ such that for each $\alpha \in \Lambda$, $f(\alpha ) \in A_{\alpha}$.
\noi
So the AC is merely a claim that one can "choose", from each set, an element in that set. Such a
choice is realized by the existence of the choice function $f$. At first glance, the AC may seem quite
harmless. Indeed, in the case that the indexing set $\Lambda$ is finite, such a choice function can
be shown to always exist merely by assuming the validity of mathematical induction (or its
equivalent axiom, that the natural numbers are well-ordered). So why the controversy? Well, Cantor
assumed that many of the properties of finite sets should hold for infinite sets, and this is where the
paradoxes arose. Hence the critics merely thought the AC would lead to more paradoxes. 
\noi
Russell pointed out the subtleties of the AC with the following example: "In an infinite collection
of pairs of shoes, the AC is not needed to establish the existence of a set containing exactly one
element from each of the pairs, for a rule can be given to select the left shoes, for example. But in
the case of an infinite collection of pairs of identical socks, no such rule is available; appeal must
be made to the AC if the assertion is made that there exists a set containing exactly one sock from
each pair."
\noi
Now, Zermelo had shown that the AC implies the WOP. Moreover, Borel showed that the two were
in fact equivalent. So the fate of the WOP was now directly tied to the fate of the AC. But the
question still remained: Are these provable (or not provable) within the ZF axiom system?
\noi
Little progress was made until 1940, when Godel proved that the AC is consistent with the ZF
system. That is, assuming the validity of the AC would not lead to contradictions (withing the ZF
system) which otherwise would not have arisen. In particular, this means that the AC cannot be
disproved within the ZF system, for if so, then the AC and it's negation could both be shown to be
true, and this is contradictory. The proponents held out hope.
\noi
It wasn't until 1964 that the question was finally resolved, although it's resolution left some not
completely satisfied. It was at this time that Cohen proved that the negation of the AC was in fact
also consistent within the ZF axiom system. Hence the AC could not be proved. The AC was thus
relegated to the status of conjectures which can neither be proved nor disproved within the ZF axiom
system.
\noi
However, as Smullyan has pointed out, this does not necessarily mean that the validity of the AC
(and hence of the WOP) is an undecidable question. It merely means that our present (ZF) axioms 
of set theory are insufficient to decide the question.  So it goes.


\end{document}