Section 9: Problem 1 Solution »

Section 9: Infinite Sets and the Axiom of Choice

Infinite sets and the Axiom of Choice

is infinite iff there is an injective function iff there is a bijection of with its proper subset.
  • When we prove the first implication,
...we assume that is infinite and construct "by induction" an injective function . First,.. we can choose point of ; define to be point so chosen. Then, assuming that we have defined , we wish to define . The set is not empty; for if it were empty,.. would be finite. Hence, we can choose an element of the set and define to be this element. "Using the induction principle", we have defined for all ... Let us try to reformulate this "induction" proof more carefully, so as to make explicit our use of the principle of recursive definition. Given the infinite set , we attempt to define recursively by the formula , an arbitrary element of for . But this is not an acceptable recursion formula at all! For it does not define uniquely in terms of ... What we are saying is that the proof we have given... is not actually a proof. Indeed, on the basis of the properties of set theory we have discussed up to now, it is not possible to prove this theorem. Something more is needed.
The rules for specifying sets:
  1. Were before: listing elements of a set; taking a subset by giving a property that the elements of the subset are to satisfy; taking unions, intersections and differences; taking cartesian products; the set of all subsets (the power set).
  2. The Axiom of Choice: Given a collection of disjoint nonempty sets, there exists a set consisting of exactly one element from each set in the collection.
The axiom of choice becomes important when one needs to prove the existence of a set with an arbitrary chosen elements from an infinite collection of other sets. For example,
  1. The union of a countable collection of countable sets is countable. This is Theorem 7.5 proved in Section 7 that Munkres mentions on page 61 as the one that was proved by implicitly using the axiom of choice. To prove the theorem one starts with the definition of a countable set, which is equivalent to the existence of a surjective function from the positive integers onto the set. Since there are many possible functions to choose from, one needs the axiom of choice to choose one such function for each set in the collection. In fact, one needs a weaker form of the axiom, the axiom of countable choice.
  2. If is surjective then it has a right inverse. To construct a right inverse of a surjective function , for every one needs to choose some , but the existence of this arbitrary choice depends on the axiom of choice. (Note, that to show that if is injective then it has a left inverse, we do not need the axiom of choice, as in this case we map every to the only element of .)
  3. The product of an arbitrary collection of sets. (Compare to Exercise 3(c) of §5.) If for a collection of sets , we define the product  as the set of all functions such that for every : , then the statement “for any collection of nonempty sets their product is nonempty” is just equivalent to the axiom of choice.
It turns out that in many cases the existence (or non-existence) of such a set cannot be derived based on the other axioms. Therefore, one assumes that the axiom (or its weaker form) holds, and takes the existence of the set needed for the proof as granted. In other words, one just believes that the required set ensured by the axiom of choice does exist.

Cardinality

has greater cardinality than if there is an injection from into , but there is no injection from into .
  • The relation is transitive, and nonreflexive. Moreover, according to Schroeder-Bernstein theorem, Section 7, if there are injections and , then and have the same cardinality. Therefore, it remains to show that for every and , there is an injection or an injection , which will be done in Section 10.
  • An uncountable set has greater cardinality than .
  • has the same cardinality as , which greater than the cardinality of .
    • The continuum hypothesis states that there is no set having cardinality between the cardinalities of and .
  • For every , has greater cardinality than .
    • The generalized continuum hypothesis states that for every there is no set having cardinality between the cardinalities of and .