Injectivity and Surjectivity

Section 1.3 Injectivity and Surjectivity

In Section 1.2, 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.

🔗

Checkpoint 1.3.1.

This exercise refers to the collections of functions is Checkpoint 1.2.2.

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?

🔗

🔗

Proposition 1.3.2.

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.

🔗

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

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

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.

🔗

Putting together Proposition 1.2.3, Proposition 1.3.2, and Proposition 1.3.3 we have the following.

🔗

Corollary 1.3.5. 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.3.5 are equivalent means that if \(f\) satisfies any one of the three conditions, then \(f\) satisfies the other two conditions as well.

🔗

Exercises Exercises

1.

Is the composition of two injective functions always injective? Is the composition of two surjective functions always surjective? For each question, if the answer is yes, give a proof. If the answer is no, give an example.

🔗

2.

Find examples illustrating possibilities for surjectivity and injectivity for which the domain and codomain are the same set \(T\text{.}\)

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.

🔗

🔗

3.

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.

🔗

4.

Let \(\N=\{0,1,2,3,\ldots\}\text{.}\) Find a function \(f\colon \N\to \N\) such that the number of elements in the set \(f^{-1}(j)\) is \(j\text{,}\) for all \(j\in \N\text{.}\)

🔗

Prev Top Next