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.