Master of Science in Mathematics

Lecture Notes. Accessed on: 2019-10-21 18:28:18

## Composition

** Theorem**. Let $f:X\to Y$ be a function. If $g:Y\to Z$ and $g\circ f$ is injective, then $f$ is injective.

** Proof**. Let $x_1, x_2\in X$. Then $$ f(x_1)=f(x_2) \Longrightarrow (g\circ f)(x_1)=(g\circ f)(x_2) \Longrightarrow x_1=x_2 $$ shows that $f$ is injective.

** Theorem**. Let $f:X\to Y$ be a function. If $g:Y\to Z$ and $g\circ f$ is surjective, then $g$ is surjective.

** Proof**. Let $z\in Z$. Then there exists $x\in X$ such that $(g\circ f)(x)=z$. Thus it follows $g(f(x))=z$ shows, for all $z\in Z$ there exists $y$ (namely $y=f(x)$) such that $g(y)=z$ and so $g$ is surjective.

** Theorem**. Let $f:X\to Y$ be a function. If $f$ is injective and $g:Y\to Z$ is injective, then $g\circ f$ is injective.

** Proof**. Let $x_1, x_2\in X$. Then $$ (g\circ f)(x_1)=(g\circ f)(x_2) \Longrightarrow f(x_1)=f(x_2) \Longrightarrow x_1= x_2 $$ shows that $g\circ f$ is injective.

** Theorem**. Let $f:X\to Y$ be a function. If $f$ is surjective and $g:Y\to Z$ is surjective, then $g\circ f$ is surjective.

** Proof**. Let $z\in Z$. Since $g$ is surjective there exists $y\in Y$ such that $g(y)=z$. Since $f$ is surjective there exists $x\in X$ such that $f(x)=y$. Thus $(g\circ f)(x)=z$ and so $g\circ f$ is surjective.

** Theorem**. Let $f:X\to Y$ be a function. Then $f$ is injective if and only if given any functions $g,h:Y\to X$, if $f\circ g=f\circ h$, then $g=h$.

** Proof**. Assume $f$ is injective. Let $g,h:Y\to X$ and assume $f\circ g= f\circ h$. Let $y\in Y$. Then $(f\circ g)(y)=(f\circ h)(y)$. Since $f$ is injective it follows $g(y)=h(y)$ for all $y\in Y$. Conversely, assume $g,h:Y\to X$, $f\circ g=f\circ h \implies g=h$ holds. Let $x_1, x_2\in X$ and assume $x_1\neq x_2$. Assume, for a contradiction, $f(x_1)=f(x_2)$. Let $g:Y\to X$ be defined by $g(y)=x_1$ for all $y\in Y$. Let $h:Y\to X$ be defined by $h(y)=x_2$ for all $y\in Y$. Notice $$ (f\circ g)(y)=f(g(y))=f(x_1)=f(x_2)=(f\circ h)(y) $$ for all $y\in Y$. Thus, $f\circ g=f\circ h$, yet $g\neq h$ since $g(y)=x_1\neq x_2=h(y)$. Therefore, $f(x_1)\neq f(x_2)$ and so $f$ is injective.

** Theorem**. Let $f:X\to Y$ be a function. Then $f$ is surjective if and only if given any functions $g,h:Y\to X$, if $g\circ f=h\circ f$, then $g=h.$

** Proof**. Assume $f$ is surjective and let $g:Y\to Z$ and $h:Y\to Z$ be functions such that $g\circ f=h\circ f$. Let $y\in Y$. Since $f$ is surjective, there exists $x\in X$ such that $y=f(x)$. Then $$g(y) =g(f(X)) =h(f(x)) =h(y)$$ as needed to show $g=h$. Conversely, and for contrapositive, suppose $f$ is not surjective. Then there exists $y_1\in Y$ such that $y_1=f(x)$ does not hold for all $x\in X$. Let $Z=\{a,b\}$ and let $g$ and $h$ be defined by $g(y)=a$ for all $a\in Y$ and $$h(y)=\begin{cases} a & \text{ if } y\neq y_1 \\ b & \text{ if } y=y_1. \end{cases} $$ Then we have $g\neq h$ such that $g\circ f=h\circ f$. Thus $f$ is not right cancelable.

** Theorem**. Let $f:X\to Y$ be a function. Then $f$ is injective if and only if there exists a function $g:Y\to X$ with $g\circ f=I_X$ ($f$ has a left inverse).

** Proof**. Assume $X\neq \emptyset$ and also assume $f:X\to Y$ is injective. Let $y\in Y$. Either $y\in f(X)$ or $y\notin f(X)$. Define $g:Y\to X$ as follows \begin{equation} g(y)= \begin{cases} x & y\in f(X) \text{ and } f(x)=y \\ x_0 & y \notin f(X) \end{cases} \end{equation} where $x_0$ is a fixed element of $X\neq \emptyset$. Then $g$ is defined for all $y\in Y$. If $y’\in Y$ with $x_1=g(y’)\neq g(y’)=x_2$, then $y’=f(x_1)\neq f(x_2)=y’$, since $f$ is injective. Thus $f$ is injective implies $g$ is a function. If $x\in X$, then $$(g\circ f)(x)=g(f(x))=g(y)=x, \qquad \text{ for some $y\in f(X)$} $$ which shows $g\circ f=I_X$. Conversely, assume $f:X\to Y$ and there exists $g:Y\to X$ such that $g\circ f=I_X$. Let $x_1,x_2\in X$ and assume $f(x_1)=f(x_2)$. Then $$x_1=(g\circ f)(x_1)=g(f(x_1))=g(f(x_2))=(g\circ f)(x_2)=x_2 $$ which shows $f$ is injective.

** Theorem**. Let $f:X\to Y$ be a function. Then $f$ is surjective if and only if there exists a function $h:Y\to X$ with $f\circ h=I_Y$ ($f$ has a right inverse).

** Proof**. Assume there exist $h:Y\to X$ with $f \circ h=I_Y$. Let $b\in Y$. Then $$b=(f\circ h)(b)=f(h(b))=f(a)$$ where $a\in X$, shows $f$ is surjective. Conversely, follows using the Axiom of Choice. Suppose $f$ is surjective. Then $f^{-1}(b)\subseteq X$ is a nonempty set for every $b\in Y$. For each $b\in Y$ choose $a_b\in f^{-1}(b)$. Then the map $h:Y\to X$ defined by $h(b)=a_b$ is such that $f\circ h=I_Y$ since $(f\circ h)(y)=f(h(y))=f(a_y)=y$.

## Inverse Functions

If the inverse relation $f^{-1}$ is also a function, then we say $f$ is an ** invertible function**, or just

**.**

*invertible*** Theorem**. A function $f:X\to Y$ is invertible if and only if it is injective. If $f$ is invertible then $f^{-1}$ is also invertible and $(f^{-1})^{-1}=f$.

** Proof**. Let $f$ be invertible, then $f^{-1}$ is a function. It follows that $f^{-1}(f(x))=x$ for all $x\in X$. If $a=f^{-1}(y_1)$ and $a=f^{-1}(y_2)$ we have $y_1 = f(a)$ and $y_2 =f(a)$. So $f$ is injective. Let $f$ be injective. If $af^{-1}y_1$ and $af^{-1}y_2$ we have $y_1 f(a$ and $y_2 fa$. Therefore, $y_1=y_2$ and we have proven that $f^{-1}$ is a function. We know that $(f^{-1})^{-1}=f$ by previous theorem and so $f^{-1}$ is also invertible.

** Definition**. Let $X$ and $Y$ be sets. A function $f$ is called

**, if $f$ is both injective and surjective.**

*bijective*** Theorem**. Let $f:X\to Y$ be a function. Then $f$ is bijective if and only if there exists a unique function $f’:Y\to X$ such that both $f’\circ f=I_X$ and $ f \circ f’ = I_Y$.

** Proof**. If $f$ is bijective, then $f$ is injective and surjective; and thus there exists functions $g$ and $h$ such that $g\circ f=I_X$ and $ f \circ h = I_Y$. Notice $$ g=g \circ I_Y=g \circ (f \circ h)=(g\circ f)\circ h=I_X\circ h=h $$ showing $f’:=g=h$ as needed. Conversely, follows from the statements above.

** Theorem**. Let $f:X\to Y$ be a function. If $f$ and $g:Y\to Z$ are bijections, then $g\circ f$ is a bijection and $$ (g\circ f)^{-1}=f^{-1}\circ g^{-1}. $$

** Proof**. If $f$ and $f$ are bijections, then $g\circ f$ is a bijection and $(g\circ f)^{-1}=f^{-1}\circ g^{-1}$. Therefore, the inverse of a function $f:X\to Y$ is a function $f^{-1}:Y\to X$ if and only if $f$ is a bijection. Since $f$ and $g$ are bijections, $f^{-1}:Y\to X$ and $g^{-1}:Z\to Y$ are functions. Hence, $f^{-1}\circ g^{-1}:Z\to X$ is a function. It follows that, $g\circ f$ is injective and surjective, and so a bijection. Thus $(g\circ f)^{-1}:Z\to X$ is also a function. Let $z\in Z$. Since $f$ and $g$ are surjections there exists $x\in X$ and $y\in Y$ such that \begin{equation} \label{surjcomp} g(y)=z \qquad \text{and} \qquad f(x)=y, \end{equation} respectively. Written in inverse function notation, $y=g^{-1}(z)$ and $x=f^{-1}(y)$. By substitution, $x=f^{-1}(g^{-1}(z))=(f^{-1}\circ g^{-1})(z)$. Notice it also follows from \eqref{surjcomp} that $$(g\circ f)(x)=g(f(x))=g(y)=z.$$ Written in inverse function notation we obtain $(g\circ f)^{-1}(z)=x$.