# Proving one specific equivalent formulation of AC [duplicate]

I will state the axiom of choice and give one equivallent formulation, i am interested in proving the $$\Leftarrow$$ way of the theorem. I will omit details.

Axiom of choice: For collection of nonempty sets $$\mathcal{X}$$ there exists a choice function $$f:\mathcal{X}\rightarrow \bigcup\mathcal{X}$$ such that for an set $$A\in\mathcal{X}$$ is $$f(A)\in A$$. In symbols $$(\forall x)(\emptyset \notin \mathcal{X}\Rightarrow(\exists f: \mathcal{X}\rightarrow \bigcup\mathcal{X})\wedge (\forall A)(A\in X\Rightarrow f(A)\in A)$$

Theorem: The following is equivalent to axiom of choice: For any surjective function $$\varphi:X\rightarrow Y$$ exists $$\psi:Y\rightarrow X$$ s.t. $$\varphi \circ \psi = \operatorname{id}_Y$$.

Proof. $$\Rightarrow$$: Assume AC holds and let $$\varphi:X\rightarrow Y$$ be surjective. Assume this particular system of nonempty sets $$\mathcal{X}=\{\varphi^{-1}(y)\mid y\in Y\}$$. (Yes, they are nonetmpyset, because $$\varphi$$ is a surjection). By AC there exists some $$f:\mathcal{X}\rightarrow \bigcup\mathcal{X}$$ s.t. $$A\in \mathcal{X}$$ implies $$f(A)\in A$$. Apparently $$\bigcup\mathcal{X}=X$$. Define $$g:Y\rightarrow \mathcal{X}$$ by $$g:y\mapsto\varphi^{-1}(y)$$ and finally $$\psi:Y\rightarrow X$$ by $$\psi:y\mapsto f(g(y))$$. Now it is straightforward to show that $$\varphi\circ \psi = \operatorname{id}_Y$$.

Could someone potentionally help me with the other way around? Assuming the theorem and proving axiom of choice? This is what I have so far:

$$\Leftarrow$$: Assume the theorem holds, and assume arbitrary system of nonempty sets $$\mathcal{X}$$. We wish to find a function $$f:\mathcal{X}\rightarrow \bigcup\mathcal{X}$$ satysfying $$A\in \mathcal{X} \Rightarrow f(A)\in A$$.

I am quite unsure where I should be finding that $$f$$. Or where to make use of the surjection. Will the fact that any function $$h$$ can be decomposed into two $$s, i$$ s.t. $$i\circ s = h$$ and $$s$$ is surjective and $$i$$ injective, help me in any way? Help please.

## marked as duplicate by Asaf Karagila♦ axiom-of-choice StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Feb 4 at 8:12

Define $$\bigsqcup \mathcal{X} = \{ (A, a) \mid A \in \mathcal{X} \text{ and } a \in A \}$$. This is just the disjoint union of the sets in $$X$$.
The function $$\bigsqcup \mathcal{X} \to \mathcal{X}$$ defined by $$(A,a) \mapsto A$$ is surjective, so by the assumption, there exists a function $$f' : \mathcal{X} \to \bigsqcup{X}$$ such that $$f'(A) = (A,a)$$ for some $$a \in A$$.
Now there is an evident function $$\pi : \bigsqcup \mathcal{X} \to \bigcup \mathcal{X}$$ defined by $$\pi(A,a) = a$$. The composite $$f = \pi \circ f' : \mathcal{X} \xrightarrow{f'} \textstyle\bigsqcup \mathcal{X} \xrightarrow{\pi} \bigcup \mathcal{X}$$ is then the choice function you desire.