surjection and axiom of choice

In this entry, we show the statement that

(*) every surjection has a right inverse

is equivalent to the axiom of choice (AC).

Proposition 1.

AC implies (*).

Proof.

Let $f:A\to B$ be a surjection. Then the set $C:=\{f^{-1}(y)\mid y\in B\}$ partitions $A$ . By the axiom of choice, there is a function $g:C\to\bigcup C$ such that $g(f^{-1}(y))\in f^{-1}(y)$ for every $y\in B$ . Since $\bigcup C=A$ , $g$ is a function from $C$ to $A$ . Define $h:B\to A$ by $h(y)=g(f^{-1}(y))$ . Then $h(y)\in f^{-1}(y)$ , and therefore $(f\circ h)(y)=f(h(y))=y$ , implying that $f$ has a right inverse. ∎

Remark. The function $h$ is easily seen to be an injection: if $h(y_{1})=h(y_{2})$ , then $y_{1}=f(h(y_{1}))=f(h(y_{2}))=y_{2}$ .

Proposition 2.

(*) implies AC.

Before proving this, let us remark that, in the collection $C$ of non-empty sets of the axiom of choice, there is no assumption that the sets in $C$ be pairwise disjoint. The statement

(**) given a set $C$ of pairwise disjoint non-empty sets, there is a choice function $f:C\to\bigcup C$

seemingly weaker than AC, turns out to be equivalent to AC, and we will prove this fact first.

Proof.

Obviously AC implies (**). Conversely, assume (**). Let $C$ be a collection of non-empty sets. We assume $C\neq\varnothing$ . For each $a\in C$ , define a set $A_{a}:=\{(x,a)\mid x\in a\}$ . Since $a\neq\varnothing$ , $A_{a}\neq\varnothing$ . In addition, $A_{a}\cap A_{b}=\varnothing$ iff $a\neq b$ (true since elements of $A_{a}$ and elements of $A_{b}$ have distinct second coordinates). So the collection $D:=\{A_{a}\mid a\in C\}$ is a set consisting of pairwise disjoint non-empty sets. By (**), there is a function $f:D\to\bigcup D$ such that $f(A_{a})\in A_{a}$ for every $a\in C$ . Now, define two functions $g:C\to D$ and $h:\bigcup D\to\bigcup C$ by $g(a)=A_{a}$ and $h(x,a)=x$ Then, for any $a\in C$ , we have $(h\circ f\circ g)(a)=h(f(A_{a}))$ . Since $f(A_{a})\in A_{a}$ , its first coordinate is an element of $a$ . Therefore $h(f(A_{a}))\in a$ , and hence $h\circ f\circ g$ is the desired choice function. ∎

Proof of Propositon 2.

We show that (*) implies (**), and since (**) implies AC as shown above, the proof of Proposition 2 is then complete.

Let $C$ be a collection of pairwise disjoint non-empty sets. Each element of $\bigcup C$ belongs to a unique set in $C$ . Then the function $g:\bigcup C\to C$ taking each element of $\bigcup C$ to the set it belongs in $C$ , is a well-defined function. It is clearly surjective. Hence, by assumption, there is a function $f:C\to\bigcup C$ such that $g\circ f=1_{C}$ (a right inverse of $g$ ). For each $x\in C$ , $g(f(x))=x$ , which is the same as saying that $f(x)$ is an element of $x$ by the definition of $g$ . ∎

Remark. In the category of sets, AC is equivalent to saying that every epimorophism is a split epimorphism. In general, a category is said to have the axiom of choice if every epimorphism is a split epimorphism.

Title	surjection and axiom of choice
Canonical name	SurjectionAndAxiomOfChoice
Date of creation	2013-03-22 18:44:37
Last modified on	2013-03-22 18:44:37
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	9
Author	CWoo (3771)
Entry type	Derivation
Classification	msc 03E25