1
$\begingroup$

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.

$\endgroup$
1

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – TylerD007
    Feb 29 at 0:57
  • $\begingroup$ @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 $. $\endgroup$ Feb 29 at 17:02
1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – TylerD007
    Feb 29 at 1:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .