Question

Give an example of a function f : N → N that is surjective but not injective. You must explain why your example is surjective and why it is not injective. Hint: To show that a function f : N → N is surjective, you need to show that for all y ∈ N there is some x ∈ N such that f(x) = y. To show that a function is not injective, simply show that there are two points x1 6= x2 in the domain such that f(x1) = f(x2).

Answer 1

Answer:

Consider f: N → N defined by f(0)=0 and f(n)=n-1 for all n>0.

Step-by-step explanation:

First we will prove that f is surjective. Let y∈N be any natural number. Define x as the number x=y+1. Then x∈N, and f(x)=x-1=(y+1)-1=y.  We conclude that f is surjective.

However, f is not injective. Take x1=0 and x2=1. Then x1≠x2 but f(x1)=0 and f(x2)=x2-1=1-1=0. We have shown that there are two natural numbers x1,x2 such that x1≠x2 but f(x1)=f(x2), that is, f is not injective.

Note:

If 0∉N in your definition of natural numbers, the same reasoning works with the function f: N → N defined by f(1)=1 and f(n)=n-1 for all n>1. The only difference is that you consider x1=1, x2=2 for the injectivity.