# Homework Help: Set Theory proof on well ordered sets

1. Nov 22, 2009

### oliphant

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. Nov 22, 2009

### 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.

3. Nov 22, 2009

### Hurkyl

Staff Emeritus
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

$$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!

4. Nov 22, 2009

### Hurkyl

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

5. Nov 23, 2009

### 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.