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)
Best Answer
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$.