## You are here

Homesurjection and axiom of choice

## Primary tabs

# 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.

## Mathematics Subject Classification

03E25*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections