Set Theory proof on well ordered sets

[oliphant]

Homework Statement

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.

Homework Equations

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.

 

[clamtrox]

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.

 

[Hurkyl]

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!

 

[Hurkyl]

P.S. how would you do the problem if you assumed the axiom of choice?

 

[oliphant]

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.