Can Every Surjection Have a Right Inverse Without the Axiom of Choice?

[Unit]

I thought of this today while eating apples.

Suppose we have two arbitrary sets X and Y and a surjection g:X→Y. We seek an injection f:Y→X. Each element of Y has at least one pre-image in X, but there might be more than one; the nonempty sets $X_y = \{ x\in X : g(x) = y \}$ are subsets of X, indexed by Y. In fact, they partition X, for if we had $x\in X_a\cap X_b$ then, by definition, a = g(x) = b. Thus these sets are pairwise disjoint; by the axiom of choice, there exists a function h such that $h(X_y) \in X_y$ for all $y \in Y$. From here, we can define the injection f(y) = h(X_y).

Is there a proof which does not use the axiom of choice?

 

[DonAntonio]

I thought of this today while eating apples.

Suppose we have two arbitrary sets X and Y and a surjection g:X→Y. We seek an injection f:Y→X. Each element of Y has at least one pre-image in X, but there might be more than one; the nonempty sets $X_y = \{ x\in X : g(x) = y \}$ are subsets of X, indexed by Y. In fact, they partition X, for if we had $x\in X_a\cap X_b$ then, by definition, a = g(x) = b. Thus these sets are pairwise disjoint; by the axiom of choice, there exists a function h such that $h(X_y) \in X_y$ for all $y \in Y$. From here, we can define the injection f(y) = h(X_y).

Is there a proof which does not use the axiom of choice?

In the general case? I highly doubt it. For particular cases it may be,

for example for finite X (and, thus, finite Y), or perhaps some weak case of AC if X is countable...

DonAntonio

 

[lugita15]

This is somewhat related:
http://en.wikipedia.org/wiki/Cantor–Bernstein–Schroeder_theorem

 

[jgens]

That every surjective function has a right inverse is equivalent to the axiom of choice.

 

[SteveL27]

I thought of this today while eating apples.

Suppose we have two arbitrary sets X and Y and a surjection g:X→Y. We seek an injection f:Y→X. Each element of Y has at least one pre-image in X, but there might be more than one; the nonempty sets $X_y = \{ x\in X : g(x) = y \}$ are subsets of X, indexed by Y. In fact, they partition X, for if we had $x\in X_a\cap X_b$ then, by definition, a = g(x) = b. Thus these sets are pairwise disjoint; by the axiom of choice, there exists a function h such that $h(X_y) \in X_y$ for all $y \in Y$. From here, we can define the injection f(y) = h(X_y).

Is there a proof which does not use the axiom of choice?

I think you might have this a little backward, but let me try to straighten this out. You can tell me if I'm understanding you correctly.

To get to the conclusion right away: As jgens noted, the statement "every surjection has a right inverse" is equivalent to the Axiom of Choice. I think it's what you're getting at.

When doing problems with maps between two sets, there's a convention that f goes left to right and g goes right to left. It's very confusing to start with g:X->Y. So if you don't mind I'll change your notation to conform to this convention.

So we have $f:X \rightarrow Y$ a surjection.

For each $y \in Y$ we can define the inverse image of $y$, exactly as you have it above:

$f^{-1}(y) = X_y = \{ x\in X : f(x) = y \}$ and for each $y$ this is a nonempty set.

Now the collection of sets $f^{-1}(y)$ does of course partition X; and using the Axiom of Choice we can define $g:Y \rightarrow X$ by choosing $g(y) \in f^{-1}(y)$.

Then it's clear that for each y we have $fg(y) = y$. We say that g is a right inverse of $f$. And we have just proved that AC implies that every surjection has a right inverse.

[Remember that fg means we do g first! This is a common point of confusion]

It turns out that you can go back the other way: "Every surjection has a right inverse" implies AC. [Needs proof of course.] So they are equivalent.

I'm not sure where you were going with the bit about an injection; so if I'm not sure if I answered the question you actually meant to ask. However I seem to recall that every injection has a left inverse; and this does not require any form of Choice.