Denumerable set and surjective function

[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?

 

[autre]

Any ideas?

 

[autre]

I'm really stuck guys

 

[micromass]

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.

 

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

 

[autre]

Try a simpler problem first, replacing the assumption "A is denumerable" with "A = N, the set of natural numbers."

Good idea.

How about 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-> 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?

 

[AKG]

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.

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?

Since h(b') = h(b) = n iff b' =/= b, h is injective.

This isn't quite right, perhaps a typo?

Am I on the right track?

Yes.

 

[autre]

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?

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

This isn't quite right, perhaps a typo?

Not a typo, just brainstorming.

 

[disregardthat]

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

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.

 

[autre]

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

The well-ordering principle?

 

[autre]

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

 

[disregardthat]

The well-ordering principle?

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

 

[autre]

Why wonder when you can just pick the smallest one?

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\inB, there exists an n\inN such that f(n) = b. Define h: B-> N as the function f(b) = n' where for all b\inB, n'\inN' is the smallest element of some N'\subseteqN. Thus, h is injective.

 

[disregardthat]

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?

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.

 

[autre]

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 natural numbers containing n has a smallest element by induction on n.

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