# 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\ne \mathrm{\varnothing}$. For each $a\in C$, define a set ${A}_{a}:=\{(x,a)\mid x\in a\}$. Since $a\ne \mathrm{\varnothing}$, ${A}_{a}\ne \mathrm{\varnothing}$. In addition, ${A}_{a}\cap {A}_{b}=\mathrm{\varnothing}$ iff $a\ne 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 |