# CIS-375 Help Session Note 4 (Spring 2020)

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


• 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 (One-to-one) A function $$f$$ is called one-to-one 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 one-to-one.

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. One-to-one 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 one-to-one.

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 one-to-one and onto $$B$$.

($$\Rightarrow$$) Suppose $$f^{-1}$$ is a function from $$B$$ to $$A$$.

• Because $$f^{-1}$$ is a function, $$f$$ has to be one-to-one.
• 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 one-to-one and onto $$B$$.

• Because $$f$$ is one-to-one, 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 one-to-one and onto.

• Using mathematical expression, bijection can be written as follows:
• (one-to-one) $$(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

1. If $$f: A \rightarrow B$$, $$\fdom f = A$$?
2. If $$f: A \rightarrow B$$, $$\fim f = B$$?
3. When is $$f^{-1}$$ a function (when is $$f$$ intervible)?
4. If $$f: A \rightarrow B$$ is one-to-one, is $$f^{-1}: B \rightarrow A$$?
1. (✔) Yes, by definition.
2. (✘) No, $$\fim f \subseteq B$$.
3. A function $$f$$ is invertible if and only if it is one-to-one. Keep in mind that $$f^{-1}$$ always exists as a relation, but is not necessarily a function.
4. (✘) 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}$$.
$f = \{(x, y) : x \in \mathbb{Z}, y \in \mathbb{Z}, x=y^2 \}$
1. Is it a function? If not, explain why and stop. Otherwise, continue with the remaining questions.
2. What are its domain and image?
3. Is the function one-to-one? If not, explain why and stop. Otherwise, answer the remaining question.
4. What is its inverse function?
1. It can be seen that $$(1, -1) \in f$$ and $$(1, 1) \in f$$. Because $$-1 \neq 1$$, it is not a function.
$f = \{(x, y) : x \in \mathbb{N}, y \in \mathbb{N}, x=y^2 \} \quad (\mathbb{N} = \{0, 1, 2, \ldots\})$
1. Is it a function? If not, explain why and stop. Otherwise, continue with the remaining questions.
2. What are its domain and image?
3. Is the function one-to-one? If not, explain why and stop. Otherwise, answer the remaining question.
4. What is its inverse function?
1. 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.

2. 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 2D-plane. 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}$$.

3. 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 one-to-one.

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

1. Prove $$f(x) > 0$$. This is obviously true because $$1 + \lvert x \rvert > 0$$.
2. Prove $$f(x) \leq 1$$. This is obviously true because $$1 + \lvert x \rvert \geq 1$$. The equality holds when $$x=0$$.
3. 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{1-b}{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 one-to-one 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 one-to-one
• Need to show $$f$$ is onto $$B$$

Now, let’s prove every single step:

• Notice that $$f = (f^{-1})^{-1}$$. Because $$f^{-1}$$ is one-to-one, 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\}.$