Exercise 3.3.2 (Composition preserves injectivity/surjectivity)

Question

Let $f : X\rightarrow Y$ and $g : Y\rightarrow Z$ be functions. Show that if $f$ and $g$ are both injective, then so is $g\circ f$; similarly, show that if $f$ and $g$ are both surjective, then so is $g\circ f$.

Il-Young Son · Accepted Answer

\subsubsection{Injection}
Let $x, x'\in X$ and $y, y'\in Y$ such that $x
eq x'$ and $f(x) =y$ and $f(x')=y'$.  Since $f$ is injective,  $y
eq y'$ and since $g$ is injective $g(y)
eq g(y')$.  Therefore $(g\circ f)(x)
eq (g\circ f)(x')$ and so $g\circ f : Xightarrow Z$ is injective.

\subsubsection{Surjection}
Suppose $g\circ f$ is not surjective.  Then there exists some $z\in Z$ such that $z
otin (g\circ f)(X)$.  Since $g$ is surjective, there is some $y\in Y$ for which $g(y)=z$.  And similarly, since $f$ is surjective, there is some $x\in X$ such that $f(x)=y$. This implies $(g\circ f)(x) = z$ which contradicts the claim that $z
otin (g\circ f)(X)$.

Khagan Gulusoy · Answer

\begin{proof} \begin{enumerate} \item ($g\circ f$ is injective) By Definition 3.3.14, to show that $g\circ f$ is injective, we have to demonstrate that $g\circ f(x_1) eq g\circ f(x_2)$ for any $x_1 eq x_2$. Since $g$ and $f$ are both injective, we have $f(x_1) eq f(x_2)$ for all $x_1 eq x_2$. Therefore, we have $g(f(x_1)) eq g(f(x_2)),$ and thus, $g\circ f(x_1) eq g\circ f(x_2)$ for any $x_1$ and $x_2.$ Thus, we can conclude that $g\circ f$ is injective. \item ($g\circ f$ is surjective) Since $f:X ightarrow Y$ and $g:Y ightarrow Z,$ we have $g\circ f:X ightarrow Z.$ By Definition 3.3.17, we have to show that for every $z\in Z$ there exists $x\in X$ such that $(g\circ f)(x)=z.$ \begin{figure}[H] \centering \begin{tikzpicture}[ele/.style={fill=black,circle,minimum width=.8pt,inner sep=1pt}, ele2/.style={fill=red,circle,minimum width=1.6pt,inner sep=1pt}, every fit/.style={ellipse,draw,inner sep=-2pt}] % Set X ode[ele] (x0) at (0,5) {}; ode[ele] (x1) at (0,4) {}; ode[ele2,label=left:$x$] (x2) at (0,3) {}; ode[ele2,label=left:$x^{\prime}$] (x3) at (0,2) {}; ode[ele] (x4) at (0,1) {}; ode[ele] (x5) at (0,0) {}; ode[draw,fit= (x0) (x1) (x2) (x3) (x4) (x5) ,minimum width=2cm, label=below:$X$] {} ; % Ellipse X % Set Y ode[ele] (y1) at (4,4) {}; ode[ele2,label=above:$y$] (y2) at (4,3) {}; ode[ele] (y3) at (4,2) {}; ode[ele] (y4) at (4,1) {}; ode[draw,fit= (y1) (y2) (y3) (y4),minimum width=2cm, label=below:$Y$] {} ; % Ellipse Y % Set Z ode[ele] (z1) at (8,4) {}; ode[ele2,label=right:$z$] (z2) at (8,3) {}; ode[ele] (z3) at (8,2) {}; % ode[ele] (z4) at (8,1) {}; ode[draw,fit= (z1) (z2) (z3),minimum width=2cm, label=below:$Z$] {} ; % Ellipse % Arrows f:X->Y and g:Y->Z \draw[->,thick,shorten <=2pt,shorten >=2pt] (x0) -- (y1); \draw[->,thick,shorten <=2pt,shorten >=2pt] (x1) -- (y1); \draw[->,red,thick,shorten <=2pt,shorten >=2] (x2) -- (y2); \draw[->,red,thick,shorten <=2pt,shorten >=2] (x3) -- (y2); \draw[->,thick,shorten <=2pt,shorten >=2] (x4) -- (y3); \draw[->,thick,shorten <=2pt,shorten >=2] (x5) -- (y4); \draw[->,thick,shorten <=2pt,shorten >=2] (y1) -- (z1); \draw[->,red,thick,shorten <=2pt,shorten >=2] (y2) -- (z2); \draw[->,thick,shorten <=2pt,shorten >=2] (y3) -- (z3); \draw[->,thick,shorten <=2pt,shorten >=2] (y4) -- (z3); %\draw[->,thick,shorten <=2pt,shorten >=2] (y2) -- (z4); \end{tikzpicture} \caption{The idea of the proof is to fix $z$ and then go to the previous set since surjectivity guarantees that we can always go backwards at any point in the range.} \end{figure} Let $z \in Z$ be arbitrary. Since $g$ is surjective we have $y\in Y$ such that $g(y) = z.$ Since $f$ is surjective, for that particular $y$ we have $x\in X$ such that $f(x)=y.$ In other words, we have found a $x\in X$ such that $g(f(x)) = g(y) = z$, as desired. %Since $g$ is surjective, we have: there exists $f(x)$ such that $g(f(x)) = z.$ Since $f$ is also surjective, we have: for every $y\in Y$ there exists $x\in X$ such that $f(x)=y.$ Thus, we have: there exists $x\in X$ such that $g(f(x)) = z,$ as desired. \end{enumerate} \end{proof}

Exercise 3.3.2 (Composition preserves injectivity/surjectivity)

Answers

0.0.1 Injection

0.0.2 Surjection

Comments

Comments

Exercise 3.3.2 (Composition preserves injectivity/surjectivity)

Answers

0.0.1 Injection

0.0.2 Surjection

Comments

Comments

Add answer