CIS375 Help Session Note 4 (Spring 2020)
29 Mar 2020Scire ad trascendere  Learn to transcend.
Topics covered:
 Functions
Please always pay attention to Blackboard announcements and your mailbox. Prof. Lee and I are trying different approaches to make sure this course can go on as usual. You do not want to miss major changes in course format or policies.
Concepts on textbook
Definition 24.1 (Function) A relation \(f\) is called a function provided \((a, b) \in f\) and \((a, c) \in f\) imply \(b=c\).
 Do not be scared away by the relational definition of functions. We usually write \(f(a) = b\), it is equivalent to \((a, b) \in f\).
 Using function notation, this definition says “if \(f(a)=b\) and \(f(a)=c\) then \(b=c\)”. This is essentially saying for a specific input, the output of a function has to be unique.
Definition 24.5 (Domain, image) Let \(f\) be a function. The set of all possible first elements of the ordered pairs in \(f\) is called the domain of \(f\) and is denoted by \(\operatorname{dom} f\). The set of all possible second elements of the ordered pairs in \(f\) is called the image of \(f\) and is denoted by \(\operatorname{im} f\). \(\newcommand{\fdom}{\operatorname{dom}}\newcommand{\fim}{\operatorname{im}}\) In setbuilder notation,

Since \(f\) is a relation, which is essentially a set, we can enumerate all of its elements like so: \(f = \{\ldots, (a_i, b_i), (a_{i+1}, b_{i+1}), (a_{i+2}, b_{i+2}), \ldots, (a_{j}, b_{j}), \ldots\}\)
Then we have:
Definition 24.8 (\(f: A \rightarrow B\)) Let \(f\) be a function and let \(A\) and \(B\) be sets. We say that \(f\) is a function from \(A\) to \(B\) provided \(\fdom f = A\) and \(\fim f \subseteq B\). In this case, we write \(f: A \rightarrow B\). We also say \(f\) is a mapping from \(A\) to \(B\).
 If we write \(f: A \rightarrow B\), it means \(\fdom f = A\), but it does not necessarily mean \(\fim f = B\)! In fact, \(B\) is a superset of \(\fim f\).
Proposition 24.10 Let \(A\) and \(B\) be finite sets with \(\lvert A \rvert = a\) and \(\lvert B \rvert = b\). The number of functions from \(A\) to \(B\) is \(b^a\).
 Suppose \(A = \{1, 2\}\), \(B = \{3, 4, 5\}\). We can let \(f(1)\) be either 3, 4 or 5, which are 3 possibilities. We can also let \(f(2)\) be either 3, 4, 5, which are another three possibilities. In general, for each element \(x \in A\), there are \(b\) ways to define \(f(x)\). Therefore, the number of functions from \(A\) to \(B\) is \(\underbrace{b \times b \times \cdots \times b}_{\mbox{repeat}~a~\mbox{times}} = b^a\).
Definition 24.13 (Onetoone) A function \(f\) is called onetoone provided that, whenever \((x, b), (y, b) \in f\), we must have \(x = y\). In other words, if \(x \neq y\), then \(f(x) \neq f(y)\).
Proposition 24.14 Let \(f\) be a function. The inverse relation \(f^{1}\) is a function if and only if \(f\) is onetoone.
Proposition 24.15 Let \(f\) be a function and suppose \(f^{1}\) is also a function. Then \(\fdom f = \fim f^{1}\) and \(\fim f = \fdom f^{1}\).
 The definition of function regulates that given an input \(x\), the output \(f(x)\) must be unique. Onetoone is a stronger condition, where given an output \(y\), there is a unique input \(x\) such that \(f(x) = y\).
 A function is invertible if and only if it is onetoone.
Proposition 24.18 (Onto) Let \(f : A \rightarrow B\). We say that \(f\) is onto \(B\) provided that for every \(b \in B\) there is an \(a \in A\) so that \(f(a) = b\). In other words, \(\fim f = B\).
 The notation \(f : A \rightarrow B\) only needs \(\fim f \subseteq B\). That is, it is possible for some elements in \(B\) that are not in \(\fim f\). If \(f\) is onto \(B\), then its image is equal to \(B\), which means for each element \(b \in B\), there must be some \(a \in A\) such that \(f(a) = b\).
Theorem 24.21 Let \(A\) and \(B\) be sets and let \(f : A \rightarrow B\). The inverse relation \(f^{1}\) is a function from \(B\) to \(A\) if and only if \(f\) is onetoone and onto \(B\).
(\(\Rightarrow\)) Suppose \(f^{1}\) is a function from \(B\) to \(A\).
 Because \(f^{1}\) is a function, \(f\) has to be onetoone.
 Because \(f^{1} : B \rightarrow A\), we know that \(\fdom f^{1} = B\), which indicates \(\fim f = B\). Therefore, \(f\) is onto \(B\).
(\(\Leftarrow\)) Suppose \(f\) is onetoone and onto \(B\).
 Because \(f\) is onetoone, the inverse realtion \(f^{1}\) is a function.
 Because \(f\) is onto \(B\), \(\fim f = \fdom f^{1} = B\). We know that \(\fim f^{1} = \fdom f = A\). Therefore, \(f^{1}\) is a function from \(B\) to \(A\).
Definition 24.22 (Bijection) Let \(f: A \rightarrow B\). We call \(f\) a bijection provided it is both onetoone and onto.
 Using mathematical expression, bijection can be written as follows:
 (onetoone) \((x, b) \in f \land (y, b) \in f \rightarrow x = y\)
 (onto) \(\fim f = B\), or \(\{b \mid \exists a, (a, b) \in f \} = B\).
Sample questions
 If \(f: A \rightarrow B\), \(\fdom f = A\)?
 If \(f: A \rightarrow B\), \(\fim f = B\)?
 When is \(f^{1}\) a function (when is \(f\) intervible)?
 If \(f: A \rightarrow B\) is onetoone, is \(f^{1}: B \rightarrow A\)?
 (✔) Yes, by definition.
 (✘) No, \(\fim f \subseteq B\).
 A function \(f\) is invertible if and only if it is onetoone. Keep in mind that \(f^{1}\) always exists as a relation, but is not necessarily a function.
 (✘) No. Despite the fact that Proposition 24.15 states “\(\fdom f = \fim f^{1}\) and \(\fim f = \fdom f^{1}\)”, the notation \(f: A \rightarrow B\) only requires \(\fim f \subseteq B\). Therefore, \(B\) is not necessarily the image of \(f\), which means it may not be the domain of \(f^{1}\).
 Is it a function? If not, explain why and stop. Otherwise, continue with the remaining questions.
 What are its domain and image?
 Is the function onetoone? If not, explain why and stop. Otherwise, answer the remaining question.
 What is its inverse function?
 It can be seen that \((1, 1) \in f\) and \((1, 1) \in f\). Because \(1 \neq 1\), it is not a function.
 Is it a function? If not, explain why and stop. Otherwise, continue with the remaining questions.
 What are its domain and image?
 Is the function onetoone? If not, explain why and stop. Otherwise, answer the remaining question.
 What is its inverse function?

If \((x, a) \in f\) and \((x, b) \in f\), we have \(x = a^2\) and \(x = b^2\). When \(c \geq 0\), \(\sqrt{c^2} = c\). Therefore, we have \(a = b = \sqrt{x}\), which indicates \(f\) is a function.

One of the ways to find out the domain and image of a function is to graph it. First, we enumerate possible elements in the relation:
\[f = \{(0, 0), (1, 1), (4, 2), (9, 3), (16, 4) \ldots\}.\]Note that each element correspond to a point in the 2Dplane. Therefore, we can graph the function as follows:
The domain of \(f\) is the span of \(x\)axis of its graph; the image of \(f\) is the span of \(y\)axis of its graph. From the image, we can tell that both the \(y\) values can go from 0 to an arbitrarily large integer, so we hypothesize its image is \(\mathbb{N}\). The \(x\) values on the graph are \(\{0, 1, 4, 9, 16, \ldots\}\), so we hypothesize that the domain of \(f\) is the set of perfect squares (denoted by \(\mathbb{S}\)). Now, we need to prove this rigorously.
The proof is not difficult. \(\forall (x, y) \in f\), because \(y \in \mathbb{N}\) and \(x = y^2\), it is clear that \(x \in \mathbb{S}\). Because \(\sqrt{c^2} = c\) when \(c \geq 0\), we have \(y = \sqrt{x}\). Due to the fact that \(x \in \mathbb{S}\), we know that \(y \in \mathbb{N}\). Therefore, \(\fdom f = \mathbb{S}\), \(\fim f = \mathbb{N}\).

If \((x, b) \in f\) and \((y, b) \in f\), we have \(x=b^2\), \(y=b^2\). Because \(\sqrt{c^2} = c\) when \(c \geq 0\), we have \(x = y = \sqrt{b}\), which means the function is onetoone.

The inverse function is
\[\begin{align*} f^{1} &= \{(y, x) : (x, y) \in f\}\\ &= \{(y, x) : x \in \mathbb{N}, y \in \mathbb{N}, x=y^2\}\\ &= \{(x, y) : x \in \mathbb{N}, y \in \mathbb{N}, y=x^2\} ~(\mbox{swap}~x~\mbox{and}~y) \end{align*}\]
Let \(x,y \in \mathbb{N}\), If \(y \mid x\) and \(x \mid y\), what is the relationship between \(x\) and \(y\)?
First of all, you can try to come up with examples where \(y \mid x \land x \mid y\) is satisfied. For example, \(x=1, y=1\), \(x=3, y=3\) and so on. Therefore, one may hypothesize that \(y \mid x \land x \mid y \rightarrow x =y\). Now, let’s prove this proposition.
If \(y \mid x\), then \(\exists k_1 \in \mathbb{Z}\), \(x = k_1y\). If \(x \mid y\), then \(\exists k_2 \in \mathbb{Z}\), \(y = k_2x\). If we substitute \(y\) with \(x\), we would have \(x=k_1(k_2x)=k_1k_2x\). For this equality to hold true, the only possibility is \(k_1k_2=1\). Because \(k_1\) and \(k_2\) are both integers, we have \(k_1=k_2=1\) or \(k_1=k_2=1\). But notice that \(x\), \(y\) are natural numbers, so they should be both greater than or equal to zero. Therefore, only \(k_1=k_2=1\) is possible. In this case, \(x=y\) holds.
Find the image of function for \(f(x)=\frac{1}{1 + \lvert x \rvert}~(x \in \mathbb{R})\).
As it is mentioned before, one of most effective ways to find out the image of a function is to graph it. The plot of \(f(x)\) is shown below.
Because the span of \(y\) values of this function plot is between 0 and 1, we hypothesize that its image is between 0 and 1. Let’s prove this rigorously.
 Prove \(f(x) > 0\). This is obviously true because \(1 + \lvert x \rvert > 0\).
 Prove \(f(x) \leq 1\). This is obviously true because \(1 + \lvert x \rvert \geq 1\). The equality holds when \(x=0\).

Denote the set \(\{x \in R : 0 < x \leq 1\}\) by \(S\), we want to show \(\fim f = S\). We need to prove that \(\forall b \in S\), there must be a \(a \in R\) such that \(f(a) = b\). This is essentially solving \(\frac{1}{1 + \lvert a \rvert} = b\). It can be seen that
\[\begin{gather*} \frac{1}{1 + \lvert a \rvert} = b\\ 1 + \lvert a \rvert = \frac{1}{b}\\ \lvert a \rvert = \frac{1b}{b}. \end{gather*}\]Because \(b \in S\), there will always be a solution for \(a\) on \(\mathbb{R}\). (A stricter proof should make use of intermediate value theorem.)
Therefore, we can conclude that \(\fim f = S\).
Suppose \(f^{1} : B \rightarrow A\) is a bijection. Prove that \(f: A \rightarrow B\) is a bijection.
 We know that “\(f^{1} : B \rightarrow A\) is a bijection”. This is a very informative statement, let’s break it down step by step:
 \(f^{1}\) is a function.
 \(f^{1} : B \rightarrow A\) means \(\fdom f^{1} = B\) and \(\fim f^{1} \subseteq A\).
 “bijection” means \(f^{1}\) is both onetoone and onto
 \(f^{1}\) is onto means \(\fim f^{1} = A\).
 Proving “\(f: A \rightarrow B\) is a bijection” also requires many steps:
 Need to show \(f\) is a function
 Need to show \(f\) is from \(A\) to \(B\)
 Need to show \(f\) is onetoone
 Need to show \(f\) is onto \(B\)
Now, let’s prove every single step:
 Notice that \(f = (f^{1})^{1}\). Because \(f^{1}\) is onetoone, we know that \(f\) is a function.
 Because \(\fdom f^{1} = B\) and \(\fim f^{1} = A\), by Proposition 24.18, we know that \(\fdom f = A\) and \(\fim f = B\). This not only shows \(f\) is from \(A\) to \(B\), it also shows \(f\) is onto \(B\).

To show \(f\) is one to one, it is essentially proving \((x, b) \in f \land (y, b) \in f \rightarrow x=y\). It can be seen that
\[\begin{align*} &(x, b) \in f \land (y, b) \in f \rightarrow x=y\\ \Rightarrow & (b, x) \in f^{1} \land (b, y) \in f^{1} \rightarrow x=y, \end{align*}\]which is clearly true because \(f^{1}\) is a function.
Therefore, we can conclude that \(f\) is a bijection.
Let \(f: A \rightarrow B\) be a function. If \(X \subseteq A\), then \(f(X)\) stands for the set of all values \(f\) takes when applied to the elements of \(X\); that is:
\[\begin{align*} f(X) = \{ f(x) : x \in X \}. \end{align*}\]Let \(f : \mathbb{Z} \rightarrow \mathbb{Z}\) be \(f(x) = 2x+1\). If \(X = \{1, 0, 1, 2\}\), find \(f(X)\).
This is just equivalent to applying the function to every single element inside the set. Therefore, we have
\[f(X) = \{1, 1, 3, 5\}.\]Suppose \(f : A \rightarrow B\) is a function and let \(Y\) be a set. Then \(f^{1}(Y)\) is the set of all elements that are mapped to a value in \(Y\). That is,
\[\begin{align*} f^{1}(Y) = \{x \in A : f(x) \in Y\}. \end{align*}\]Let \(f : \mathbb{Z} \rightarrow \mathbb{Z}\) be \(f(x) = x^2\). If \(Y = \{0, 1, 3, 9\}\), find \(f^{1}(Y)\).
In the previous question, we tried to extend the definition of \(f(\cdot)\). In this question, we are trying to extend the definition of \(f^{1}(\cdot)\). However, the difference is that \(f\) is a function, but \(f^{1}\) may not be a function. A a result, \(\lvert f(X) \rvert = \lvert X \rvert\) (assume \(X \subseteq \fdom f\)), but \(\lvert f^{1}(Y) \rvert\) is not necessarily equal to \(\lvert Y \rvert\). To compute \(f^{1}(Y)\), for each \(y \in Y\), we need to find all \(x \in A\) such that \(f(x) = y\). Sometimes, there may be no such \(x\); sometimes, there may be more than one \(x\).
 When \(y = 0\), \(f(0) = 0\).
 When \(y = 1\), \(f(1) = f(1) = 1\).
 When \(y = 3\), there is no \(x \in \mathbb{Z}\) such that \(f(x) = y\).
 When \(y = 9\), \(f(3)=f(3) = 9\).
Therefore, we can write
\[f^{1}(Y) = \{0, 1, 1, 3, 3\}.\]