CIS-375 Help Session Note 4 (Spring 2020)

• 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:

  • $\fdom f = \{\ldots, a_{i}, a_{i+1}, a_{i+2}, \ldots, a_{j}, \ldots\}$
  • $\fim f = \{\ldots, b_{i}, b_{i+1}, b_{i+2}, \ldots, b_{j}, \ldots\}$

• 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\).

• 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\).

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

• 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\).

(\(\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\).

• 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\).

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}\).

1. It can be seen that \((1, -1) \in f\) and \((1, 1) \in f\). Because \(-1 \neq 1\), it is not a 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*}\]

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.

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\).

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

This is just equivalent to applying the function to every single element inside the set. Therefore, we have

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