# If $f$ is surjective, it has a right inverse

I've been struggling to understand how the surjection of a function $$f : X \rightarrow Y$$ implies that it has a right inverse. My questions basically reside on the application of the axiom of choice to the proof.

First question: The axiom of choice states that, for any set $$Y$$, if $$\varnothing \not\in Y$$, then there exists a function $$g : Y \rightarrow \bigcup_{y\in Y} X_y$$. such that $$\forall y \in Y g(y)\in X_y$$. Why, if $$f : X \rightarrow Y$$ is surjective, $$\varnothing \not\in Y$$? I can't find my way on this one.

Second question: As far as I understand, $$\bigcup_{y\in Y} X_y$$ represents the union of a family of the sets $$X_y$$ indexed by the elements $$y\in Y$$. Hence, $$\bigcup_{y\in Y} X_y$$ is equal to $$\{x : \exists y \in Y (x\in X_y)\}$$. If $$X_y$$ is defined as $$\{x\in X : y=f(x)\}$$, then $$\{x : \exists y\in Y (x\in X_y)\}$$ is equal to $$\{x : \exists y[y\in Y \land x\in X \land y=f(x)]\}$$, which is the same as $$\{x \in X : f(x) \in Y\}$$. The set $$\{x \in X : f(x) \in Y\}$$ is equal to the inverse image $$g[Y]$$, which is equal to $$X$$, since $$f : X \rightarrow Y$$. Hence, $$\bigcup_{y\in Y} X_y$$ is equal to $$X$$ and $$g : Y \rightarrow \bigcup_{y\in Y} X_y$$ is equivalent to $$g : Y \rightarrow X$$. Is this correct?

Third question: If we define $$X_y$$ as being equal to $$\{x\in X : y=f(x)\}$$, then $$\forall y\in Y g(y)\in X_y$$ is equivalent to $$\forall y \in Y g(y)\in X \land y=f(g(y))$$. Is this also correct?

If my (incomlete) proof attempt is correct, the axiom of choice $$g : Y \rightarrow \bigcup_{y\in Y} X_y$$. such that $$\forall y \in Y g(y)\in X_y$$, considering $$X_y$$ equal to $$\{x\in X : y=f(x)\}$$, could be rewritten as $$g : Y \rightarrow X$$, such that $$\forall y \in Y \hspace{0.5em} g(y)\in X \land y=f(g(y))$$, which concludes our proof.

I apologize for the basic questions, but this all seems very confusing for me.

• Feb 29 at 11:41

Your statement of the Axiom of Choice is unclear, because you never explain what $$X _ y$$ is. There are two ways to fix this (and if you're going through a course or a textbook, then you should probably find out which version of AC they're using):

1. If $$\varnothing \notin Y$$, then there's a function $$g \colon Y \to \bigcup Y$$ (that is $$g \colon Y \to \bigcup _ { y \in Y } y$$) such that for each $$y \in Y$$, $$g ( y ) \in y$$.
2. If $$X$$ is a $$Y$$-indexed family of sets and for each $$y \in Y$$, $$X _ y \ne \varnothing$$, then there's a function $$g \colon Y \to \bigcup _ { y \in Y } X _ y$$ such that for each $$y \in Y$$, $$g ( y ) \in X _ y$$.

I'll call these two versions AC1 and AC2.

First question: There is no reason why $$\varnothing \notin Y$$. If you use AC1, then the $$Y$$ in your hypothesis is not the same as the $$Y$$ in AC. Instead of $$Y$$, you have to use $$\{ A \subseteq X \; | \; \exists \, y \in Y , \; A = f ^ * [ \{ y \} ] \}$$, the set of all preimages under $$f$$ of elements of $$Y$$. These preimages are all nonempty, because $$f$$ is surjective. On the other hand, if you use AC2, then they are the same $$Y$$, but you don't need $$\varnothing \notin Y$$ but rather $$X _ y \ne \varnothing$$, and this is the case if $$X _ y : = f ^ * [ \{ y \} ]$$, which is nonempty because $$f$$ is surjective.

For the other two questions, your development seems correct, but notice that you're using AC2. So you'll need to rewrite this a bit if you want to use AC1.

• Thank you for the reply, Mr Bartels. Yes, I noticed some textbooks use $AC1$ and some others $AC2$, but I never actually realized they would mean different things. I will try to reformulate my proof in both versions, using your definition of $Y$ with $AC1$. The only part of your explanation I didn't understand fully is why you translate $\bigcup Y$ as $\bigcup_{y\in Y} y$. Does the letter $y$ stand for a set or an element? Textbooks usually define $\bigcup Y$ as $\{x: \exists X \in Y (x\in X)\}$, so your formulation is new to me. Feb 29 at 0:57
• @TylerD007 : In pure set theory, everything is a set, but in $\bigcup _ { y \in Y } y$, the lowercase $y$ stands specifically for those sets that are elements of $Y$. (In AC1, even in a set theory with non-set elements, $Y$ has to be a collection of sets.) Notice that for any $Y$-indexed family of sets, $\bigcup _ { y \in Y } X _ y$ is defined as $\{ x \; | \; \exists \, y \in Y , \; x \in X _ y \}$, so for the identity family where $X _ y = y$, we get $\bigcup _ { y \in Y } y = \{ x \; | \; \exists \, y \in Y , \; x \in y \}$, which is the same thing as $\bigcup Y$. Feb 29 at 17:02

If $$f:X\to Y$$, maybe $$\emptyset\in Y$$. I mean, we don't really know or care about that. The things which we require to be nonempty in the standard proof are the fibres $$f^{-1}(y)$$, $$y\in Y$$, and we would look at a choice function on $$K:=\{f^{-1}(y):y\in Y\}$$. Which, by the way, is NOT equal to $$\bigcup_{y\in Y}f^{-1}(y)$$; the line:

"$$\{X_y:y\in Y\}=\bigcup_{y\in Y}X_y$$"

Is incorrect. The elements of the left hand side are just the sets $$X_y$$, not the elements of the sets $$X_y$$ (which are what live in the right hand side).

But please note that the choice function $$g$$ on $$K$$ is not the function $$Y\to X$$ that we want. $$K$$ is not $$Y$$! We do not use a choice function on $$Y$$!! We use a choice function on the set $$K$$ of all fibres,... because that's exactly what we want to do, choose a preimage of $$y$$ for each $$y$$.

To your third question: yes, that's the point. Given a choice function $$g$$ on $$K$$, we know $$g(f^{-1}(y))\in f^{-1}(y)$$ thus $$\phi:Y\ni y\mapsto g(f^{-1}(y))\in X$$ satisfies $$f(\phi(y))=y$$ for all $$y\in Y$$. Note $$\phi$$ is not $$g$$! They don't even have the same domain.

• Thank you for your reply, Mr. FShrinke. Yes, I noticed my mistake and edited my original post soon after, but I think you were faster than me. Feb 29 at 1:01