Derivate that a function is injective

Printable View

March 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

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

$g(a) = a, g(b) = b, g(c) = c, g(d) = c$
$f(a) = 1, f(b) = 2, f(c) = 3, f(d) = 4$
$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?
March 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

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

$g(a) = a, g(b) = b, g(c) = c, g(d) = c$
$f(a) = 1, f(b) = 2, f(c) = 3, f(d) = 4$
$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,

$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 $f\circ g$ is 1-1 then also $g$ is 1-1 , and

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

Try to prove the above.

Tonio
March 7th 2011, 10:51 AM
posix_memalign

Quote:

Originally Posted by tonio

No, it's not: as you showed,

$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 $f\circ g$ is 1-1 then also $g$ is 1-1 , and

if $f\circ g$ is onto then also $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. $g(a) = g(b) \Longrightarrow a \neq b$ and also assume that f and f o g are injective.
Then we would have $f(g(a)) = c = f(g(b))$ , where $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? :-)
March 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. $g(a) = g(b) \Longrightarrow a \neq b$ and also assume that f and f o g are injective.
Then we would have $f(g(a)) = c = f(g(b))$ , where $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
March 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. $g(a) = g(b) \Longrightarrow a \neq b$

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