- SET THEORY 549
set A, one could conceive of another set whose members were the subsets of A. This
set is nowadays denoted 2 A and called the power set of A. If A has a finite number
ç of elements, then 2 A has 2" elements, counting the improper subsets 0 and A.
It was not long, however, before the indiscriminate use of this freedom to form
sets led to paradoxes. The most famous of these is Russell's paradox, discussed in
the next section. The source of the difficulty is that "existence" has a specialized
mathematical meaning. The abstraction that comes with set theory has the conse-
quence that much of the action in a proof takes place "offstage." That is, certain
objects needed in a proof are called into existence by saying, "Let there be...,"
but no procedure for constructing them is given. Proofs relying on the abstract
existence of such objects, when it is not possible to choose a particular object and
examine it, became more and more common in the twentieth century. Indeed, much
of measure theory, topology, and functional analysis would be impossible without
such proofs. The principle behind these proofs later came to be known as Zermelo's
axiom, after Ernst Zermelo (1871-1953), who first formulated it in 1904 to prove
that every set could be well ordered. 10 It was also known as the principle of free
choice (in German, Auswahlprinzip) or, more commonly in English, the axiom of
choice. In its broadest form this axiom states that there exists a function f defined
on the class of all nonempty sets such that f(A) e A for every nonempty set. In-
tuitively, if A is nonempty, there exist elements of A, and f(A) chooses one such
element from every nonempty set.
This axiom is used in very many proofs, but probably the earliest (see Moore,
1982, p. 9) is Cantor's proof that a countable union of countable sets is countable.
The proof goes as follows. Assume that A\, i4 2 ,...are countable sets, and let
A — A\ U i4 2 U • • •. Then A is countable. For, let the sets Aj be enumerated, as
followsA\ = an, an, • • • é
A 2 = 02i, a 22 , · · · 1An = a„i, a„2, ... ,Then the elements of A can be enumerated as follows: áð, aj 2 , a 2 i, 013, a 22 ,031,...,
where the elements whose ranks are larger than the triangular number T„ = n(n +
l)/2 but not larger than Tn+\ = (n+ l)(n + 2)/2 are those for which the sum of
the subscripts is ç + 2. There are ç + 1 such elements and ç + 1 such ranks. It is
a very subtle point to notice that this proof assumes more than the mere existence
of an enumeration of each of the sets, which is given in the hypothesis. It assumes
the simultaneous existence of infinitely many enumerations, one for each set. The
reasoning appears to be so natural that one would hardly question it. If a real
choice exists at each stage of the proof, why can we not assume that infinitely
many such choices have been made? As Moore notes, without the axiom of choice,10 A set is well ordered if any two elements can be compared and every nonempty subset has a
smallest element. The positive integers are well ordered by the usual ordering. The positive real
numbers are not.