Section 9: Infinite Sets and the Axiom of Choice

Infinite sets and the Axiom of Choice

• When we prove the first implication,

...we assume that $A$ is infinite and construct "by induction" an injective function $f:\mathbb{Z}_{+}\rightarrow A$ . First,.. we can choose point $a_{1}$ of $A$ ; define $f(1)$ to be point so chosen. Then, assuming that we have defined $f(1),...,f(n-1)$ , we wish to define $f(n)$ . The set $A-f(\{1,...,n-1\})$ is not empty; for if it were empty,.. $A$ would be finite. Hence, we can choose an element of the set $A-f(\{1,...,n-1\})$ and define $f(n)$ to be this element. "Using the induction principle", we have defined $f$ for all $n\in\mathbb{Z}_{+}$ ... 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 $A$ , we attempt to define $f:\mathbb{Z}_{+}\rightarrow A$ recursively by the formula $f(1)=a_{1}$ , $f(i)=$ an arbitrary element of $[A-f(\{1,...,i-1\})]$ for $i>1$ . But this is not an acceptable recursion formula at all! For it does not define $f(i)$ uniquely in terms of $f|\{1,...,i-1\}$ ... 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.

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.

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 $f$ is surjective then it has a right inverse. To construct a right inverse of a surjective function $f:A\rightarrow B$ , for every $y\in B$ one needs to choose some $x\in f^{-1}(y)$ , but the existence of this arbitrary choice depends on the axiom of choice. (Note, that to show that if $f$ is injective then it has a left inverse, we do not need the axiom of choice, as in this case we map every $y\in f(A)$ to the only element of $f^{-1}(y)$ .)
3. The product of an arbitrary collection of sets. (Compare to Exercise 3(c) of §5.) If for a collection of sets $\{A_{\alpha}\}_{\alpha\in J}$ , we define the product $\sqcap_{\alpha\in J}A_{\alpha}$  as the set of all functions $\mathbf{x}:J\rightarrow\cup_{\alpha\in J}A_{\alpha}$ such that for every $\alpha\in J$ : $\mathbf{x}(\alpha)\in A_{\alpha}$ , then the statement “for any collection of nonempty sets their product is nonempty” is just equivalent to the axiom of choice.

Cardinality

• The relation is transitive, and nonreflexive. Moreover, according to Schroeder-Bernstein theorem, Section 7, if there are injections $A\rightarrow B$ and $B\rightarrow A$ , then $A$ and $B$ have the same cardinality. Therefore, it remains to show that for every $A$ and $B$ , there is an injection $A\rightarrow B$ or an injection $B\rightarrow A$ , which will be done in Section 10.
• An uncountable set has greater cardinality than $\mathbb{Z}_{+}$ .
• $\mathcal{P}(\mathbb{Z}_{+})$ has the same cardinality as $\mathbb{R}$ , which greater than the cardinality of $\mathbb{Z}_{+}$ .
  • The continuum hypothesis states that there is no set having cardinality between the cardinalities of $\mathbb{Z}_{+}$ and $\mathbb{R}$ .
• For every $A$ , $\mathcal{P}(A)$ has greater cardinality than $A$ .
  • The generalized continuum hypothesis states that for every $A$ there is no set having cardinality between the cardinalities of $A$ and $\mathcal{P}(A)$ .