# Derivate that a function is injective

• Mar 6th 2011, 04:51 PM
posix_memalign
Derivate that a function is injective
If we have that f and f o g (that is, f(g) ) are both injective, must then g be injective?

I find that this is false and I show it with an example, where I have

\$\displaystyle A = \{a,b,c,d\}, B=\{a,b,c,d\}, C=\{1,2,3,4\}\$
\$\displaystyle g: A \Longrightarrow B, f: B \Longrightarrow C, f o g: A \Longrightarrow C\$

\$\displaystyle g(a) = a, g(b) = b, g(c) = c, g(d) = c\$
\$\displaystyle f(a) = 1, f(b) = 2, f(c) = 3, f(d) = 4\$
\$\displaystyle f(g(a)) = 1, f(g(b)) = 2, f(g(c)) = 3, f(g(d)) = 3\$

Here I have that f and f o g are injective but g is not, hence g does not have to be injective.

Is this a correct way to show this at all?
• Mar 6th 2011, 06:02 PM
tonio
Quote:

Originally Posted by posix_memalign
If we have that f and f o g (that is, f(g) ) are both injective, must then g be injective?

I find that this is false and I show it with an example, where I have

\$\displaystyle A = \{a,b,c,d\}, B=\{a,b,c,d\}, C=\{1,2,3,4\}\$
\$\displaystyle g: A \Longrightarrow B, f: B \Longrightarrow C, f o g: A \Longrightarrow C\$

\$\displaystyle g(a) = a, g(b) = b, g(c) = c, g(d) = c\$
\$\displaystyle f(a) = 1, f(b) = 2, f(c) = 3, f(d) = 4\$
\$\displaystyle f(g(a)) = 1, f(g(b)) = 2, f(g(c)) = 3, f(g(d)) = 3\$

Here I have that f and f o g are injective but g is not, hence g does not have to be injective.

Is this a correct way to show this at all?

No, it's not: as you showed,

\$\displaystyle f\circ g(c)=f(g(c))=3=f(g(d))=f\circ g(d) \,,\,\,and\,\,c\neq d\Longrightarrow f\circ g\$ is not 1-1.

In fact, it is easy to show that

if \$\displaystyle f\circ g\$ is 1-1 then also \$\displaystyle g\$ is 1-1 , and

if \$\displaystyle f\circ g\$ is onto then also \$\displaystyle f\$ is.

Try to prove the above.

Tonio
• Mar 7th 2011, 10:51 AM
posix_memalign
Quote:

Originally Posted by tonio
No, it's not: as you showed,

\$\displaystyle f\circ g(c)=f(g(c))=3=f(g(d))=f\circ g(d) \,,\,\,and\,\,c\neq d\Longrightarrow f\circ g\$ is not 1-1.

In fact, it is easy to show that

if \$\displaystyle f\circ g\$ is 1-1 then also \$\displaystyle g\$ is 1-1 , and

if \$\displaystyle f\circ g\$ is onto then also \$\displaystyle f\$ is.

Try to prove the above.

Tonio

I see now that I was wrong, thank you.

I try again, I have that f and f o g are injective, it follows then that g is injective:

I show this with a contradiction, assume that there exists elements s.t. \$\displaystyle g(a) = g(b) \Longrightarrow a \neq b\$ and also assume that f and f o g are injective.
Then we would have \$\displaystyle f(g(a)) = c = f(g(b))\$, where \$\displaystyle a \neq b\$
This implies that f o g is not injective, which is a contradiction as it was assumed as a premise it was injective, hence g must be injective.

Am I getting closer? :-)
• Mar 7th 2011, 02:19 PM
tonio
Quote:

Originally Posted by posix_memalign
I see now that I was wrong, thank you.

I try again, I have that f and f o g are injective, it follows then that g is injective:

I show this with a contradiction, assume that there exists elements s.t. \$\displaystyle g(a) = g(b) \Longrightarrow a \neq b\$ and also assume that f and f o g are injective.
Then we would have \$\displaystyle f(g(a)) = c = f(g(b))\$, where \$\displaystyle a \neq b\$
This implies that f o g is not injective, which is a contradiction as it was assumed as a premise it was injective, hence g must be injective.

Am I getting closer? :-)

Yes, that was correct.

Tonio
• Mar 7th 2011, 03:26 PM
emakarov
A little correction.
Quote:

Originally Posted by posix_memalign
I show this with a contradiction, assume that there exists elements s.t. \$\displaystyle g(a) = g(b) \Longrightarrow a \neq b\$

It should say, "g(a) = g(b) and \$\displaystyle a\ne b\$".