Proof of Axiom of Choice equivalent.

[leetaxx0r]

I'm trying to prove that the axiom of choice is equivalent to the following statement:

For any set $$X$$ and any function $$f:X\to X$$, there exists a function $$g:X\to X$$ such that $$f\circ g\circ f=f$$.​

I was able to prove that the AoC implies this, but I'm having a harder time going the other direction. It seems like if you define an equivalence relation on $$X$$ where $$x\sim y$$ iff $$f(x)=f(y)$$, then the composite function $$g\circ f$$ must map everything in each equivalence class to one of its members.

This seems like it's important, but we're still only choosing points for a very specific collection of subsets of $$X$$, namely the equivalence classes induced by the function. Is there a way to extend this to any collection of subsets, or am I heading in the wrong direction?

 

[grief]

Hmm... this is kind of a weird way of doing it, but I think it works: Let A be a pairwise disjoint family of nonempty sets. Then Let X be (UA)U(A)U{null}. Then define f:X->X by letting f(x)=B if x is in UA and B is in A and x is in B, and letting f(B)=null for B in A, and letting f(null)=null.

Then the equivalence relations include elements of A, since for every element B of A, everything in B and nothing else maps to B.

 

[leetaxx0r]

That looks very clean. Thank you very much. It was the fact that the domain and codomain had to be equal that was causing most of the trouble it seems.