Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Given g from X onto Y, can we find some f from Y into X without the axiom of choice?

  1. May 2, 2012 #1
    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 [itex]X_y = \{ x\in X : g(x) = y \}[/itex] are subsets of X, indexed by Y. In fact, they partition X, for if we had [itex]x\in X_a\cap X_b[/itex] 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 [itex]h(X_y) \in X_y[/itex] for all [itex]y \in Y[/itex]. From here, we can define the injection f(y) = h(Xy).

    Is there a proof which does not use the axiom of choice?
     
  2. jcsd
  3. May 2, 2012 #2
    Re: Given g from X onto Y, can we find some f from Y into X without the axiom of choi



    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
     
  4. May 7, 2012 #3
  5. May 7, 2012 #4

    jgens

    User Avatar
    Gold Member

    Re: Given g from X onto Y, can we find some f from Y into X without the axiom of choi

    That every surjective function has a right inverse is equivalent to the axiom of choice.
     
    Last edited: May 7, 2012
  6. May 7, 2012 #5
    Re: Given g from X onto Y, can we find some f from Y into X without the axiom of choi

    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 [itex]f:X \rightarrow Y[/itex] a surjection.

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

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

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

    Then it's clear that for each y we have [itex]fg(y) = y[/itex]. We say that g is a right inverse of [itex]f[/itex]. 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.
     
    Last edited: May 7, 2012
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Given g from X onto Y, can we find some f from Y into X without the axiom of choice?
Loading...