In his book, Naive Set Theory, Paul R. Halmos leaves it as an exercise to show how a surjective relation implicitly defines a function using the axiom of choice. I am completely new to the axiom, and find it quite the peculiar. Perhaps, I might have misunderstood it completely (please tell me if I have), but the way I attempted at it is as follows:
if $R$ be a relation between non-empty sets $X$ and $Y$, then it is true that each value of $R$ in $Y$ has a preimage in $X$. We can then form a collection $C$ that consists of all preimages of $R$. Namely, if $a,b,c,d ...$ be elements of $Y$, then $C$ = $\{R\{a\}^{-1}, R\{b\}^{-1}, R\{c\}^{-1}, R\{d\}^{-1} ...\}$. Hence, the cartesian product of $C$ will consist of functions with the range consisting of elements in $X$. So if we choose the range of any of these functions, we can call this the domain of our function $f$ and map each element of $f$ to the element in $Y$ whose preimage it was a part of. Would this be correct? I only seek affirmation and, perhaps, guidance from those more professional. Thank you in advance.
Yes, the idea is that.
Observe it is simpler to confine yourself to total relations, that is relations in which every element of the domain has assigned at least one element of the codomain. Why that? Functions are total relations.
In general, for every function $f : X \to Y$ you can consider the family of the fibers of $f$, that is the sets $$f^{-1}(y) := \{x \in X \mid f(x) = y\} .$$ These sets are pairwise disjoint and cover $X$. However, in general some fibers may be empty. If $f$ is a surjection, the fibers do form a partition of $X$.
Now what? This:
Applying the axiom of choice to the family $\{f^{-1}(y) \mid y \in Y\}$, there is a choice function $g : Y \to X$, that is $g(y) \in f^{-1}(y)$ for every $y \in Y$.