# Composition of functions

• Apr 10th 2011, 02:53 PM
siracide
Composition of functions
Hello, I have trouble proving that "if f o g is injective, then f is injective."
Let g be a function from X to Y and let f be a function from Y to Z.

My attempt to solving it is by contradiction:

Assume that f is not injective, that is, there exists a z that belongs to Z for each y that belongs to set Y such that f(y) != z.

There exist y1,y2 belong to Y, y1!=y2, such that f(y1)=f(y2).

By definition of injection, y1=g(x1) and y2=g(x2) for some x1, x2 that belong to X,
but x1!=x2 since g(x1)!=g(x2).

Since f(y1)=f(y2), we have f(g(x1))=f(g(x2)), so (fog)(x1)=(fog)(x2), which is a contradiction.

Therefore f is injective

Am I in the correct way?

P.S. I apologize if my symbology is hard to read. I am new to the forum and I am not familiar with the text format.
• Apr 10th 2011, 03:16 PM
Plato
Quote:

Originally Posted by siracide
Hello, I have trouble proving that "if f o g is injective, then f is injective."
Let g be a function from X to Y and let f be a function from Y to Z.

Let \$\displaystyle X=\{1,2,3\},~Y=\{a,b,c,d\},~Z=\{p,q,r\}\$.

Then let \$\displaystyle g=\{(1,a),(2,b),(3,c)\}~\&~f=\{(a,p),(b,q),(c,r),( d,r)\}\$

Is \$\displaystyle f\$ injective? Is \$\displaystyle f\circ g\$ injective?
• Apr 10th 2011, 03:51 PM
siracide
Oh I see, in the example you give f is not injective since there are two values of Y that correspond to Z. However, f o g is injective. I think it is easier to explain a proof with examples like yours,I do not know if this is the formal process, though. Can I restate my proof like this?

Assume that f is not injective, that is, there exists a z that belongs to Z for each y that belongs to set Y such that f(y) != z.

There exist y1,y2 belong to Y, y1!=y2, such that f(y1)!=z and f(y2)!=.

By definition of injection, y1=g(x1) and y2=g(x2) for some x1, x2 that belong to X.
For f o g to be injective we have f(g(x1))=f(g(x2)), whcih means f(x1)=z and f(x2)=z.

Therefore f(y1) != f(x1).

Then, it is not necessary for f to be injective when f o g is injective.
• Apr 11th 2011, 03:17 AM
emakarov

Quote:

Assume that f is not injective, that is, there exists a z that belongs to Z for each y that belongs to set Y such that f(y) != z.
This is the definition of surjective, not injective, function.

Quote:

There exist y1,y2 belong to Y, y1!=y2, such that f(y1)!=z and f(y2)!=.
Only when Y has more than one element.

Quote:

By definition of injection, y1=g(x1) and y2=g(x2) for some x1, x2 that belong to X.
Again, you confuse injection and surjection.

Quote:

For f o g to be injective we have f(g(x1))=f(g(x2))
I don't see why this is necessary.

Quote:

whcih means f(x1)=z and f(x2)=z.
The function f cannot be applied to x1 because x1 is in X, but f : Y -> Z.

Quote:

Then, it is not necessary for f to be injective when f o g is injective.
This fact does not need a general proof. Plato proved it by providing one counterexample.
• Apr 11th 2011, 04:30 AM
Plato
Quote:

Originally Posted by siracide
Oh I see, in the example you give f is not injective since there are two values of Y that correspond to Z. However, f o g is injective. I think it is easier to explain a proof with examples like yours,I do not know if this is the formal process, though. Can I restate my proof like this?

There is absolutely no reason to do that.
In mathematics true statements are proven.
False statements are shown to be false by example.

In this particular question you are asked to prove something.
However, the statement is false.
Therefore you must simply give an example that shows it is false.
• Apr 11th 2011, 10:37 AM
Deveno
in general, if you have a mathematical statement like: If P, then Q, and you wish to prove it is true, you need to show: WHENEVER P, then ALWAYS Q.

if the statement is not true, you only need to show FOR ONE P, NOT Q, you don't need to "disprove all cases".