Equivalent statements of the Axiom of Choice

As a little project for myself this winter break, I'm trying to go through as much of Enderton's Elements of Set Theory as I can. I hit a snag trying to show two forms of the Axiom of Choice are equivalent. This is exercise 31 on page 55.

The first form is:

For any relation $R$ there is a function $G\subseteq R$ with $\text{dom}\ G=\text{dom}\ R$.

and the second form is:

For any set $I$ and any function $H$ with domain $I$, if $H(i)\neq\emptyset$ for all $i\in I$, then $\times_{i\in I}H(i)\neq\emptyset$.

Here is what I have so far:

Assume the first form. Take any set $I$ and let $H$ be a function with domain $I$ such that $H(i)\neq\emptyset$ for all $i\in I$. This function $H$ is a relation, so by the Axiom of Choice, there exists a function $G\subseteq H$ such that $\text{dom}\ G=\text{dom}\ H=I$. Since $\text{dom}\ G=I$, for each $i\in I$, there exists some $G(i)$ such that $(i,G(i))\in G$. But since $G\subseteq H$, $(i,G(i))=(j,H(j))$ for some $j\in I$. Since these are ordered pairs, $i=j$ and $G(i)=H(j)$? I suppose I want to be able to show that for all $i\in I$, I can have $G$ "choose" some element $G(i)\in H(i)$, and thus $G\in\times_{i\in I}H(i)$, showing that $\times_{i\in I}H(i)\neq\emptyset$, but I don't see how the first form allows one to do that. Instead, all I see is that $G(i)=H(i)$.

Conversely, I assume the second form. I take any relation $R$, and denote $\text{dom}\ R=I$. Let $H$ be any function with domain $I$. Now if $H(i)\neq\emptyset$ for all $i$, then $\times_{i\in I}H(i)\neq\emptyset$, so then I could take some $f\in\times_{i\in I}H(i)$, so by definition, $\text{dom} f=I$, and for all $i$, $f(i)\in H(i)$. If it is the case that $(i,H(i))\in R$, then $f\subseteq R$, and the first form would be proven. Again, I suppose I want $H$ to be a function that, for each $i\in I$, $H$ takes the value of exactly one $y_i$ such that $iRy_i$, but again, I don't see how the assumed axiom allows one to do this.

Can anyone explain how to get around these two issues? Thank you.

Solution 1:

The key in these kinds of proofs is to find a particular instance of the proposition you are assuming that will yield the one you want. So in order to prove the second form from the first, you start with $I$ and $H$, and want to "cook up" some $R$ for which the $G$ will yield what you want. And conversely.

You are sort of on the right track, but the problem is that you are trying to apply each form to the information from the other, instead of cooking up an appropriate set to apply the "other" form in each case. For instance, in your second proof, you shouldn't take $H$ to be any function, you want to cook up a particular function.

Now, before we actually prove they are equivalent, let's think about them. Intuitively, why should these two "be" the Axiom of Choice? In a relation, every element in the domain is associated to many elements in the codomain. Being able to find a function "contained" in the relation is like, for each $x$ in the domain, picking one element from each of the things that are associated to $x$ to be the image of $x$. This is the Axiom of Choice (you are picking one element from each collection of "things related to $i$" for $i\in I$). As for the second, an element of $\mathop{\times}\limits_{i\in I}H(i)$ is a function from $I$ to $\cup H(i)$ such that the image of $i$ is in $H(i)$ for each $i$; again, a choice of elements from a family of sets, again Choice. Knowing how each of them relates to AC, and hence to each other, should help you figure out how to show the equivalence: after all, that equivalence should be one in which the particular "choice" that one form allows you to make is exactly the "choice" that the other form requires you to make.

For more explicit hints:

In your attempt to show the first form implies the second, you are focusing on the wrong thing; you don't want to look at $H$ as a relation, because then you will have $G=H$ ($H$ is already a function). Instead, define a relation $R\subseteq I\times \cup H(i)$ by $(i,x)$ if and only if $x\in H(i)$. (That is, $H(i)$ is a nonempty set for each $i$; associate with each $i$ all elements in $H(i)$). Now use the first form with $R$, not with $H$, because the $G$ should give you an element of the product (think of them as described above).

For the second, assume that $R$ is a relation, and you want to define a function contained in $R$ with the same domain. Let $I$ be the domain of $R$, and for each $i\in I$, let $H(i) = \{ x\in\mathrm{codom}(R)\mid iRx\}$. Use the fact that the product is nonempty to pick an element in the product (which "picks" an element from each of the sets of "things related to $i$") and use that to define the function $G$.

Solution 2:

Assume the first form. Let $I$ be any set and let $H$ be any function such that $\text{dom}\ H=I$, and $H(i)\neq\emptyset$ for all $i\in I$. Define a relation $R\subseteq I\times\bigcup_{i\in I}H(i)$ by $$ \langle i,x\rangle\in R\Leftrightarrow x\in H(i). $$ By assumption, there exists a function $G\subseteq R$ with $\text{dom}\ G=\text{dom}\ R=I$, as for each $i\in I$, $i\in\text{dom}\ R$ since $H(i)$ is nonempty. So for all $\langle i,G(i)\rangle\in G$, $\langle i,G(i)\rangle\in R$, and thus by the definition of $R$, $G(i)\in H(i)$. It follows that $G\in\prod_{i\in I}H(i)$, so $\prod_{i\in I}H(i)\neq\emptyset$. Thus the second form follows from the first.

Conversely, let $R$ be any relation, and denote $\text{dom}\ R=I$. Define a function $$ H\colon I\to\mathscr{P}(\text{ran}\ R)\colon i\mapsto H(i):=\{x\in\text{ran}\ R\ |\ iRx\}. $$ In particular, $H$ is a function with domain $I$, and $H(i)\neq\emptyset$ for all $i\in I$. So by the second form, $\prod_{i\in I}H(i)\neq\emptyset$, so take $G\in\prod_{i\in I}H(i)$. Hence $\text{dom}\ G=I$, and for all $i\in I$, $G(i)\in H(i)$. Also, for any $\langle i,G(i)\rangle\in G$, $G(i)\in H(i)\subseteq\text{ran}\ R$, and so $\langle i,G(i)\rangle\in R$, so $G\subseteq R$. Hence the two statements of the Axiom of Choice are equivalent.