10.2: Properties of Functions
( \newcommand{\kernel}{\mathrm{null}\,}\)
a function whose image is all of its codomain — that is, every element of the codomain is an output for the function;
a surjective function
synonym for surjective
function f is surjective
A function f:A→B is surjective if f(A)=B. Since we have f(A)⊆B by definition of image, to show that a function is surjective we only need to show f(A)⊇B.
- Function f:A→B is surjective if B⊆f(A). That is, f is surjective if for every element b∈B, there exists at least one element a∈A such that f(a)=b.
- Function f:A→B is not surjective if there exists at least one element b∈B for which there is no element a∈A satisfying f(a)=b. (Equivalently, there exists b∈B for which every a∈A satisifes f(a)≠b.)
Show that, of the following functions, f is surjective and g is not.
f:Z→Ng:Z→Qm↦|m|m↦m/2
Solution
Show that f is surjective.
Consider an arbitrary element n of the codomain N. Since N⊆Z, n is also an element of the domain. In particular, f(n)=n, since n≥0. Therefore, as an element of the codomain, we have n∈f(Z).
Show that g is not surjective.
We need to find a specific example of a rational number that is not an output for g. For this, we could use 1/3, since there is no integer such that m/2=1/3.
a function for which two different inputs never produce the same output
an injective function
synonym for injection
synonym for injective
function f is injective
Function f:A→B is injective if the following conditional always holds for elements a1,a2∈A:
if a1≠a2 then f(a1)≠f(a2).
Alternatively, one can establish that the contrapositive of the above conditional always holds for elements a1,a2∈A:
if f(a1)=f(a2) then a1=a2.
Function f:A→B is not injective if there exists at least one pair of elements a1,a2∈A with a1≠a2 but f(a1)=f(a2).
The function f:R→R, f(x)=x2, is not injective, since f has repeated outputs. For example, f(−1)=f(1). And in fact, f(−x)=f(x) for every x∈R.
Verify that the function f:N→N, f(n)=2n+1, is injective.
Solution
Using the contrapositive version of the Injective Function Test, suppose domain elements n1,n2∈N satisfy f(n1)=f(n2). Then using the formula defining the input-output rule for f, we have
2n1+1=2n2+1,
which reduces to n1=n2.
An injection f:A↪B gives us a way of thinking of A as a subset of B, by considering f(A)⊆B.
Let Σ={a,b,…,z}, and define φ:Σ→N by the following table.
σ | a | b | c | ⋯ | z |
φ(σ) | 1 | 2 | 3 | ⋯ | 26 |
Then f embeds Σ into N in a familiar way, and lets us think of letters as numbers.
a function that is both injective and surjective
an bijective function
synonym for bijection
Function f:R→R, f(x)=x3 is bijective.
A bijection f:A→B allows us to think of A and B as essentially the same sets.
Consider again f:Σ→N from Example 10.2.4. If we write B=f(Σ)={1,2,3,…,26}, then really we could think of the function as being defined f:Σ→B. This version of f is bijective, and allows us to identify each letter with a corresponding number:
a↔1,b↔2,c↔3,…,z↔26.
In this way, we can think of Σ and B as essentially the same set.
Which of the following functions are bijections?
f:Z→Z,g:Z→N,h:Z→Z,m↦2m,m↦|m|,m↦−m.
Solution.
Is f bijective?.
No, f is not bijective because it is not surjective. For example, there is no m∈Z such that f(m)=1.
Is g bijective?.
No, g is not bijective because it is not injective. For example, g(−1)=g(1).
Is h bijective?.
Yes, h is bijective. It is injective because if m1≠m2 then −m1≠−m2. And it is surjective because for n∈Z, we can realize n as an output n=h(m) by setting m=−n.
Checkpoint 10.2.1: Bijections of counting sets.
For m∈N write
N<m={n∈N→n<m={0,1,…,m−1}.
Prove that there exists a bijection N<l→N<m if and only if ℓ=m.