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.