# 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 \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
$\u27e8a,b\u27e9\in R$, let ${f}_{ab}$ send $a$ to $b$ and agree
with $f$ elsewhere. Let $F=\{{f}_{ab}\mid \u27e8a,b\u27e9\in R\}$. Clearly $\bigcup F\subseteq A\times B$, so suppose
$\u27e8u,v\u27e9\in \bigcup F$; then there is a pair $\u27e8a,b\u27e9\in R$ such that $\u27e8u,v\u27e9\in {f}_{ab}\in F$. Either $\u27e8u,v\u27e9=\u27e8a,b\u27e9$, or $v=f(u)=c\circ g(u)=c(R\left[\{u\}\right])\in R\left[\{u\}\right]$. In each case, $\u27e8u,v\u27e9\in R$.
Thus, $\bigcup F\subseteq R.$ For each pair $\u27e8a,b\u27e9\in R$, $\u27e8a,b\u27e9\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 $\u27e8a,f(a)\u27e9\in f$,
$\u27e8a,f(a)\u27e9\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 |