I am working on an assignment that requires proving the equivalence of two versions of the axiom of choice.

(1st form): For any relation $R$, there is a function $H \subseteq R$ with dom $H =$ dom $R$.

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

To clarify, $\prod_{i \in I} H(i) = \{f | f\text{ is a function with domain }I \ \& \ (\forall i \in I) f(i) \in H(i)\}$.

$I$ is supposed to be like an Index Set.

Here is what I have so far.


(1st form) $\implies$ (2nd form):

(1) We assume the 1st form and that $h(i) \neq \emptyset$ for all $i \in I$.

(2) Considering $\prod_{i \in I} H(i)$, this itself is a relation since it is a set of ordered pairs (i.e. - function are sets of ordered pairs $<x,y>$ where whenever $<x,y>$ and $<x,y'>$ then $y = y'$).

(3) By the 1st form, there is a function $H \subseteq X_{i \in I} H(i)$ with $\operatorname{dom}H =\operatorname{dom}\prod_{i \in I} H(i)$.

(4) Then, since dom $h =\operatorname{dom}\prod_{i \in I} H(i) =\operatorname{dom}I$, and $H(i) \neq \emptyset$ for all $i \in I$, we have $H$ itself as a member of $\prod_{i \in I} H(i)$.

(5) So $\prod_{i \in I} H(i) \neq \emptyset$.

I am still working on the other direction but any help or hints anyone can provide would be greatly appreciated.

Thank you in advance.



If $R\subseteq I\times B$ is a relation whose domain is $I$, for each $i\in I$ let $H(i)=\{b\in B\mid \langle i,b\rangle\in R\}$. Then $H(i)$ is non-empty. What sort of elements live in the product $\prod_{i\in I}H(i)$?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.