1
$\begingroup$

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)

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Manx Jun 8 at 7:27
  • 1
    $\begingroup$ 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). $\endgroup$ – Aniruddha Deshmukh Jun 8 at 9:03
  • $\begingroup$ @ 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? $\endgroup$ – Manx Jun 8 at 10:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.