Theorem 1   A relation $R$ is the union of a set of functions each of which has the same domain as $R$ if and only if for each set $A$ of nonempty sets, there is a choice function on $A$ .

Proof. Suppose that $R$ is a relation with $\dom(R) = A \mbox{ and } \rng(R) \subseteq B$ . Let $g \colon A \to \mathcal{P}(B)$ be given by $a \mapsto R\left[\{a\}\right]$ . There is be a choice function $c$ on $g\left[A\right]$ . Let $f = c \circ g$ , and for each pair $\langle a,b\rangle \in R$ , let $f_{ab}$ send $a$ to $b$ and agree with $f$ elsewhere. Let $F = \{f_{ab}\mid \langle a,b \rangle \in R\}$ . Clearly $\bigcup F \subseteq A \times B$ , so suppose $\langle u,v \rangle \in \bigcup F$ ; then there is a pair $\langle a,b\rangle \in R$ such that $\langle u,v \rangle \in f_{ab} \in F$ . Either $\langle u,v \rangle = \langle a,b\rangle$ , or $v = f(u) = c \circ g(u) = c(R\left[\{u\}\right]) \in R\left[\{u\}\right]$ . In each case, $\langle u,v \rangle \in R$ . Thus, $\bigcup F \subseteq R.$ For each pair $\langle a,b\rangle \in R$ , $\langle a,b\rangle \in f_{ab} \in F$ , so $R \subseteq \bigcup F$ . Therefore, $R = \bigcup F$ .
Suppose that $A$ is set of nonempty sets. Let $R = \bigcup \{\{a\} \times a \mid a \in A \}$ . A set $x$ is an element of $ \dom(R)$ if and only if $x \in \{a\}$ for some $a \in A$ . Thus, $\dom(R) = A$ . There is a set $F$ of functions, each of which has domain $A$ , such that $R = \bigcup F$ . Let $f \in F$ ; then $\dom(f) = A$ , and for each pair $\langle a,f(a)\rangle \in f$ , $\langle a,f(a)\rangle \in \{a\} \times a$ ; i.e., $f(a) \in a$ . Each such $f$ is, thus, a choice function on $A$ .