# surjection and axiom of choice

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.

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$. ∎

Title surjection and axiom of choice SurjectionAndAxiomOfChoice 2013-03-22 18:44:37 2013-03-22 18:44:37 CWoo (3771) CWoo (3771) 9 CWoo (3771) Derivation msc 03E25