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