Are $X$ and $Y$ the same in these two equivalent formulations of the axiom of choice?

Question

I'm having troubles understanding how the following definition is a possible version of the axiom of choice:

Let $X,Y$ be sets and $f:$ $X$$\,\to\,$$Y$ a surjective function, then a function $g:$ $Y$$\,\to\,$$X$ exists with $f \circ g = i$ with $i$ the identity function of $Y$.

I'm familiar with the following definition of the axiom of choice:

Let $Y$ be a set and $\chi$ a subset of $\mathcal{P}(Y)$, then a function $\alpha$ : $\chi $$\,\to\,$ $Y$ exists with $\alpha(X)\in X$ for every $X \in \chi$.

More precisely I don't understand what $X,Y$ represents in the first definition in regards to the second one. Is $Y$ the same in both? Is $X$ in the first definition the equivalent of $\chi$ in the second one?

Answer 1

The choice function should be definable for a collection of non-empty sets, so we demand that $\forall A \in \chi: A \neq \emptyset$

If $f:X \to Y$ is surjective we apply the choice function to the family $\chi=\{f^{-1}[\{y\}]: y \in Y\} \subseteq \mathscr{P}(X)$, which is a set of non-empty subsets iff $f$ is surjective.

The $X$ and $Y$ in both formulations are independent of each other (they're just "local names", or technically "bound variables". Here we apply the second one for the set $Y=X$ (where $X$ is from the first one).

Answer 2

It may be easier to see how things work if we introduce a different (seemingly weaker) version of the axiom that you are already familiar with:

Let $Y$ be a set and $\chi$ be a subset of $\mathcal{P}(Y)$ whose members are all nonempty and mutually disjoint, then a function $\alpha:\chi\rightarrow Y$ exists with $\alpha(X)\in X$ for every $\chi\in X$.

The part that I've put in bold makes it seem weaker, but it really isn't (I'll write a bit about this at the bottom).

It is more natural to prove an equivalence between the above statement, which I'll call Axiom $A$, and the one you are unsure about that involves right-inverses, which I'll call Axiom $B$. This will show you how the two connect and what roles the variables occupy in relating the two versions of the axiom of choice.

$\underline{\textrm{Axiom}\; A\Rightarrow \textrm{Axiom}\; B}$

Assume Axiom $A$. Let $f:X\rightarrow Y$ be a surjective function.

The indexed family of sets $\{f^{-1}(y)\}_{y\in Y}$ is a subset of $\mathcal{P}(X)$. Also, all members are nonempty as $f$ is surjective. And they're all mutually disjoint (as if a point belonged to two distinct members of $\{f^{-1}(y)\}_{y\in Y}$, it would have a non-unique image under f). Now, apply Axiom $A$ to this subset to get a function, $\alpha:\{f^{-1}(y)\}_{y\in Y}\rightarrow X$, which sends each set $\{f^{-1}(y)\}$ to a member of itself. Finally, if we define $g:Y\rightarrow X$ by $g(y)=\alpha(\{f^{-1}(y)\})$, it is easy to see that this is the desired right-inverse of $f$.

$\underline{\textrm{Axiom}\; B\Rightarrow \textrm{Axiom}\; A}$

Assume Axiom $B$. Let $Y$ be a set and $\chi$ be any subset of $\mathcal{P}(Y)$ whose members are all nonempty and mutually disjoint.

We can define a function $f: \cup_{X\in\chi} X\rightarrow \chi$ so that $f(X)=X\;\forall\; X\in \chi$ (note $f$ takes elements in $Y$ as input and outputs elements in $\chi$ so $f(X)$ is the image of all $y\in X$ under $f$). Given that all the members of $\chi$ are mutually disjoint, it is easy to see that $f^{-1}(X)=X\;\forall\; X\in\chi$

Now, by Axiom $B$, there exists a function, $g: \chi\rightarrow \cup_{X\in\chi}$, that is a right-inverse of $f$. This means, for any $X\in \chi$, $(f\circ g)(X)=X\Rightarrow g(X)\in f^{-1}(X)=X$, i.e. $g(X)\in X\;\forall\; X\in\chi$ ($g$ takes members of $\chi$ as inputs and outputs members of $Y$, so the notation with the $X$s is a bit confusing).

Finally we define $\alpha: \chi\rightarrow Y$ as $\alpha(X)=g(X)$ (the only difference between $\alpha$ and $g$ is that of codomains - $\alpha$'s is bigger). Since $g(X)=X$ always, it is clear that $\alpha$ is the desired function in the statement of Axiom $A$, so we are done.

---

Now, as to how Axiom $A$ is equivalent to the version in your question (the one you say you are already familiar with):

Let $Y$ be a set and $\chi$ be a subset of $\mathcal{P}(Y)$ whose members are all nonempty, then a function $\alpha:\chi\rightarrow Y$ exists with $\alpha(X)\in X$ for every $\chi\in X$.

Call the above Axiom $C$. Clearly Axiom $C$ implies Axiom $A$ (because Axiom $A$ is just a special case of Axiom $C$). But, somewhat counterintuitively, the converse is also true.

$\underline{\textrm{Axiom}\; A\Rightarrow \textrm{Axiom}\; C}$

Let $Y$ be a set and $\chi$ be a subset of $\mathcal{P}(Y)$ whose members are all nonempty.

We turn our attention to the set $Z=\{y\times\{X\}|y\in Y,X\in \mathcal{P}(Y),\}$.

Because of the way $Z$ has been defined, anything of the form $S\times \{S\}$ (where $S$ is any nonempty member of $\mathcal{P}(Y)$) will be a subset of $Z$ i.e. it will belong to $\mathcal{P}(Z)$.

Which means, in particular, that the set $\nu=\{X\times \{X\}|X\in\chi\}$ is a subset of $\mathcal{P}(Z)$. As all members $X\in\chi$ are nonempty, all members of $\nu$ are also nonempty. But, because of the second components all $\nu$'s elements possess, they are all necessarily pairwise disjoint. So we can apply Axiom $A$ to get a function $\beta: \nu\rightarrow Z$ s.t. $\beta(W)\in W\;\forall\;W\in \nu$ i.e. $\beta(X\times \{X\})\in X\times\{X\}\;\forall\; X\in\chi$.

If we look at the first component of $\beta$'s image, we see that it is basically what we want.

Finally, define $p:Z\rightarrow Y, p(y\times\{X\})=y\;\forall\;y\in Y\;\forall\;X\in\mathcal{P}(Y)$ and $\alpha':\chi\rightarrow Z, \alpha'(X)=\beta(X\times \{X\})$, it is relatively easy to see that $\alpha: \chi\rightarrow Y, \alpha=p\circ \alpha'$ is the desired function (basically $\alpha$ is just picking up the first component of what ever $\alpha'$ outputs. $\alpha'$ in turn is just like $\beta$ except it directly takes elements $X\in \chi$ as input rather than the roundabout way that $\beta$ takes $X$).