There is no doubt that you have heard of the word "function". In fact, you probably know many different kinds of functions, for example, linear functions, polynomial functions, logarithm functions, exponential functions, trignometric functions, etc. But what is the definition of a function? One might say a function is a rule that assigns a number to any chosen number. For example, the function \(y=2x+1\) assigns \(3\) to \(1\), and assigns \(2\pi +1\) to \(\pi\). First of all, what does it mean when we say "assign"? Second, do functions have to do with numbers? Let us consider the following example. Let \(U\) be the set of all members of Utica College and let \(C\) be the set of colors. Let \(f\) be a function from \(U\) to \(C\) that assigns a person their hair color. For example \(f(\text{Xiao Xiao})\) is black. Cleary \(f\) is a function but it has nothing to do with numbers. So what is the definition of a function?
Subsection7.1Basic Definition
Definition7.1
A function from a set \(A\) to a set \(B\) is a relation \(f\) from \(A\) to \(B\) such that the following two conditions hold:
- for any \(a \in A\), there exists \(b \in B\) such that \((a,b) \in f\) and
- the existence of \(b\) is unique, namely, if there exists \(b' \in B\) such that \((a,b') \in f\), then \(b = b'\).
The set \(A\) is called the domain of the function and the set \(B\) is called the codomain of the function. If \((a,b) \in f\), we denote \(b\) by \(f(a)\). We write \(f: A \to B\) and read "\(f\) is a function from \(A\) to \(B\)".
Task7.2
Let \(R = \{1,2,3,4\}\), \(S = \{\alpha,\beta,\gamma\}\) and \(T = \{a,b,c,d,e\}\). Determine which of the following relations is a function from one set to another? Explain your answers. For those that are functions, specify their domains and codomains.
- \(\{(\alpha,2), (\beta, 3), (\gamma, 1)\}\).
- \(\{(a,2),(b,4),(c,1),(d,2)\}\).
- \(\{(1,\alpha), (2, \gamma), (3, \beta), (4, \beta)\}\).
- \(\{(1,c),(2,d),(3,a),(4,b),(4,e)\}\).
Can you use pictures to descrbie these relations?
Definition7.3
Let \(f: A \to B\) be a function. For any element \(a \in A\), the element \(f(a) \in B\) is called the image of \(a\) (in \(B\) under \(f\)). For any \(X \subset A\), the set \begin{equation*}f(X) := \{f(a) \in B \; | \; a \in X\} \subset B\end{equation*} is called the image of \(X\) (in \(B\) under \(f\)). When \(X=A\), we call the set \(f(A)\) the image of the function \(f\).
Task7.4
Let \(A = \{1,2,3,4,5,6\}\) and \(B = \{a,b,c,d,e\}\). Consider the function \(f\) defined by the relation \begin{equation*}\{(1,a), (2,a), (3,c), (4,c), (5,d), (6,e)\}.\end{equation*} Answer the following questions.
- What is \(f(6)\)?
- What is the image of \(3\) in \(B\) under \(f\)?
- What is \(f(\{2,6\})\)?
- What is the image of \(\{1,3\}\) in \(B\) under \(f\)?
- Can you find a subset \(X \subset A\) so that \(f(X) = \emptyset\)?
Task7.5
Let \(f: A \to B\) be a function and \(X \subset A\). Fill in the blanks: \begin{equation*}s \in f(X) \; \text{if and only if} \; \; \exists \; t \in \underline{\hspace{10mm}} \; \text{such that} \; f(\underline{\hspace{5mm}}) = \underline{\hspace{10mm}}\end{equation*}Use the answer above to fill in the next blank \begin{equation*}f(X) := \{b \in B \; | \; \hspace{25mm}\}.\end{equation*}
Definition7.6
Let \(f: A \to B\) be a function. For any element \(b \in B\), the set \begin{equation*}f^{-1}(b) := \{a \in A \; | \; f(a) = b\}\end{equation*} is called the preimage of \(b\). Similarly, for any subset \(Y\) of \(B\), the set \begin{equation*}f^{-1}(Y) := \{a \in A \; | \; f(a) \in Y\}\end{equation*} is called the preimage of \(Y\).
Note that the image of an element in the domain of a function is an element of the codomain but the preimage of an element in codomain is a subset of the domain.
Task7.7
Let \(A = \{1,2,3,4,5,6\}\) and \(B = \{a,b,c,d,e\}\). Consider the function \(f\) defined by the relation
\begin{equation*} \{(1,a), (2,a), (3,c), (4,c), (5,d), (6,e)\}.\end{equation*} Answer the following questions.
- What is \(f^{-1}(a)\)?
- What is the preimage of \(b\)?
- What is \(f^{-1}(\{c,d\})\)?
- What is the preimage of \(\{a, d\}\)?
- Can you find a nonempty subset \(T\) of \(Y\) such that \(f^{-1}(T) = \emptyset\).
Task7.8
Let \(f: A \to B\) be a function and \(Y \subset B\). Fill in the blanks: \begin{equation*}s \in f^{-1}(Y) \; \text{if and only if} \; \; \exists \; t\in \underline{\hspace{10mm}} \; \text{such that} \; f(\underline{\hspace{5mm}}) = \underline{\hspace{10mm}}.\end{equation*}
Task7.9
Let \(f: A \to B\) be a function. Let \(X_1, X_2\) be two subsets of \(A\). Determine which of the following statemsnts is/are true. For the true statements, prove them; for the false statements, find counterexamples.
- If \(X_1 \subset X_2\), then \(f(X_1) \subset f(X_2)\).
- If \(f(X_1) \subset f(X_2)\), then \(X_1 \subset X_2\).
Task7.10
Let \(f: A \to B\) be a function. Let \(Y_1, Y_2\) be two subsets of \(B\). Determine which of the following statemsnts is/are true. For the true statements, prove them; for the false statements, find counterexamples.
- If \(Y_1 \subset Y_2\), then \(f^{-1}(Y_1) \subset f^{-1}(Y_2)\).
- If \(f^{-1}(Y_1) \subset f^{-1}(Y_2)\), then \(Y_1 \subset Y_2\).
Task7.11
Let \(f: A \to B\) be a function. Let \(X_1, X_2\) be two subsets of \(A\) and \(Y_1, Y_2\) be two subsets of \(B\). Determine which of the following statemsnts is/are true. For the true statements, prove them; for the false statements, find counterexamples.
- \(f(X_1 \cap X_2) = f(X_1) \cap f(X_2)\).
- \(f^{-1}(Y_1 \cup Y_2) = f^{-1}(Y_1) \cup f^{-1}(Y_2)\).
Task7.12
Let \(f: A \to B\) be a function. Let \(X_1, X_2\) be two subsets of \(A\) and \(Y_1, Y_2\) be two subsets of \(B\). Determine which of the following statemsnts is/are true. For the true statements, prove them; for the false statements, find counterexamples.
- \(f(X_1 \cup X_2) = f(X_1) \cup f(X_2)\).
- \(f^{-1}(Y_1 \cap Y_2) = f^{-1}(Y_1) \cap f^{-1}(Y_2)\).
Subsection7.2Injection, Surjection, Bijection and Inverse
Definition7.13
Let \(f: A \to B\) be a function. We say that \(f\) is one-to-one provided that for any \(b \in B\) there exists at most one \(a \in A\) such that \(f(a) = b\). If \(f\) is one-to-one, we also say that \(f\) is an injection.
Task7.14
In the definition of one-to-one, "at most one" means there could be one or there could be none. Describe precisely for which \(b \in B\) that there exists exactly one \(a \in A\) so that \(f(a)=b\) and for which \(b \in B\) that there is no \(a \in A\) so that \(f(a)=b\). Give a concrete example to describe your findings.
Definition7.15
Let \(f: A \to B\) be a function. We say that \(f\) is onto provided that for any \(b \in B\) there exists at least one \(a \in A\) such that \(f(a) = b\). If \(f\) is onto, we also say that \(f\) is an surjection.
Task7.16
In the definition of onto, "at least one" means there could be one or there could be more than one. Give a concrete example of a function \(f:A \to B\) so that for some element \(b_1 \in B\), there exsits exactly one \(a \in A\) such that \(f(a)=b_1\), and for some other \(b_2 \in B\), there exists more than one \(a \in A\) such that \(f(a) = b_2\).
Definition7.17
We say that a function \(f: A \to B\) is a one-to-one correspondence, or bijection provided that \(f\) is one-to-one and onto.
Task7.18
Let \(A = \{1,2,3,4,5,6\}\), \(B = \{a,b,c,d,e\}\) and \(C = \{1,2,3,4,5\}\). First find the domain and codomain for each one of the followings and then decide which one is one-to-one, onto, and/or one-to-one correspondence.
- \(\{(1,a),(2,e),(3,d),(4,e),(5,b),(6,c)\}\)
- \(\{(a,3),(c,4),(d,1),(e,2),(a,6),(b,5)\}\)
- \(\{(1,c),(2,e),(3,a),(4,d),(5,b)\}\)
- \(\{(2,4),(1,3),(5,2),(3,1),(4,5)\}\)
Task7.19
Give an example of each of the following and give a brief proof of the properties you claim.
- A function \(f: \mathbb{R} \to \mathbb{R}\) that is one-to-one but not onto.
- A function \(f: \mathbb{R} \to \mathbb{R}\) that is onto but not one-to-one.
- A function \(f: \mathbb{R} \to \mathbb{R}\) that is neither one-to-one nor onto.
- A (non-linear) function \(f: \mathbb{R} \to \mathbb{R}\) that is both one-to-one and onto.
Task7.20
Let \(A = \{a,b\}\) and \(B = \{c,d,e\}\) be two sets.
- Is there a one-to-one function from \(B\) to \(A\)? Explain.
- Is there an onto function from \(A\) to \(B\)? Explain.
- What, in general, can you say about the relative sizes of the domain and codomain of an onto function? A one-to-one function? A one-to-one correspondence?
Before you continue to solve tasks about one-to-one and onto functions, you need to think about what the general strategy should be. If \(f\) is a one-to-one function, then for any element \(b\) in the codomain, that exists at most one element \(a\) in the domain so that \(f(a)=b\). So there are two possibilities, either there is no \(a\) in the domain so that \(f(a) = b\) or there is exactly one element \(a\) in the domain so that \(f(a) = b\). Now let us recall how we show a statement of the form if \(P\), then \(Q\) or \(R\). We show it by assuming \(P \land (\sim Q)\) is true and show that \(R\) is true. Put things in context, we suppose that there is indeed an element \(a\) in the domain so that \(f(a) = b\) (this is the \((\sim Q)\) statement) and show that the choice of \(a\) is unique, namely there is exactly one element \(a\) in the domain so that \(f(a) = b\) (this is the \(R\) statement).
Now how do we show that there is exactly one element \(a\) in the domain so that \(f(a) = b\)? One way of saying the same thing is that it is impossible to have two distinct elements \(a_1\) and \(a_2\) such that \(f(a_1) = f(a_2) = b\), or equivalently, if \(a_1\) and \(a_2\) are two distinct elements in the domain, then \(f(a_1)\) and \(f(a_2)\) are distinct elements in the codomain. Another way of saying the same thing is its contrapositive, namely, if \(f(a_1)\) and \(f(a_2)\) are the same elements in the codomain, then \(a_1\) and \(a_2\) are the same elements in the domain. Now which one do you think is easier to work with. Choose one that you prefer and solve the following tasks.
The strategy of showing a function is onto is much simpler. To show that for every \(b\) in the codomain, there exists an element \(a\) in the domain such that \(f(a)=b\), we just have to find an expression of \(a\) (in terms of \(b\)) such that when we plug in the expression of \(a\) into the formula of \(f\), we are guarantee to get \(b\).
For each of the following three tasks, find out if the function is one-to-one, onto, and/or one-to-one correspondence. Explain your answer.
Task7.21
\(f_1: \mathbb{R} \to \mathbb{R}\) defined by \(f_1(s) = 3s+2\).
Task7.22
Let \(O\) be the set of odd integers and \(S = \{4n-3 \; | \; n \in \mathbb{Z} \}\). Let \(f_2: O \to S\) defined by \(f_2(m) = 2m+3\). (Hint: Think about why \(2\) times any odd integer plus \(3\) must be a number of the form \(4n-3\).)
Task7.23
As above, let \(O\) be the set of odd integers. Let \(f_3: \mathbb{Z} \to O\) defined by \(f_3(n) = n^2+n+1\). (Hint: Think about why any integer squared plus that same intege, and then plus one must be odd.)
Definition7.24
For any function \(f: A \to B\), we define its inverse relation \begin{equation*}\text{INV}(f) = \{(b,a) \; | \; (a,b) \in f\}.\end{equation*}
Task7.25
In the definition of inverse relation, we know that the function \(f\) (as a relation) is a subset of \(A \times B\). Which set contains the inverse relation \(\text{INV}(f)\) as a subset?
For each one of the functions in Task 7.18, write down their inverse relations. Then determine which one(s) of the inverse relations are functions.
Task7.26
Let \(f: A \to B\) be a function. The inverse relation \(\text{INV}(f)\) is a function (from \(B\) to \(A\)) if and only if \(f\) is a one-to-one correspondence.
Definition7.27
If \(f: A \to B\) is a one-to-one correspondence, then the function defined by its inverse relation \(\text{INV}(f)\) is called the inverse of \(f\), and is denoted by \(f^{-1}\).
Definition7.28
If \(f: A \to B\) and \(g: B \to C\) are two functions, then a new function \(g\circ f : A \to C\) can be defined by \((g \circ f)(a) = g(f(a))\) for all \(a \in A\). The new function \(g \circ f\) is called \(g\) composed with \(f\).
Let us investigate some relationship betweens \(g, f\) and \(g \circ f\).
Task7.29
Give an example of functions \(f: A \to B\) and \(g: B \to C\) such that
- \(f\) is onto and \(g \circ f\) is not;
- \(g\) is onto and \(g \circ f\) is not;
- \(f\) is one-to-one and \(g \circ f\) is not;
- \(g\) is one-to-one and \(g \circ f\) is not.
Task 7.29 says that if only one of \(f\) and \(g\) is one-to-one (respectively onto) then \(g \circ f\) does not have to be one-to-one (respectively onto). The next task says that if both \(f\) and \(g\) are one-to-one (respectively onto) then \(g \circ f\) will be as well.
Task7.30
Let \(f: A \to B\) and \(g: B \to C\) be two functions. Prove or disprove the following two statements:
- if \(f\) and \(g\) are both one-to-one, then \(g \circ f\) is one-to-one;
- if \(f\) and \(g\) are both onto, then \(g \circ f\) is onto.
Now let us consider the converse. Suppose \(g\circ f\) is one-to-one (respectively onto), can we say that \(f\) and/or \(g\) is one-to-one (respectively onto) as well?
Task7.31
Let \(f: A \to B\) and \(g: B \to C\) be two functions. Prove or disprove of the following statements:
- If \(g \circ f\) is one-to-one, then \(f\) is one-to-one.
- If \(g \circ f\) is one-to-one, then \(g\) is one-to-one.
- If \(g \circ f\) is onto, then \(f\) is onto.
- If \(g \circ f\) is onto, then \(g\) is onto.
(You need to give an explicit counter-example if you want to disprove one of these statements.)
Given three functions \(f: A \to B\), \(g: B \to C\) and \(h: C \to D\), there are two ways to compose them. We can first compose \(g\) with \(f\) to get \(g \circ f : A \to C\), then compose \(h\) with \(g \circ f\) to get \(h \circ (g \circ f) : A \to C\). Or we can first compose \(h\) with \(g\) to get \(h \circ g: B \to C\), then compose \(h \circ g\) with \(f\) to get \((h \circ g) \circ f : A \to C\). We know that \(h \circ (g \circ f) : A \to C\) and \((h \circ g) \circ f): A \to C\) have the same domain and codomain but are they the same functions?
Task7.32
Prove that composition is associative, namely, \begin{equation*}h \circ (g \circ f) = (h \circ g) \circ f.\end{equation*}
Definition7.33
For any set \(A\), there exists a function \(\mathrm{id}_A : A \to A\) defined by \(\mathrm{id}_A(a) = a\) for all \(a \in A\). This function \(\mathrm{id}_A\) is called the identity function on \(A\).
Question: Is \(\mathrm{id}_A\) one-to-one? Is \(\mathrm{id}_A\) onto?
Task7.34
If \(f: A \to B\) is a one-to-one correspondence, then prove that \(f^{-1} \circ f = \mathrm{id}_A\) and \(f \circ f^{-1} = \mathrm{id}_B\). (Hint: Think about the definition of \(f^{-1}\).)
Task7.35
For any function \(f: A \to B\), if there exists another function \(g : B \to A\) such that \(g \circ f = \mathrm{id}_A\) and \(f \circ g = \mathrm{id}_B\), show that \(f\) is a one-to-one correspondence and \(g = f^{-1}\). (Hint: Task 7.31)
Task7.36
Prove or disprove:
- If \(f: A \to B\) and \(g : B \to C\) are both one-to-one correspondence, then \(g \circ f\) is also a one-to-one correspondence.
- If \(g \circ f\) is a one-to-one correspondence, then \(f\) and \(g\) are both one-to-one correspondence.
Task7.37
Suppose that \(f: A \to B\) and \(g: B \to C\) are both one-to-one correspondence. Show that \((g \circ f)^{-1} = f^{-1} \circ g^{-1}\). Can you explain why this principle can be called the "Socks and Shoes" principle? (Hint: Task 7.35.)
