14
$\begingroup$

I read an Theorem that states:

Let $A$ and $B$ be non-empty sets, and let $f:A \to B$ be a function, then the function $f$ has a right inverse if and only if $f$ is surjective.

The Theorem proof uses Axiom of Choice. My question is, if Axiom of Choice is not true, then is this Theorem false? My question is because I tried to find a proof that not uses the axiom but I did not found it and this result is very important because it implies, with another statement, that a function $f$ has an inverse if and only if $f$ is bijective.

$\endgroup$
  • 1
    $\begingroup$ I'm not sure about the surjectivity statement, but you can skip it and prove directly that a function $f$ has an inverse if and only if it's bijective, and that proof doesn't require the axiom of choice. $\endgroup$ – Jim Aug 8 '13 at 19:21
14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How about the category of sets for objects and inclusion for arrows? Say $A\subsetneq B$, then how do you distinguish the inclusion $i:A\to B$ from the identity $\operatorname i_A$? $\endgroup$ – Oskar Limka Jan 6 '17 at 0:49
  • $\begingroup$ I am certainly not the person to ask about categories and arrows. $\endgroup$ – Asaf Karagila Jan 6 '17 at 7:00
  • $\begingroup$ If $f: A\to B$ is bijective, no need axiom of choice to prove that it's invertible at right ? True ? Indeed, let $f:A\to B$ bijective. Set $R=\{(a,f(a))\mid a\in A\}$. By bijectivity, $\forall b\in B, \exists !a\in A: (a,b)\in R$. Set $R'=\{(b,a)\mid (a,b)\in R\}$. Then $R'$ is a relation because $(y,x)\in R'\iff (x,y)\in R$. Let $g$ the application corresponding to $R'$. Therefore $f\circ g(b)=f(g(b))=b$. Did I used axiom of choice here ? $\endgroup$ – user380364 Aug 30 '18 at 17:30
  • $\begingroup$ @user380364: No, you didn't use the axiom of choice. Because you only have one option for each fiber. $\endgroup$ – Asaf Karagila Aug 30 '18 at 17:31
  • $\begingroup$ Ok, so the trick is really when there is many choice (I suppose infinitely many, no ?). I'll think about it... thank you. $\endgroup$ – user380364 Aug 30 '18 at 17:32
6
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You should put $ signs around your MathJax code for it to be rendered properly, like $A\times P(A)$ -> $A\times P(A)$. $\endgroup$ – A.P. Apr 1 '15 at 20:49
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It may be late at night, but I don't see where your proof differs from mine except having $E$ instead of $B$ $\endgroup$ – Hagen von Eitzen Aug 8 '13 at 22:18
  • $\begingroup$ @HagenvonEitzen Sorry; I read your answer too quickly, thinking you were proving the existence of a section of a surjection, given this traditional form of AC. (I think I interposed "this from", reading "from this" instead.) $\endgroup$ – user43208 Aug 9 '13 at 0:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.