[Notes](#fn1): Problem Class, 13 Oct 2020

# [Notes](#fn1): Problem Class, 13 Oct 2020 > Group 11 -- Problem Class, MATH40001/40009 IUM > Stergios M. Antonakoudis (stergios@imperial.ac.uk) Welcome to IUM Problem Class Group 11. \ Today's class: **Problem Sheet 3 of Part I.** [^1]: *These notes[^1] are typed up and created during and for the purposes of the discussion in the online session of Problem Class Group 11 for IUM on MS Teams, similarly to the use of a 'whiteboard' in an actual class.* --- ## A brief overview: ==functions== > $X \;\text{and} \; Y$ denote sets; $f$ denotes a function. * $\;f\!:X \rightarrow Y \;$ is a function -- it is a function *from* $X$ *to* $Y$. * $X$ is the domain of $f\;\;$and$\;\;Y$ is the co-domain of $f$. * The image or range of $f$ is the subset of $Y$ given by -- *the values of $f$* -- $\{\;y\in Y : \exists \;x \in X,\; y=f(x) \;\}$ and it is often denoted by $f(X)$, $\text{Im}(f)$ or $\text{Image}(f)$. * A function can be injective, surjective, *or both* -- bijective. --- ## Questions #### Clarify: $f: X \rightarrow Y$ is a bijection $\iff$ it has a two-sided inverse $g: Y \rightarrow X$. #### Solution/Proof In one direction ($\Leftarrow$), let $g$ be a two-sided inverse of $f$, so $\forall x \in X \; g(f(x))=x \;$ and $\forall y \in Y\;f(g(y))=y$. $f$ is injective: If $f(x_1)=f(x_2)$, then $g(f(x_1))=g(f(x_2))$; hence, $x_1=x_2$ (by the first of the two propositions for $g\circ f$). $f$ is surjective: If $y \in Y$, then $f(g(y))=y$ (by the second of the propositions for $f\circ g$); hence, $x=g(y) \in X$ implies $f(x)=y$. **QED** (for $\Leftarrow$) In the other directions ($\Rightarrow$), let $f$ be a bijection between $X$ and $Y$. GOAL: Construct $g: Y \rightarrow X$ that is a two-sided inverse of $f$. Given any $y \in Y$, we will firstly show that we can *==uniquely==* specify $x \in X$ with $f(x)=y$, and *define* $g(y)=x$ with ==$f(g(y)) =y$==. We know $f$ is surjective; hence there is (!) an $x \in X$ with $f(x)=y$. We know $f$ is injective; hence for all $x' \in X$ with $x' \neq x$, we have $f(x') \neq f(x)$ --- *by definition of what it means for $f$ to be injective*. In other words, there is at most one element $x \in X$ with $g(y)=x$ (!). Hence, we have defined $g: Y \rightarrow X$, with $\forall y\in Y, \;f\circ g(y)=y$. To complete the proof we need to show that $g$ is *indeed* a two-sided inverse of $f$ i.e. $\forall x \in X,\; g(f(x))=x$ and $\forall y \in Y,\; f(g(y))=y$. Let $x \in X$. The values of $x\in X$ and $g(f(x))\in X$ under the function $f: X \rightarrow Y$ are $f(x) \in Y$ and $f(g(f(x))) \in Y$, respectively. We can re-write the latter, using that composition of functions is associative (*from lecture notes*) as follows $f(g(f(x)))=f\circ g (f(x))= f(x)$. -- where the last equality is *by construction/definition* of the function $g$. In other words, we have $f(g(f(x)))=f(x)$ and, using that the function $f$ is injective, we conclude $g(f(x))=x$. Hence, $g= f^{-1}$. **QED** (for $\Rightarrow$) --- ## Problems to discuss: ==1, 2, 3, 4, 5== --- ### ==Problem 1== Say $X,Y$ and $Z$ are sets, and $f:X\rightarrow Y$ and $g:Y\rightarrow Z$ are functions. In the course notes we proved that if $f$ and $g$ are injective, then $g\circ f$ is also injective, and that if $f$ and $g$ are surjective, then $g\circ f$ is surjective. But what about the other way? 1. If $g\circ f$ is injective, then is $f$ injective? Give a proof or a counterexample. 2. If $g\circ f$ is injective, then is $g$ injective? Give a proof or a counterexample. 3. If $g\circ f$ is surjective, then is $f$ surjective? Give a proof or counterexample. 4. If $g\circ f$ is surjective, then is $g$ surjective? Give a proof or counterexample. ### ==Solution== --- ### ==Problem 2== For each of the following functions, decide whether or not they are injective, surjective, bijective. *Proofs required!* 1. $f: \mathbb{R} \rightarrow \mathbb{R}$, $f(x) = \frac{1}{x}$ if $x\neq 0$ and $f(0) = 0$. 2. $f: \mathbb{R} \rightarrow \mathbb{R}$, $f(x) = 2x+ 1$. 3. $f: \mathbb{Z} \rightarrow \mathbb{Z}$, $f(x) = 2x+ 1$. 4. $f: \mathbb{R} \rightarrow \mathbb{R}$ defined by $f(x) = 3−x$ if the Riemann hypothesis is true, and $f(x) = 2 +x$ if not. \[NB the Riemann Hypothesis is a hard unsolved problem in mathematics; nobody currently knows if it is true or false.\] 5. $f: \mathbb{Z} \rightarrow \mathbb{Z}$, $f(n) =n^3−2n^2+ 2n−1$. ### ==Solution== 4. If RH is true -- then $f(x)=3-x$; equivalently, $x = 3 - f(x)$. Let $g: \mathbb{R} \rightarrow \mathbb{R}$, given by $g(y) = 3 - y$, then $g$ is a two-sided inverse of $f$. Hence, $f$ is a bijection. If RH is not true -- then $f(x)= 2+ x$. Let $g:\mathbb{R} \rightarrow \mathbb{R}$, given by $g(y) = y -2$, then $g$ is a two sided inverse of $f$. Hence, $f$ is a bijection. We conclude that $f$ is a bijection. 5. $f$ is injective -- Let $n\in \mathbb{Z}$, consider the difference $f(n+1) -f(n) = \ldots >0$. Hence, $f$ is *strictly* increasing. Is $f$ surjective? **_NO_** Solution 1: $f(1)=0$ and $f(2)=3$. If $f(n)=2$, then n < 2 and 1 < n (since $f$ is strictly increasing); which is not possible for any integer values of $n$. Solution 2: Observe $n^3 -1 = (n-1)( n^2+n+1)$... --- ### ==Problem 3== For each of the following "*functions*", explain why I just lost a mark. 1. $f: \mathbb{R} \rightarrow \mathbb{R},\; f(x) = 1/x$. 2. $f: \mathbb{R} \rightarrow \mathbb{R},\; f(x) =\sqrt{x}$. 3. $f: \mathbb{Z} \rightarrow \mathbb{Z},\; f(n) = \frac{(n+1)^2}{2}$. 4. $f: \mathbb{R} \rightarrow \mathbb{R},\; f(x)\text{ is a solution to } y^3−y=x$. 5. $f: \mathbb{R}\setminus \{1\} \rightarrow \mathbb{R},\;f(x) = 1 +x+x^2+x^3+\cdots$. ### ==Solution== --- ### ==Problem 4== Prove that if $f:X\rightarrow Y$ is a function, and $g:Y\rightarrow X$ is a two-sided inverse of $f$, then $f$ is a two-sided inverse for $g$. Deduce that if $X$ and $Y$ are sets, and there exists a bijection from $X$ to $Y$, then there exists a bijection from $Y$ to $X$. ### ==Solution== --- ### ==Problem 5== Let $Z$ be a set. If $f:X\rightarrow Z$ and $g:Y\rightarrow Z$ are ==injective== functions, let’s say that $f$ is ==friends== with $g$ if ==there is a bijection $h:X\rightarrow Y$ such that $f=g\circ h$==. Prove that $f$ is friends with $g$ if and only if the range of $f$ equals the range of $g$. ### ==Solution== ($\Rightarrow$) Let $f$ be friends with $g$: $\exists$ bijection $h: X \rightarrow Y$ with $f = g\circ h$. GOAL: Prove that $f$ and $g$ have the same range $f(X)=g(Y)$. Let $z \in f(X)$, then there is $x \in X$ so that $z=f(x)$. Consider $h(x) \in Y$, then -- by definition of being *friends* -- we have that $f(x)=g(h(x))$; in other words, $z=g(h(x))$; hence, $z \in g(Y)$. I.e. we proved that $f(X) \subset g(Y)$. Recall: $h$ is a bijection $\iff$ it was a two-sided inverse $h^{-1}$. Post-composing $f= g \circ h$ with $h^{-1}$, we get $f \circ h^{-1} = (g \circ h ) \circ h^{-1} = g \circ (h \circ h^{-1}) = g$. In other words, $g = f \circ h^{-1}$, where $h^{-1}: Y \rightarrow X$ is a bijection. Hence, $g$ is also friends with $f$. Therefore, repeating the argument above by exchanging $f$ with $g$ and $h$ with $h^{-1}$, gives $g(Y) \subset f(X)$. QED ($\Rightarrow$) ($\Leftarrow$) Let $f$ and $g$ have the same range $f(X)=g(Y)$. GOAL: Construct a bijection $h: X \rightarrow Y$ with $f = g\circ h$.