1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Set Theory proof on well ordered sets

  1. Nov 22, 2009 #1
    1. The problem statement, all variables and given/known data

    Without using the Axiom of Choice, show that if A is a well-ordered set and f : A -> B is a surjection to any set B then there exists an injection B -> A.

    2. Relevant equations

    3. The attempt at a solution
    I was wondering if the existence of the surjection from a well ordered set A implies that B is well ordered, and if so how would I prove this? Is this even the right way to start? I'm pretty lost on this so any starting hints would be appreciated.
  2. jcsd
  3. Nov 22, 2009 #2
    You can always find a total ordering by just saying that given

    [tex] x, y \in A, x \ge y [/tex]

    define a total ordering in B,

    [tex] f(x) \ge f(y) [/tex]

    Now you have to show that that's also a well-ordering. That should be pretty straightforward too. Just take a nonempty subset of B and show that it has a smallest element. Since f is a surjection, for every point in the subset there's a corresponding point in a subset of A so you should be able to find it.
  4. Nov 22, 2009 #3


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You have to show that relation is an ordering first. It's not: here's a counterexample:

    A = {1, 2, 3}
    B = {x, y}
    f(1) = f(3) = x
    f(2) = y

    Your relation has:
    [tex]x \leq y \leq x[/tex]​
    without having
    [tex]x = y[/tex]​

    So, more care is needed....

    I think basic algebra will help. You know pretty much nothing about A and B, aside from the existence of a surjection f:A-->B.

    So, if we cross our fingers and hope that we don't have to do something convoluted, if we were to go about defining a function g:B-->A, what are the only reasonable possibilities for g(b)? (For any particular b in B) Is there anything at all about A that relates to b?

    Of course, you shouldn't just do it my way. Your idea can be made to work too. It's better to do things both ways -- you get more experience that way! :biggrin:
  5. Nov 22, 2009 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    P.S. how would you do the problem if you assumed the axiom of choice?
  6. Nov 23, 2009 #5
    We were actually given a proof using the Axiom of Choice by applying it to the set {f^-1 (b) | b \in B} and defining g(b) = c(f^-1(b))

    What if I was to define [tex]g(b) = \{a \in A | f(a) = b\}[/tex]? Then [tex]g(b)[/tex] would be a subset of A and so well ordered, and I think I can finish the proof from there.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook