# Proof of Axiom of Choice equivalent.

1. Dec 1, 2009

### 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?

2. Dec 1, 2009

### 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.

3. Dec 1, 2009

### 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.