Axiom of Choice and Right Inverse

Solution 1:

This is a very delicate point about the context of domain and codomain, which in set theory exist as an external properties we give functions, rather than internal properties of them (as in category theory).

This means that we first fix some domain and codomain and we can talk about functions from $A$ to $B$. Now we can say that $f$ is surjective if its range is all $B$. Note that without this context there is no codomain, and every function is onto its range, therefore the term "surjective" is meaningless.

Now when we say that a function $f$ has a right inverse we mean that there is $g\colon B\to A$ such that $f\circ g=\text{id}_B$. When we say that $f$ has a left inverse we mean there is such $g\colon B\to A$ for which $g\circ f=\text{id}_A$. Without the axiom of choice we can prove that if a function has a right inverse then it is surjective, and that $f$ is injective if and only if it has a left inverse.

The axiom of choice is equivalent to saying that whenever $A$ and $B$ are two sets, the $f$ is a surjective function if and only if it has a right inverse. But we had set the context first. Of course we can omit it, because we are talking about any set, so we may as well replace $B$ by the range of $f$. But some context must be set for otherwise the term "surjective" is meaningless.

On the other hand, the very basic theorem that $f\colon A\to B$ has an inverse if and only if it is a bijection has nothing to do with the axiom of choice. The statement is really saying that $f$ is a bijection if and only if there is some $g\colon B\to A$ which is both right and left inverse of $f$. From the above remarks you can see that without the axiom of choice if there is an inverse (both left and right, that is) then the function is a bijection; but if it is a bijection then we can construct its left inverse and show that it is also a right inverse.

Solution 2:

One formulation of the Axiom of Choice goes as follows: If $A$ is a set of nonempty and pairwise disjoint sets then there exists a set $C$ such that $C\cap X$ is a singleton set for all $X\in A$

We can show this from the existence of right inverses for every surjective function as follows: Let $A$ be a set of nonempty and pairwise disjoint sets and $B=\bigcup A$. Then for each $b\in B$ there exists exactly one $X\in A$ with $b\in X$. This defines a function $f\colon B\to A$ and $f$ is surjective. Hence it has a right-inverse $g$. Then $C:=\{\,g(X)\mid X\in A\,\}$ is a choice set as required by the Axiom of Choice.

That $f$ has a (two-sided) inverse if and only if $f$ is bijective, does not rely on the Axiom Of Choice:

Assume $f\colon A\to B$ is bijective. Then for each $b\in B$ there exists exactly one $a\in A$ with $f(a)$. We can define $g\colon B\to A$ by letting $g(b)$ the uniquely determined $a$ such that $f(a)=b$ and readily verify that $f\circ g$ and $g\circ f$ are the identities of the respective sets.

Now assume that $f\colon A\to B$ has a left inverse $g\colon B\to A$ and a right inverse $h\colon B\to A$. Then $g=g\circ(f\circ h)=(g\circ f)\circ h=h$, so $g$ is a two-sided inverse. Now $g\circ f=\operatorname{id}_A$ implies that $f$ is injective and $f\circ g=\operatorname{id}_B$ implies that $f$ is surjective. So in summary $f$ is bijective.

Solution 3:

Take the subset $E$ in $A\times \mathcal{P}(A)$ defined by $\{(a,B) : a\in B\}$. Then the second projection is a surjective map onto $\mathcal{P}^*(A)=\mathcal{P}(A)\smallsetminus\{\emptyset\}$. A right inverse, composed with the first projection, yields a selecting function as in AC.

Solution 4:

Adding to Hagen's answer, the existence of a right inverse to any surjection $p: E \to A$ between nonempty sets also implies the axiom of choice (under his formulation).

Suppose $A$ is a (nonempty) set of pairwise disjoint nonempty sets. Let $E = \bigcup A$, and define $p: E \to A$ to be the function that takes an element $e \in E$ to the unique element $a \in A$ for which $e \in a$ (uniqueness follows from disjointness). This function is surjective because each $a \in A$ is nonempty. If $s: A \to E$ is a right inverse, then $s(a)$ picks out an element of $a$, and the image of $s$ is the desired set $C$ in his formulation.