1

Can i straight away claim that $\varphi : T \rightarrow X$ is injective, and if $f:X \rightarrow Y$ is injective, then this means $f \circ \varphi : T \rightarrow Y$ is injective for as well any set T base on the fact that the composition of two injective functions is injective?

Suppose $f \circ \varphi : a = f \circ \varphi : b$ Let $\varphi : a = c$ and $\varphi : b = d$ so $f(c) = f(d)$ Since $f:X \rightarrow Y$ is injective implies $f(c) = f(d)$ We know that $c = d$. This means that $f(c) = f(d)$ Since $\varphi : T \rightarrow X$ is injective implies $\varphi : a = \varphi : b$. We know that $a = b$. Therefore i have shown that $f \circ \varphi : a = f \circ \varphi : b$ then $a = b$.

Is my prove implies both direction? Meaning the composite function is injective if and only if $f:X \rightarrow Y$ is injective and $\varphi : T \rightarrow X$ is injective.

How do i show that $\psi \circ f : X \rightarrow T$ is injective if and only if $f:X \rightarrow Y$ is surjective for any set $T$?

J126
  • 17,451
Joe
  • 143

3 Answers3

1

Lemma: The composition of two injective functions is injective.

Proof: Let $ X, Y, Z $ be sets and $ f : X \rightarrow Y, g: Y \rightarrow Z $ be injective maps between them. Then $$ a = b \iff f(a) = f(b) ~\text{for all}~ a, b \in X $$

and $$ c = d \iff g(c) = g(d) ~\text{for all}~ c,d \in Y $$ in particular, as $ f(a), f(b) \in Y $, $$ f(a) = f(b) \iff g(f(a)) = g(f(b))$$ so that $$ a=b \iff f(a) = f(b) \iff g(f(a)) = g(f(b)), ~\text{for all}~ a,b \in X $$ which gives the definition of injectivity for $ g \circ f : X \rightarrow Z $.

As to the last part, what is $ \psi $?

0

The composition of two injective functions is certainly injective (Will's answer has a proof), and the composition of two surjective functions is also surjective. So, if the first function is injective, and the second is bijective when restricted to the image of the first function, their composition will be a bijection.

Dom
  • 1,378
  • What about the composition of a surjective function and an injective function? – Joe Sep 28 '14 at 15:52
  • As in a surjective function first? Then you may not have a bijection, as two elements of the domain could map to same thing. for example if $f:{0,1}\to{0},g:{0}\to{0}$ then $g\circ f$ is not bijective. – Dom Sep 28 '14 at 15:56
  • can i conlude that the composite function is surjective? – Joe Sep 28 '14 at 16:00
  • 1
    No, if you compose two functions, the second one must be surjective for the composition to be surjective (otherwise you can't hit the whole codomain). – Dom Sep 28 '14 at 16:11
0

To the first question: No, $f$ does not have to be injective,what you have is

If $f \circ \phi$ is injective then $\phi$ is injective.

To show this notice that $\phi(a)= \phi(b) \Rightarrow f(\phi(a)) = f(\phi(b)) \Rightarrow f\circ \phi(a)= f\circ \phi(b) \Rightarrow a=b $, because $f \circ \phi$ is injective. That means that $\phi$ is injective.

An example where $f$ is not injective is:

Take $X=\lbrace 1,2,3,4 \rbrace,Y=\lbrace 1,2,3,4 \rbrace\ \text{and}\ \ T=\lbrace 1,2 \rbrace$.Take $\phi$ to be the identity function and define $f(1) = 1, f(2) =2,f(3)=f(4)=3$. Then you have that $f \circ \phi$ is injective but $f$ is not.

To the second question:

As we have shown above, if $\psi \circ f$ is injective you have that $f$ is injective, if $f$ is also surjective then you garantee that $\psi$ is injective.

Aaron Maroja
  • 17,571