Skip to main content

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.

Proof.

Let \(t_0\) be an element of \(T\text{,}\) and suppose that \(f(s_1)=f(s_2)=t_0\) for some elements \(s_1,s_2\) in \(S\text{.}\) Applying \(g\) to both sides of \(f(s_1)=f(s_2)\text{,}\) we get \(g(f(s_1))=g(f(s_2))\text{.}\) Because \(g\of f=\One_S\text{,}\) this simplifies to \(\One_S(s_1)=\One_S(s_2)\text{,}\) so \(s_1=s_2\text{.}\) This shows that \(t_0\) has at most one element in its preimage under \(f\text{.}\) Because \(t_0\) was an arbitrary choice, we conclude that every element in \(T\) has at most one element in its preimage under \(f\text{.}\) Therefore \(f\) is injective.
Comment on the proof of Proposition 1.2.2. The proof makes use of the following observation: If \((s,t)\) and \((s',t)\) are elements of an injective function, then it must be the case that \(s=s'\text{.}\) Conversely if \(s=s'\) for every pair of elements of the form \((s,t),(s',t)\) of a function, then that function is injective.
A consequence of Proposition 1.1.4, Proposition 1.2.1, and Proposition 1.2.2 is the following.
The statement that the conditions 1, 2, and 3 in Corollary 1.2.3 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.4.

This exercise refers to the collections of functions is Checkpoint 1.1.3.
  1. Of all the functions from \(\{x,y,z\}\) to \(\{A,B\}\text{,}\) which are injective? Which are surjective?
  2. Of all the functions from \(\{A,B\}\) to \(\{x,y,z\}\text{,}\) which are injective? Which are surjective?
  3. 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{.}\)

Proof.

Because every \(s\) in \(S\) is a preimage of its image \(f(s)\text{,}\) we have \(s\in f^{-1}(\{f(s)\})\text{.}\) If \(t\neq f(s)\text{,}\) we have \(s\not\in f^{-1}(t)\text{.}\) It follows that every \(s\) in \(S\) is an element of exactly one of the preimage sets \(\{f^{-1}(t)\colon t\in T\}\text{.}\)

Exercises Exercises

1.

Find examples illustrating possibilities for surjectivity and injectivity.
  1. Give an example of a one-to-one function \(g\colon T\to T\) that is not onto.
  2. 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.
  1. Suppose that \(f\) is injective. Show that \(|S|\leq |T|\text{.}\)
  2. 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.
  1. Show that if \(f\) is injective and \(|S|=|T|\text{,}\) then \(f\) is surjective.
  2. Show that if \(f\) is surjective and \(|S|=|T|\text{,}\) then \(f\) is injective.