# Homework Help: Composite of two injections is an injection

1. Jul 19, 2010

### Jamin2112

1. The problem statement, all variables and given/known data

That's what I'm supposed to prove.

2. Relevant equations

A function f is an injection if

f(x1)=f(x2) ---> x1=x2

3. The attempt at a solution

I'm just having trouble constructing a formal proof. I mean, it's obvious that f(g(x1))=f(g(x2)) then either g(x1)=g(x2) or g(x1)≠g(x2), and since g(x1)≠g(x2) implies x1≠x2, ......

I don't know. I'm getting all tongue-tied. Help me out here.

2. Jul 19, 2010

### hunt_mat

f and g are injective then is $$g\circ f$$?, write down wheat it means for f to be injective (f(a)=f(b)=>a=b), what it means for g and what it means for $$g\circ f$$ and you should have your proof, it's a one liner.

3. Jul 19, 2010

### Staff: Mentor

Since f is an injection, you won't have the latter case. Since f(g(x1))=f(g(x2)) then g(x1)=g(x2), because f is an injection.

4. Jul 20, 2010

### Jamin2112

Proof.

Let h=f(g(x)), where f and g are injective functions.

h(x1)=h(x2) $$\Rightarrow$$ f(g(x1))=f(g(x2)) $$\Rightarrow$$ g(x1)=g(x2) (since f is an injection) $$\Rightarrow$$ x1=x2 (since g is an injection)

5. Jul 20, 2010

### Jamin2112

But the next question asks me to show that the composite of two surjections is a surjection. I'll give it a shot.

Proof. Let f:A$$\rightarrow$$B and g:C$$\rightarrow$$D be surjections.

( $$\forall$$ b$$\in$$B ) ( $$\exists$$ a$$\in$$A ) ( f(a)=b )

( $$\forall$$ d$$\in$$D ) ( $$\exists$$ c$$\in$$C ) ( f(c)=d )

Let h=f(g(x)).

....

Not sure where to go from here. Can someone give me a jump start?

6. Jul 20, 2010

### hunt_mat

Same as before with the injection, f:A->B and g:C->A. f is surjective then for all g(c) in A there is an b in B such that f(g(c))=b. What does it mean for g to be surjective?

You have to define your maps correctly.

7. Jul 20, 2010

### Jamin2112

So why is the domain of f the same as the codomain of g?

8. Jul 20, 2010

### hunt_mat

because you're looking at f(g(x)), g has to map to something that f can map from. I prefer the term image to codomain, you may hear that from time to time.

Last edited: Jul 20, 2010
9. Jul 20, 2010

### Jamin2112

Why couldn't I just say ...

Let f:A-->B and g:C-->D be surjections. For all b in B, there exists an a in A such that f(a)=b, and for all d in D, there exists a c in C such that f(c)=d. The composite function h(x)=f(g(x)) will map the set C to the set A. h will be a surjection if for all a in A, there exists a c in C such that f(c)=a.

.... I don't know. Still don't get it.

10. Jul 20, 2010

### hunt_mat

No, sorry. You have to think about the two functions f & g. You can define g:A->B, so take an a in A, g will map this from A into B with a value g(a). Now as we're considering the composition f(g(a)). The value g(a) must lie in the domain of f for the composition to make sense, otherwise the composition f(g(a)) wouldn't make sense. Are you with me so far?

f will have to be a map f:B->C, so that the composition $$f\circ g:A\rightarrow C$$ makes sense. I think your confused about the composition of functions.

11. Jul 21, 2010

### Jamin2112

I'm with you.

12. Jul 21, 2010

### hunt_mat

So I think now you're able to complete the question using the same sort of logic as you did with the injective part.