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

x, y \in A, x \ge y

define a total ordering in B,

f(x) \ge f(y)

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:

x \leq y \leq x​

without having

x = y​

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 g(b) = \{a \in A | f(a) = b\}? Then g(b) would be a subset of A and so well ordered, and I think I can finish the proof from there.