proof that a relation is union of functions if and only if AC

Theorem.

Proof.

Suppose that R is a relation with dom⁡(R)=A⁢ and ⁢rng⁡(R)⊆B. Let g:A→𝒫⁢(B) be given
by a↦R⁢[{a}]. There is be a choice function
c on g⁢[A]. Let f=c∘g, and for each pair
⟨a,b⟩∈R, let fa⁢b send a to b and agree
with f elsewhere. Let F={fa⁢b∣⟨a,b⟩∈R}. Clearly ⋃F⊆A×B, so suppose
⟨u,v⟩∈⋃F; then there is a pair ⟨a,b⟩∈R such that ⟨u,v⟩∈fa⁢b∈F. Either ⟨u,v⟩=⟨a,b⟩, or v=f⁢(u)=c∘g⁢(u)=c⁢(R⁢[{u}])∈R⁢[{u}]. In each case, ⟨u,v⟩∈R.
Thus, ⋃F⊆R. For each pair ⟨a,b⟩∈R, ⟨a,b⟩∈fa⁢b∈F, so R⊆⋃F. Therefore, R=⋃F.
Suppose that A is set of nonempty sets. Let R=⋃{{a}×a∣a∈A}. A set x is an element ofdom⁡(R) if and only if x∈{a} for some a∈A. Thus,
dom⁡(R)=A. There is a set F of functions, each of which has
domain A, such that R=⋃F. Let f∈F; then
dom⁡(f)=A, and for each pair ⟨a,f⁢(a)⟩∈f,
⟨a,f⁢(a)⟩∈{a}×a; i.e., f⁢(a)∈a.
Each such f is, thus, a choice function on A.
∎