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


A relationMathworldPlanetmath R is the union of a set of functionsMathworldPlanetmath 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.


Suppose that R is a relation with dom(R)=A and rng(R)B. Let g:A𝒫(B) be given by aR[{a}]. There is be a choice function c on g[A]. Let f=cg, and for each pair a,bR, let fab send a to b and agree with f elsewhere. Let F={faba,bR}. Clearly FA×B, so suppose u,vF; then there is a pair a,bR such that u,vfabF. Either u,v=a,b, or v=f(u)=cg(u)=c(R[{u}])R[{u}]. In each case, u,vR. Thus, FR. For each pair a,bR, a,bfabF, so RF. Therefore, R=F.
Suppose that A is set of nonempty sets. Let R={{a}×aaA}. A set x is an element of dom(R) if and only if x{a} for some aA. Thus, dom(R)=A. There is a set F of functions, each of which has domain A, such that R=F. Let fF; 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. ∎

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