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

Theorem.

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 $\mathrm{dom}(R)=A\text{ and }\mathrm{rng}(R)\subseteq B$. Let $g:A\to 𝒫(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 $⟨a,b⟩\in R$, let $f_{ab}$ send $a$ to $b$ and agree with $f$ elsewhere. Let $F=\{f_{ab}\mid ⟨a,b⟩\in R\}$. Clearly $\bigcup F\subseteq A\times B$, so suppose $⟨u,v⟩\in \bigcup F$; then there is a pair $⟨a,b⟩\in R$ such that $⟨u,v⟩\in f_{ab}\in F$. Either $⟨u,v⟩=⟨a,b⟩$, or $v=f(u)=c\circ g(u)=c(R\left[\{u\}\right])\in R\left[\{u\}\right]$. In each case, $⟨u,v⟩\in R$. Thus, $\bigcup F\subseteq R.$ For each pair $⟨a,b⟩\in R$, $⟨a,b⟩\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 $\mathrm{dom}(R)$ if and only if $x\in \{a\}$ for some $a\in A$. Thus, $\mathrm{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 $\mathrm{dom}(f)=A$, and for each pair $⟨a,f(a)⟩\in f$, $⟨a,f(a)⟩\in \{a\}\times a$; i.e., $f(a)\in a$. Each such $f$ is, thus, a choice function on $A$. ∎

Title	proof that a relation is union of functions if and only if AC
Canonical name	ProofThatARelationIsUnionOfFunctionsIfAndOnlyIfAC
Date of creation	2013-03-22 16:34:23
Last modified on	2013-03-22 16:34:23
Owner	ratboy (4018)
Last modified by	ratboy (4018)
Numerical id	4
Author	ratboy (4018)
Entry type	Proof
Classification	msc 03E25