VI I : The Axiom of Choice and related propertiesNear the end of Section V I.4 we listed several basic questions about transfinite cardinalnumbers, and we shall restate them here for the sake of convenience: 1. Is the partial ordering of cardinal numbers a linear ordering?2. Is 0 the smallest transfinite cardinal number?3. If A is an infinite set, does it follow that the idempotent identities |A|  |A| = |A| and |A| + |A| = |A| always hold?4. If there is a surjection from A to B, does it follow that |B|  |A| ? 5. Given a cardinal number , is there a unique minimal cardinal number such that >?One purpose of this section is to discuss the issues that arise when one studies such questions, and the overall answer may be summarized as follows:If certain valid constructions and operations for subsets of the natural numbers N can be extended to arbitrary sets, then the answers to thequestions stated above (and several others) are all affirmative. The good news in this statement is that it generates optimism about finding positive answers to the sorts of questions we have described. However, there is also some bad news. The “valid constructions and operations” for subsets of N can be described very explicitly, but for arbitrary sets the best we can expect are nonconstructive existence principles. This is particularly well illustrated by the following attempt to prove the answer to the fourth question is yes:Suppose that f is a surjection from A to B. Then for each b  B we know that the inverse image is f – 1[ {b} ] is nonempty. For each b pick some element g(b)  A in this inverse image. Since g(b) lies in f – 1[ {b} ] it follows that f( g(b) ) = b for all b and hence the composite f g is the identity on B. But now g must be 1 – 1 by one of the exercises for Section IV.3, and therefore we have |B|  |A| .There are two important points to notice about this:1. The ideal of picking an element out of the set has a great deal of intuitive appeal.2. On the other hand, there is no information on exactly how one should pick an element from the given nonempty subset. — In contrast, if we are dealing with subsets of N then there is a simple explicit method for making such choices; one simply takes the first element of a given nonempty subset.Taken together, these suggest that we may need to assume it is possible to pick out “possibly random” elements from nonempty subsets in some unspecified manner. During the first few decades of the 20th century mathematicians studied this question extensively. The first phase of this work produced several logically equivalent versions of the crucial assumption described above, the second sows that such the logical 149consistence of set theory is not compromised if one makes such assumptions, and the third shows that one has acceptable models for set theory in which such assumptions are true and equally acceptable models in which they are false. Since affirmative answers to the given questions (and others) are convenient for many purposes, most mathematicians are willing to make the sorts of assumptions need to justify the informal argument given above, sometimes reluctantly but generally with few reservations.We shall begin by motivating and stating three standard ways of formulating the nonconstructive existence principle that arises in connection with the questions above. This is done in Sections 1 and 2, with equivalence proofs in Section 3; a reader who prefers to skip the details of the latter may do so without loss of continuity. Section 4 contains answers to those questions in the list which are not answered in Section 2. Thefinal two sections are commentaries on two related issues. We have noted that assuming the nonconstructive existence principles does not compromise the logical soundness of set theory, and Section 5 explains the situation in a little more detail, and italso discusses the “acceptable models” mentioned above. Finally, Section 6 deals witha question dealing with Cantor’s original work: All the specific infinite subsets of the real numbers that arose in his studies either had the same cardinal number as the integers orthe real numbers, and Cantor’s Continuum Hypothesis states that there are no cardinal numbers  such that |N| <  < |R|. It turns out that the formal status of this assumption (and an associated Generalized Continuum Hypothesis) is completely analogous to the nonconstructive existence hypothesis discussed in previoussections.V I I .1 : Nonconstructive existence principles(Halmos, §§ 15 – 17; Lipschutz, §§ 5.9, 9.1 – 9.4)We have repeatedly noted that the initial and most important motivation for set theory came from questions about infinite sets. As research on such sets progressed during the late nineteenth and early twentieth century, it eventually became evident that most ofthe underlying principles involved constructing new sets from old ones and the existenceof the set of natural numbers. However, it also became clear that some results in set theory depended upon some nonconstructive existence principles. In particular, when mathematicians attempted to answer questions like 1 – 5 at the beginning of this unit, their arguments used ideas that seemed fairly reasonable but could not be carried out explicitly. In the introduction to this unit, we discussed the role of nonconstructive existence principles in analyzing Question 4. Here we shall begin with a similar analysis of Question 2 from the list. We would like to prove the following result.Theorem 1. If A is an infinite set, then A has a countably infinite subset and hence we have 0  |A| .It will follow from Theorem 1 that 0 is the unique smallest infinite cardinal number.150In Section V.2 we proved a related fact; namely, if A is countably infinite and B is an infinite subset of A, then |B| = 0 . One important step in the proof relied on the existence of a well – ordering on the standard countably infinite set N; using the 1 – 1 correspondence between N and A, it follows that A also has a well – ordering if it is countably infinite.The preceding discussion suggests that if an infinite set A has a well – ordering, thenperhaps one can generalize the previous argument for countably infinite sets A to cover other infinite sets as well. The idea that every set has a well – ordering originally appeared in Cantor’s