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

The function f(x) = x // 2 (integer division) is an example of a function from N to N that is surjective because every natural number is covered, but not injective because different numbers can result in the same output.

Step-by-step explanation:

To provide an example of a function f from the natural numbers N to N that is surjective but not injective, consider the function f(x) = x // 2, where '//' denotes integer division. For the function to be surjective, each element y in N must have at least one x such that f(x) = y. This is indeed the case here since for any y > 0, we can choose x = 2y or x = 2y + 1, and f(x) will equal y. To show that it is not injective, we can find two different numbers, x1 and x2, such that f(x1) = f(x2). For instance, if x1 = 4 and x2 = 5, both f(x1) and f(x2) equal 2, thus violating the definition of injectivity. Hence, f(x) = x // 2 is surjective because every y in N is an image of some x, but it is not injective because at least two different values in the domain map to the same value in the codomain.