# Injective and surjective proofs

If following is true, give a proof. If it is false, give a counterexample.

(a)If $$f$$ and $$g$$ are injective, then $$g\circ f$$ is injective

(b) if $$g\circ f$$ is surjective then then $$g$$ is surjective

Question:

I think both are true for specific case that $$f:A\rightarrow{B},g:B\rightarrow{C}$$,

but this only include functions s.t. co-domain(f) = domain(g),

I'm not sure for more general cases $$f:A\rightarrow{R},g:B\rightarrow{R}$$

what I get so far:

a)Proof.(for general cases)

let $$f:A\rightarrow{R},g:B\rightarrow{R},f \circ g:C\rightarrow{R}$$

(s.t. A is the domain that f is defined on

and B is the domain that g is defined on)

Assume f and g are injective

Show $$g\circ f$$ is injective

By assumption

Have $$\forall x_1,x_2\in A,x_1\neq x_2\rightarrow{f(x_1)\neq f(x_2)}$$

and $$\forall x_3,x_4\in B,x_3\neq x_4\rightarrow{g(x_3)\neq g(x_4)}$$

We want to show that:

$$\forall x_5,x_6\in C,x_5\neq x_6\rightarrow{g(f(x_5))\neq g(f(x_6))}$$

...(but I don't know how to prove)

b)Proof.

let $$f:A\rightarrow{R},g:B\rightarrow{R},f \circ g:C\rightarrow{R}$$

Assume $$\forall y \in R, \exists x_1\in C, g(f(x_1))=y$$

Show $$\forall y \in R, \exists x_2 \in B, g(x_2)=y$$

...

Definitions I'm using:

$$f:A\rightarrow{B}$$:

$$f$$:domain $$\rightarrow$$ co-domain

domain:

Subset of R that f is defined on

(for example, domain of $$\frac{1}{x}$$ is R without $$0$$)

co-domain:

R as default

range:

Outputs of f as a subset in co-domain

injective:

Let $$f:A\rightarrow{B}$$

f is injective iff $$\forall x_1,x_2\in A,x_1\neq x_2\rightarrow{f(x_1)\neq f(x_2)}$$

surjective:

Let $$f:A\rightarrow{B}$$

f is surjective iff $$\forall y \in B,\exists x\in A,f(x)=y$$

(In another word:Its range is same as its co-domain)

First, the composition is only possible when the codomain of $$f$$ is a subset of the domain of $$g$$. This means that $$f: A \rightarrow D$$ and $$g: B \rightarrow C$$ with $$D\subseteq B$$.
Now, to prove part (a), use the definition of injective; $$f$$ is injective if $$f \left( x_1 \right) = f \left( x_2 \right) \Rightarrow x_1 = x_2$$.
To use it, assume $$\left( g \circ f \right) \left( x_1 \right) = \left( g \circ f \right) \left( x_2 \right)$$. This means that $$g \left( f \left( x_1 \right) \right) = g \left( f \left( x_2 \right) \right)$$. Since $$g$$ is injective this implies $$f \left( x_1 \right) = f \left( x_2 \right)$$ and $$f$$ being injective further implies $$x_1 = x_2$$. Hence, $$g \circ f$$ is injective.
For the second part, if you take any element $$c \in C$$, then the surjectivity of $$g \circ f$$ implies the existence of $$a \in A$$ such that $$\left( g \circ f \right) \left( a \right) = g \left( f \left( a \right) \right)=c$$. Since the codomain of $$f$$ is the same as domain of $$g$$ (so that the composition is possible), $$f \left( a \right) = b \in B$$. Hence, $$\forall c \in C$$, $$\exists b \in B$$ such that $$g \left( b \right) = c$$. In particular, this $$b$$ is given by $$f \left( a \right)$$, where $$\left( g \circ f \right) \left( a \right) = c$$.
• Thanks for your responding, I know how to prove for case $f: A \rightarrow B$ and $g: B \rightarrow C$, can you explain why "the composition is only possible when the codomain of f is the domain of g". If it's by definition, It would be also fine if you can list the reference about this. – Manx Jun 8 at 7:27
• Well, for composition of two functions, say in this case $g \circ f$, the value of the composition at any point $x$ in its domain is the value of $g$ at the point $f \left( x \right)$ in its domain. To make meaning of $f \left( x \right)$, we need to make the domains of $f$ and $g \circ f$ same. To make meaning of value of $g$ at $f \left( x \right)$, we need to have $f \left( x \right)$ in the domain of $g$, i.e., codomain of $f$ and domain of $g$ must be the same (or codomain of $f$ can be subset of domain of $g$, which still reduces to our case). – Aniruddha Deshmukh Jun 8 at 9:03
• @ Aniruddha Deshmukh also domain of $g \circ f$ need to be a subset of domain of $f$ in general, that not necessary be the same? – Manx Jun 8 at 10:32