Denumerable set and surjective function

1. Oct 19, 2011

autre

This is the problem:

"Prove that if A is denumerable and there exists a g: A -> B that is surjective, then there exists an h: B -> A so that h is injective."

So I've started it as:

Suppose a set A is denumerable and a function f: A-> B is surjective. Since there exists a surjective function f: A-> B and A is denumerable, B is countable..."

I'm a little stuck here. Any ideas?

2. Oct 20, 2011

autre

Any ideas?

3. Oct 20, 2011

autre

I'm really stuck guys

4. Oct 20, 2011

micromass

Staff Emeritus
Try to explicitely define h. You won't need anywhere that A and B are denumerable.

Try to define h as some kind of "inverse" of g.

5. Oct 20, 2011

AKG

Try a simpler problem first, replacing the assumption "A is denumerable" with "A = N, the set of natural numbers." If you have surjection g : N --> B, you can explicitly define an injection h : B --> N in terms of g. See if you can figure that out first.

6. Oct 20, 2011

autre

Good idea.

Suppose there exists a function f: N -> B for some set B. Then, for all b in B, there exists an n in N such that f(n) = b. Define h: B-> A as the function that maps all b in B to a single n in N such that h(b) = n. Since f is surjective, there exists such a function. Since h(b') = h(b) = n iff b' =/= b, h is injective.

Am I on the right track?

7. Oct 20, 2011

AKG

Great. For each b, there might be a number of different n's you could choose. How might you explicitly choose one of those n's from amongst all the possible choices, if you had to?
This isn't quite right, perhaps a typo?
Yes.

8. Oct 20, 2011

autre

Perhaps an n such that if f(n) = f(n') = b, n=n'?

Not a typo, just brainstorming.

9. Oct 20, 2011

disregardthat

How may you explicitly choose an element from a subset of the natural numbers?

You can use the axiom of choice, or a much easier method which you probably are familiar with.

10. Oct 20, 2011

autre

The well-ordering principle?

11. Oct 21, 2011

autre

Quick question, can I assume A = N without loss of generality?

12. Oct 21, 2011

disregardthat

Why wonder when you can just pick the smallest one?

You can assume A = N if you are comfortable with the proof of how it applies generally (hint: A is in bijection with N).

13. Oct 21, 2011

autre

I'm not sure if we have gone over the theorem that states that every subset of N has a smallest element, is it related to the well-ordering principle?

So perhaps something like this:

Suppose there exists a function f: N -> B for some set B. Then, for all b$\in$B, there exists an n$\in$N such that f(n) = b. Define h: B-> N as the function f(b) = n' where for all b$\in$B, n'$\in$N' is the smallest element of some N'$\subseteq$N. Thus, h is injective.

14. Oct 21, 2011

disregardthat

Well, it's obvious isn't it? If n is a number in a subset A of N, then one of 1,2,3,...,n is the smallest element of the set. Prove: Every subset of the natural numbers containing the number n has a smallest element, by induction on n.

There is something weird about defining h(b) = n', where n' is the smallest element of some subset N' of N. You must specify this subset, or else h is not well-defined (it can't be any arbitrary set). I suggest you define N' = f^(-1)(b) (= the set {n in N : f(n) = b}). Then you can show injectiveness.

15. Oct 21, 2011

autre

Ah, I think I have seen that before. In light of this, does the proof I provided above work?