Proving that axiom of choice is equivalent to this proposition

Question

I'm trying to do the problem 8.2 of the book Notes on Set Theory of Moschovakis.

I want to prove that Axiom of Choice is equivalent to this statement:

$$\forall A\neq \emptyset,\, \forall f:A\longrightarrow B, \,\exists g: B\longrightarrow A \text{ such that } \forall x\in A,\, f(g(f(x)))=f(x).$$

I'm using this form of axiom of choice

(AC) $$(\forall x\in A)(\exists y\in B) P(x,y) \Rightarrow (\exists f:A\longrightarrow B)(\forall x\in A)P(x,f(x))$$

---

To prove that (AC) implies I think if we make

$$P(x,y)\Longleftrightarrow y\in x\setminus (\cup A \setminus x)$$

then $g(x)=f^{-1}(x)$ if $x\in\operatorname{Im}(f), g(x)=$ an arbitrary element of $A$ otherwise, is well defined and satisfies the statement. Is this legal?

I would like you to give a hint to prove the other implication.

Answer 1

You can't quite write $f^{-1}(x)$, since $f$ might not be injective, or reversible.

The key here is to note two things:

1. (Which you've done) It doesn't matter how you define $g$ outside $\operatorname{Im}(f)$, since $A$ is not empty, this can be any arbitrary choice.

2. We need the axiom of choice to produce $g$, so $P(x,y)$ needs to be between $B$ and $A$ (the roles are reversed here). Try $P(b,a)\iff f(a)=b$.

---

In the other direction, the goal is to have the function which exists as promised by the assumption to be your choice function. So $\exists g$ and $\exists f$ should be somewhat similar.

So given $X$ and $Y$ such that $P\subseteq X\times Y$ and $\operatorname{dom}(P)=X$, we need to find some $A$ and $B$ and a function $f\colon A\to B$ such that the map $g\colon B\to A$ will help us define $h\colon X\to Y$ for which $P(x,h(x))$ holds.

Note that $h$ chooses for each $x$ some element $y\in\{y\mid P(x,y)\}$. What would happen if we take $A=P$ and $B=X$, and $f(x,y)=x$, what does $g\colon X\to A$ will guarantee us? And what can we define from it?