Proposition 1.2.1.
Let \(f\colon S\to T\) be a function, and suppose that there exists a function \(g\colon T\to S\) such that \(f\of g =
\One_T\text{.}\) Then \(f\) is surjective.
Section 1.2 Properties of Functions
In Section 1.1, we note that a function is invertible if every element in the codomain has exactly one preimage. A function is surjective, or onto, if every element of the codomain has at least one preimage. A function is injective, or one-to-one, if every element of the codomain has at most one preimage. A function is bijective if it is both injective and surjective, that is, if every element in the codomain is the right entry of exactly one element of the function. Thus, the adjectives "bijective" and "invertible" mean the same thing. A bijective function is also called a one-to-one correspondence.
Proof.
Let \(t_0\) be an element of \(T\text{,}\) and let \(s_0=g(t_0)\text{.}\) Applying \(f\) to both sides of the last equation, we have \(f(s_0)=f(g(t_0))\text{.}\) Because \(f\of
g=\One_T\text{,}\) the last expression simplifies to \(\One_T(t_0)=t_0\text{.}\) This shows that the preimage of \(t_0\) under \(f\) has at least one element, namely \(s_0\text{.}\) Because \(t_0\) was an arbitrary choice, we conclude that every element in \(T\) has at least one element in its preimage under \(f\text{.}\) Therefore \(f\) is surjective.
Proposition 1.2.2.
Let \(f\colon S\to T\) be a function, and suppose that there exists a function \(g\colon T\to S\) such that \(g\of f =
\One_S\text{.}\) Then \(f\) is injective.
Proof.
Let \(t_0\) be an element of \(T\text{,}\) and let \(s_0=g(t_0)\text{.}\) If \(s_1\) is a preimage of \(t_0\) under \(f\text{,}\) then \(f(s_1)=t_0\text{.}\) Applying \(g\) to both sides of \(f(s_1)=t_0\text{,}\) we have \(g(f(s_1))=g(t_0)\text{.}\) On the right side, we have \(g(t_0)=s_0\text{.}\) On the left, we have \(g(f(s_1))=(g\circ f)(s_1)=\One(s_1)=s_1\text{.}\) Therefore we have \(s_1=s_0\text{.}\) This shows that any preimage of \(t_0\) under \(f\) must be equal to \(s_0\text{.}\) Because \(t_0\) was an arbitrary choice, we conclude that every element in \(T\) has at most one preimage under \(f\text{.}\) Therefore \(f\) is injective.
Comment on Proposition 1.2.1 and Proposition 1.2.2 and the Axiom of Choice.
The converse of Proposition 1.2.1 is equivalent to the Axiom of Choice. The Axiom of Choice is not used in the facts that appear in this section. By contrast, the converse of Proposition 1.2.2 does not require the Axiom of Choice.
Checkpoint 1.2.3.
The proofs for the two previous propositions both begin with the sentence "Let \(t_0\) be an element of \(T\text{,}\) and let \(s_0=g(t_0)\text{.}\)"
- In the first proof, we end up concluding that \(s_0\) is a preimage of \(t_0\) under \(f\text{.}\) Do we get the same conclusion in the second proof? If the answer is "no", then give an explicit example that shows why the answer is no.
- In the first proof, do we show that \(s_0\) is the only preimage of \(t_0\) under \(f\text{,}\) or could there be others? If the answer is "no", then give an explicit example that shows why the answer is no.
"Explicit" means you must list all the elements of the sets \(S,T\) and all the ordered pairs in the functions \(f,g\text{.}\)
Hint.
The answer to both questions is indeed "no". Use small finite sets for your examples.
Instructor’s solution for Checkpoint 1.2.3.
- No. It is possible that \(t_0\) could have 0 preimages under \(f\text{.}\) The second proof shows that if \(t_0\) has a preimage, then in has only one preimage. Example: let \(S=\{a\}\text{,}\) \(T=\{x,y\}\text{,}\) \(f=\{(a,x)\}\text{,}\) \(g=\{(x,a),(y,a)\}\text{,}\) and \(t_0=y\text{.}\) The hypotheses of the second proof are satisfied, that is, we have \(g\of f = \{(a,a)\}= \One_S\text{,}\) but \(a\) is not a preimage of \(t_0=y\text{.}\)
- No. It is possible for \(t_0\) to have many preimages under \(f\text{.}\) The proof shows that \(t_0\) has at least one preimage. Example: let \(S=\{a,b\}\text{,}\) \(T=\{x\}\text{,}\) \(f=\{(a,x),(b,x)\}\text{,}\) \(g=\{(x,a)\}\text{,}\) and \(t_0=x\text{.}\) The hypotheses of the first proof are satisfied, that is, we have \(f\of g = \{(x,x)\}=\One_T\text{,}\) but \(a=g(x)\) is not the only preimage of \(t_0=x\text{.}\)
Corollary 1.2.4. Characterization of invertibility.
The following conditions are equivalent for a function \(f\colon S\to T\text{.}\)
- The inverse relation \(f^{-1}\subseteq T\times S\) is a function \(f^{-1}\colon T\to S\text{.}\)
- The function \(f\colon S\to T\) is surjective and injective.
- There exists a function \(g\colon T\to S\) such that \(g\of f = \One_S\) and \(f\of g = \One_T\text{.}\)
The statement that the conditions 1, 2, and 3 in Corollary 1.2.4 are equivalent means that if \(f\) satisfies any one of the three conditions, then \(f\) satisfies the other two conditions as well.
Checkpoint 1.2.5.
This exercise refers to the collections of functions is Checkpoint 1.1.3.
- Of all the functions from \(\{x,y,z\}\) to \(\{A,B\}\text{,}\) which are injective? Which are surjective?
- Of all the functions from \(\{A,B\}\) to \(\{x,y,z\}\text{,}\) which are injective? Which are surjective?
- Of all the functions from \(\{x,y,z\}\) to \(\{x,y,z\}\text{,}\) which are injective? Which are surjective?
Instructor’s solution for Checkpoint 1.2.5.
- Of the 8 functions\begin{equation*} (A,A,A),(A,A,B),(A,B,A),(A,B,B),(B,A,A),(B,A,B),(B,B,A),(B,B,B), \end{equation*}none are injective because each function list contains two occurrences of at least one of the two output values. All of the functions are surjective except for \((A,A,A)\) and \((B,B,B)\text{.}\)
- Of the 9 functions\begin{equation*} (x,x),(x,y), (x,z), (y,x), (y,y), (y,z),(z,x),(z,y),(z,z), \end{equation*}6 are injective, that is, all but \((x,x), (y,y),(z,z)\text{.}\) None are surjective because none of the lists contains all three letters \(x,y,z\text{.}\)
- Of the 27 functions, 6 are injective, and the same 6 are surjective Here are those 6.\begin{equation*} (x,y,z),(x,z,y), (y,x,z), (y,z,x), (z,x,y), (z,y,x) \end{equation*}
Some counting. A set is called finite if it contains a finite number of elements. A set that is not finite is called infinite. The number of elements in a finite set \(S\) is called the size of \(S\text{,}\) denoted \(|S|\) . Formally, we say \(|S|=n\text{,}\) where \(n\) is a positive integer, if there exists a one-to-one correspondence \(\{1,2,\ldots,n\} \to S\text{.}\)
Proposition 1.2.6. Counting elements in a set using preimages.
Let \(f\colon S\to T\) be a function, where \(S,T\) are finite sets. We have
\begin{equation}
|S|=\sum_{t\in T} |f^{-1}(t)|.\tag{1.2.1}
\end{equation}
Proof.
Exercises Exercises
1.
Find examples illustrating possibilities for surjectivity and injectivity.
- Give an example of a one-to-one function \(g\colon T\to T\) that is not onto.
- Give an example of an onto function \(g\colon T\to T\) that is not one-to-one.
Instructor’s solution for Exercise 1.2.1.
- Let \(T=\{1,2,3,\ldots\}\) and consider \(g\colon T \to T\) defined by \(g(n)=n+1\text{.}\) It is clear that \(g\) is one-to-one but not onto.
- Let \(T=\{0,1,2,3,\ldots\}\) and let \(g\) be given by \(g(n)=\lfloor n/2\rfloor\text{.}\) It is clear that \(g\) is onto but not one-to-one.
2.
Suppose that \(f\) and \(g\) are both invertible, and that the composition \(g\of f\) is defined. Show that \(g\of f\) is invertible and that \((g\of f)^{-1} = f^{-1} \of g^{-1}\text{.}\) This fact is referred to as the "socks and shoes" property.
Instructor’s solution for Exercise 1.2.2.
Let \(h=f^{-1} \of g^{-1}\text{.}\) Let \(s\) be in the domain of \(f\text{.}\) We have
\begin{align*}
(h \of (g\of f))(s)
\amp= h(g(f(s)) \amp \amp \text{(definition of composition)}\\
\amp= f^{-1}(g^{-1}(g(f(s)))) \amp \amp (\text{definition of } h)\\
\amp= f^{-1}((g^{-1}\of g)(f(s))) \amp \amp (\text{(associativity of
function composition})\\
\amp= f^{-1}(f(s)) \amp \amp (g^{-1}\of g \text{ is the identity
function})\\
\amp= s\amp \amp (f^{-1}\of f \text{ is the identity
function})
\end{align*}
This establishes that \(h\of (g\of f)\) is the identity function on the domain of \(f\text{.}\) A similar derivation shows that \((g\of f)\of h\) is the identity function on the codomain of \(g\text{.}\) We conclude that \((g\of f)\) is invertible, with inverse \((g\of f)^{-1} = h = f^{-1}
\of g^{-1}\text{,}\) as desired.
3.
Let \(f\colon S\to T\) be a function, where \(S,T\) are finite sets. Use (1.2.1) to show the following.
- Suppose that \(f\) is injective. Show that \(|S|\leq |T|\text{.}\)
- Suppose that \(f\) is surjective. Show that \(|S|\geq |T|\text{.}\)
Instructor’s solution for Exercise 1.2.3.
- If \(f\) is injective, we have \(|f^{-1}(t)|\) is zero or one for all \(t\in T\text{.}\) Using (1.2.1), we have\begin{equation*} |S| = \sum_{t\in T} |f^{-1}(t)| \leq \sum_{t\in T} 1 = |T|. \end{equation*}
- If \(f\) is surjective, we have \(|f^{-1}(t)|\geq 1\) for all \(t\in T\text{.}\) Using (1.2.1), we have\begin{equation*} |S| = \sum_{t\in T} |f^{-1}(t)| \geq \sum_{t\in T} 1 = |T|. \end{equation*}
4.
Let \(f\colon S\to T\) be a function, where \(S,T\) are finite sets.
- Show that if \(f\) is injective and \(|S|=|T|\text{,}\) then \(f\) is surjective.
- Show that if \(f\) is surjective and \(|S|=|T|\text{,}\) then \(f\) is injective.
Instructor’s solution for Exercise 1.2.4.
- If \(f\) is injective, we have \(|f^{-1}(t)|\) is zero or one for all \(t\in T\text{.}\) Using (1.2.1), we have\begin{equation*} |S| = \sum_{t\in T} |f^{-1}(t)| \leq \sum_{t\in T} 1 = |T|. \end{equation*}The only way that the sum \(\sum_{t\in T} |f^{-1}(t)|\) can be equal to \(\sum_{t\in T} 1 \) is for every preimage set \(f^{-1}(t)\) to have exactly one element, never zero elements. This means that if \(|S|=|T|\text{,}\) then \(f\) must be surjective.
- If \(f\) is surjective, we have \(|U_t|\geq 1\) for all \(t\in T\text{.}\) Using (1.2.1), we have\begin{equation*} |S| = \sum_{t\in T} |f^{-1}(t)| \geq \sum_{t\in T} 1 = |T|. \end{equation*}The only way that the sum \(\sum_{t\in T} |f^{-1}(t)|\) can be equal to \(\sum_{t\in T} 1 \) is for every preimage set \(f^{-1}(t)\) to have exactly one element, never more than one element. This means that if \(|S|=|T|\text{,}\) then \(f\) must be injective.
