Composite of two injections is an injection

[Jamin2112]

Homework Statement

That's what I'm supposed to prove.

Homework Equations

A function f is an injection if

f(x₁)=f(x₂) ---> x₁=x₂

The Attempt at a Solution

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

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

 

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

 

[Mark44]

Homework Statement

That's what I'm supposed to prove.

Homework Equations

A function f is an injection if

f(x₁)=f(x₂) ---> x₁=x₂

The Attempt at a Solution

I'm just having trouble constructing a formal proof. I mean, it's obvious that f(g(x₁))=f(g(x₂)) then either g(x₁)=g(x₂) or g(x₁)≠g(x₂),

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

and since g(x₁)≠g(x₂) implies x₁≠x₂, ...

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

 

[Jamin2112]

Nevermind. I was thinking to hard about this.

Proof.

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

h(x₁)=h(x₂) \Rightarrow f(g(x₁))=f(g(x₂)) \Rightarrow g(x₁)=g(x₂) (since f is an injection) \Rightarrow x₁=x₂ (since g is an injection)

 

[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\rightarrowB and g:C\rightarrowD be surjections.

( \forall b\inB ) ( \exists a\inA ) ( f(a)=b )

( \forall d\inD ) ( \exists c\inC ) ( f(c)=d )

Let h=f(g(x)).

...

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

 

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

 

[Jamin2112]

Same as before with the injection, f:A->B and g:C->A

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

 

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

 

[Jamin2112]

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.

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.

 

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

 

[Jamin2112]

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.

I'm with you.

 

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